arXiv:1209.3849 · Chicago Journal of Theoretical Computer Science

The non-adaptive query complexity of testing k-parities

Harry Buhrman, Garcia-Soriano, David, Arie Matsliah, Ronald de Wolf

Published Sep 18, 2012• 26 citations

Abstract

We prove tight bounds of Theta(k log k) queries for non-adaptively testing whether a function f:{0,1}^n -> {0,1} is a k-parity or far from any k-parity. The lower bound combines a recent method of Blais, Brody and Matulef [BBM11] to get lower bounds for testing from communication complexity with an Omega(k \log k) lower bound for the one-way communication complexity of k-disjointness.

DOI: 10.48550/arxiv.1209.3849

Related papers

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

Xi Chen, Erik Waingarten, Jinyu Xie

We prove a lower bound of Ω(n1/3) for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function f:{0,1}n→ {0,1} is monotone versus far from monotone. This improves the recent lower bound of Ω(n1/4) for the same problem by Belovs and Blais (STOC'16). Our result builds on a new family of random Boolean functions that can be viewed as a two-level extension of Talagrand's random DNFs.

arXiv:1702.06997ACM Symposium on Theory of Computing (STOC)Jun 15, 201742 citations

Weak Parity

Scott Aaronson, Andris Ambainis, Kaspars Balodis +1 more

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.

arXiv:1312.0036Nov 29, 20130 citations

Multiparty Communication Complexity of Disjointness

Arkadev Chattopadhyay, Anil Ada

We obtain a lower bound of n^Omega(1) on the k-party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication when k is a constant. For k=o(loglog n), the bounds remain super-polylogarithmic i.e. (log n)^omega(1). The previous best lower bound for three players until recently was Omega(log n). Our bound separates the communication complexity classes NP^{CC}_k and BPP^{CC}_k for k=o(loglog n). Furthermore, by the results of Beame, Pitassi and Segerlind \cite{BPS07}, our bound implies proof size lower bounds for tree-like, degree k-1 threshold systems and superpolynomial size lower bounds for Lovasz-Schrijver proofs. Sherstov \cite{She07b} recently developed a novel technique to obtain lower bounds on two-party communication using the approximate polynomial degree of boolean functions. We obtain our results by extending his technique to the multi-party setting using ideas from Chattopadhyay \cite{Cha07}. A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.

arXiv:0801.3624Jan 23, 200863 citations

Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

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).

Leibniz international proceedings in informaticsJan 1, 20212 citations

Query Complexity: Cryptography, Property Testing, and Lower Bounds Across Models

Weiqiang Yuan

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.

Jan 1, 20260 citations

The Unbounded-Error Communication Complexity of Symmetric Functions

Alexander A. Sherstov

We prove an essentially tight lower bound on the unbounded-error communication complexity of every symmetric function, i.e., f(x,y)=D(|x∧y|), where D: {0,1,…,n}→{0,1} is a given predicate and x,y range over {0,1} n . Specifically, we show that the communication complexity of f is between Θ(k/log5 n) and Θ(k logn), where k is the number of value changes of D in {0,1,…, n}. Prior to this work, the problem was solved only for the parity predicate D (Forster 2001). Our proof is built around two new ideas. First, we show that a predicate D gives rise to a rapidly mixing random walk on ℤ 2 , which allows us to reduce the problem to communication lower bounds for “typical” predicates. Second, we use Paturi’s approximation lower bounds (1992), suitably generalized here to clusters of real nodes in [0,n] and interpreted in their dual form, to prove that a typical predicate behaves analogous to the parity predicate with respect to a smooth distribution on the inputs.

COMBINATORICAOct 1, 200837 citations