We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that n randomized queries and n/2 quantum queries are needed to compute parity on all inputs. But surprisingly, we give a randomized algorithm for Weak Parity that makes only O(n/log^0.246(1/eps)) queries, as well as a quantum algorithm that makes only O(n/sqrt(log(1/eps))) queries. We also prove a lower bound of Omega(n/log(1/eps)) in both cases; and using extremal combinatorics, prove lower bounds of Omega(log n) in the randomized case and Omega(sqrt(log n)) in the quantum case for any eps>0. We show that improving our lower bounds is intimately related to two longstanding open problems about Boolean functions: the Sensitivity Conjecture, and the relationships between query complexity and polynomial degree.
The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponential. On the other hand, we use a computerized exhaustive search to prove tightness of this bound.
This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to
1/2. Our contributions include the following: i) An analysis of the optimal success probability of quantum and randomized query algorithms of two fundamental partial symmetric Boolean functions given a fixed number of queries. We prove that for any quantum algorithm computing these two functions using
T queries, there exist randomized algorithms using
poly(T) queries that achieve the same success probability as the quantum algorithm, even if the success probability is arbitrarily close to 1/2. ii) We establish that for any total symmetric Boolean function
f, if a quantum algorithm uses
T queries to compute
f with success probability
1/2+β, then there exists a randomized algorithm using
O(T2) queries to compute
f with success probability
1/2+Ω(δβ2) on a
1−δ fraction of inputs, where
β,δ can be arbitrarily small positive values. As a corollary, we prove a randomized version of Aaronson-Ambainis Conjecture for total symmetric Boolean functions in the regime where the success probability of algorithms can be arbitrarily close to 1/2. iii) We present polynomial equivalences for several fundamental complexity measures of partial symmetric Boolean functions. Specifically, we first prove that for certain partial symmetric Boolean functions, quantum query complexity is at most quadratic in approximate degree for any error arbitrarily close to 1/2. Next, we show exact quantum query complexity is at most quadratic in degree. Additionally, we give the tight bounds of several complexity measures, indicating their polynomial equivalence.
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on n input bits, each of which has approximate Fourier sparsity at most O(n³) and randomized parity decision tree complexity Θ(n). This improves upon the recent work of Chattopadhyay, Mande and Sherif [Chattopadhyay et al., 2020] both qualitatively (in terms of designing a large number of examples) and quantitatively (shrinking the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
Query complexity studies the amount of information about an input that is needed to solve a computational problem. This thesis investigates query complexity in several settings, with applications to cryptography and property testing, as well as connections to communication complexity and other computational models. In property testing, we study tolerant junta testing and establish the first superpolynomial quantum advantage for this problem: within a certain parameter regime, a quantum algorithm uses polynomially many queries, whereas every classical randomised algorithm requires quasipolynomially many queries. In cryptography, we study the average-case complexity of search problems. We show that verifiable delay functions do not exist in the random oracle model, and strengthen known barriers to constructing average-case hard TFNP problems from one-way functions. Finally, we study lower bounds and their behaviour across computational models. We prove new direct sum results for randomised parity decision trees. We also establish a new separation between query complexity measures of total Boolean functions and, through query-to-communication lifting, derive new communication lower bounds and lower bounds for unambiguous finite automata.