0000000000550031
AUTHOR
Juris Smotrovs
Enumerable classes of total recursive functions: Complexity of inductive inference
This paper includes some results on complexity of inductive inference for enumerable classes of total recursive functions, where enumeration is considered in more general meaning than usual recursive enumeration. The complexity is measured as the worst-case mindchange (error) number for the first n functions of the given class. Three generalizations are considered.
A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases
The paper gives a short introduction to mutually unbiased bases and the Welch bounds and demonstrates that the latter is a good technical tool to explore the former. In particular, a criterion for a system of vectors to satisfy the Welch bounds with equality is given and applied for the case of MUBs. This yields a necessary and sufficient condition on a set of orthonormal bases to form a complete system of MUBs. This condition takes an especially elegant form in the case of homogeneous systems of MUBs. We express some known constructions of MUBs in this form. Also it is shown how recently obtained results binding MUBs and some combinatorial structures (such as perfect nonlinear functions an…
Worst Case Analysis of Non-local Games
Non-local games are studied in quantum information because they provide a simple way for proving the difference between the classical world and the quantum world. A non-local game is a cooperative game played by 2 or more players against a referee. The players cannot communicate but may share common random bits or a common quantum state. A referee sends an input x i to the i th player who then responds by sending an answer a i to the referee. The players win if the answers a i satisfy a condition that may depend on the inputs x i .
Quantum Strategies Are Better Than Classical in Almost Any XOR Game
We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1−o(1) fraction of all 2-player XOR games.
A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases
The paper gives a short introduction to mutually unbiased bases and the Welch bounds and demonstrates that the latter is a good technical tool to explore the former. In particular, a criterion for a system of vectors to satisfy the Welch bounds with equality is given and applied for the case of MUBs. This yields a necessary and sufficient condition on a set of orthonormal bases to form a complete system of MUBs. This condition takes an especially elegant form in the case of homogeneous systems of MUBs. We express some known constructions of MUBs in this form. Also it is shown how recently obtained results binding MUBs and some combinatorial structures (such as perfect nonlinear functions an…
Closedness properties in ex-identification
In this paper we investigate in which cases unions of identifiable classes are also necessarily identifiable. We consider identification in the limit with bounds on mindchanges and anomalies. Though not closed under the set union, these identification types still have features resembling closedness. For each of them we and n such that (1) if every union of n − 1 classes out of U1, ... , Un is identifiable, so is the union of all n classes; (2) there are classes U1, ... ,Un−1 such that every union of n−2 classes out of them is identifiable, while the union of n − 1 classes is not. We show that by finding these n we can distinguish which requirements put on the identifiability of unions of cl…
Separations in Query Complexity Based on Pointer Functions
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. We show this is false by giving an example of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $\Omega(n/\log(n))$ while its zero-error randomized query complexity is $\tilde O(\sqrt{n})$. We further show that the quantum query complexity of the same function is $\tilde O(n^{1/4})$, giving the first example of a total function with a super-quadra…
Closedness properties in team learning of recursive functions
This paper investigates closedness properties in relation with team learning of total recursive functions. One of the first problems solved for any new identification types is the following: “Does the identifiability of classes U1 and U2 imply the identifiability of U1∪U2?” In this paper we are interested in a more general question: “Does the identifiability of every union of n−1 classes out of U1,...,Un imply the identifiability of U1∪...∪Un?” If the answer is positive, we call such identification type n-closed. We show that n-closedness can be equivalently formulated in terms of team learning. After that we find for which n team identification in the limit and team finite identification t…
Effects of Kolmogorov complexity present in inductive inference as well
For all complexity measures in Kolmogorov complexity the effect discovered by P. Martin-Lof holds. For every infinite binary sequence there is a wide gap between the supremum and the infimum of the complexity of initial fragments of the sequence. It is assumed that that this inevitable gap is characteristic of Kolmogorov complexity, and it is caused by the highly abstract nature of the unrestricted Kolmogorov complexity.
Closedness Properties in EX-Identification of Recursive Functions
In this paper we investigate in which cases unions of identifiable classes of recursive functions are also necessarily identifiable. We consider identification in the limit with bounds on mindchanges and anomalies. Though not closed under the set union, these identification types still have features resembling closedness. For each of them we find such n that 1) if every union of n - 1 classes out of U1;, . . ., Un is identifiable, so is the union of all n classes; 2) there are such classes U1;, . . ., Un-1 that every union of n-2 classes out of them is identifiable, while the union of n - 1 classes is not. We show that by finding these n we can distinguish which requirements put on the iden…
Parameterized Quantum Query Complexity of Graph Collision
We present three new quantum algorithms in the quantum query model for \textsc{graph-collision} problem: \begin{itemize} \item an algorithm based on tree decomposition that uses $O\left(\sqrt{n}t^{\sfrac{1}{6}}\right)$ queries where $t$ is the treewidth of the graph; \item an algorithm constructed on a span program that improves a result by Gavinsky and Ito. The algorithm uses $O(\sqrt{n}+\sqrt{\alpha^{**}})$ queries, where $\alpha^{**}(G)$ is a graph parameter defined by \[\alpha^{**}(G):=\min_{VC\text{-- vertex cover of}G}{\max_{\substack{I\subseteq VC\\I\text{-- independent set}}}{\sum_{v\in I}{\deg{v}}}};\] \item an algorithm for a subclass of circulant graphs that uses $O(\sqrt{n})$ qu…
Unions of identifiable classes of total recursive functions
J.Barzdin [Bar74] has proved that there are classes of total recursive functions which are EX-identifiable but their union is not. We prove that there are no 3 classes U1, U2, U3 such that U1∪U2,U1∪U3 and U2∪U3 would be in EX but U1∪U2∪U3∉ EX. For FIN-identification there are 3 classes with the above-mentioned property and there are no 4 classes U1, U2, U3, U4 such that all 4 unions of triples of these classes would be identifiable but the union of all 4 classes would not. For identification with no more than p minchanges a (2p+2−1)-tuple of such classes do exist but there is no (2p+2)-tuple with the above-mentioned properly.
Worst case analysis of non-local games
Non-local games are studied in quantum information because they provide a simple way for proving the difference between the classical world and the quantum world. A non-local game is a cooperative game played by 2 or more players against a referee. The players cannot communicate but may share common random bits or a common quantum state. A referee sends an input $x_i$ to the $i^{th}$ player who then responds by sending an answer $a_i$ to the referee. The players win if the answers $a_i$ satisfy a condition that may depend on the inputs $x_i$. Typically, non-local games are studied in a framework where the referee picks the inputs from a known probability distribution. We initiate the study …
Multi-letter reversible and quantum finite automata
The regular language (a+b)*a (the words in alphabet {a, b} having a as the last letter) is at the moment a classical example of a language not recognizable by a one-way quantum finite automaton (QFA). Up to now, there have been introduced many different models of QFAs, with increasing capabilities, but none of them can cope with this language. We introduce a new, quite simple modification of the QFA model (actually even a deterministic reversible FA model) which is able to recognize this language. We also completely characterise the set of languages recognizable by the new model FAs, by finding a "forbidden construction" whose presence or absence in the minimal deterministic (not necessaril…
Unions of identifiable families of languages
This paper deals with the satisfiability of requirements put on the identifiability of unions of language families. We consider identification in the limit from a text with bounds on mindchanges and anomalies. We show that, though these identification types are not closed under the set union, some of them still have features that resemble closedness. To formalize this, we generalize the notion of closedness. Then by establishing “how closed” these identification types are we solve the satisfiability problem.
Quantum strategies are better than classical in almost any XOR game
We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1-o(1) fraction of all 2-player XOR games.