Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Symposium on Theory of Computing (STOC)

Restriction Trees for Sparsity and Applications

Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett

Published Jun 9, 2026• 0 citations
Publisher

Abstract

Exact and point-wise approximating representations of Boolean functions by real polynomials have been of great interest in the theory of computing. We focus on the study of sparsity of such representations. Our results include the following: First, we show that for every total Boolean function, its exact and approximate sparsity in the De Morgan basis are polynomially related to each other in the log scale, ignoring poly-log(n) factors. This answers an open question posed by Knop, Lovett, McGuire and Yuan (STOC 2021). It builds on and is analogous to the seminal result of Nisan and Szegedy (Computational Complexity 1994) who proved the same for degree and approximate degree. Second, we consider more powerful representations using generalized monomials, where each monomial is an indicator of a sub-cube. There are 3n such monomials, where n is the number of variables. We prove that even for these representations, the sparsity and approximate sparsity of total Boolean functions remain polynomially related to each other in the log scale, ignoring poly-log(n) factors. Third, we show that for every total Boolean function f, the log of its De Morgan sparsity characterizes up to polynomial loss and ignoring poly-log(n) factors, the quantum and classical 2-party bounded-error communication complexity of f ∘ EQ4, where EQ4 is Equality of two 2-bit strings, one held by Alice and the other by Bob. As a consequence, we show that bounded-error quantum protocols cannot exhibit super-polynomial cost advantage over their classical counterparts, for computing such functions.

DOI
10.1145/3798129.3800895

Related papers

Quantum-Classical Equivalence for AND-Functions

Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay +2 more

A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form $$ F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), $$ when the outer function $f$ is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function $f$, the bounded-error quantum and classical deterministic communication complexities of the function $f \circ \mathrm{AND}_2$ are polynomially related, up to polylogarithmic factors in $n$. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of $f$. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.

cs.CCCross-listedarXiv:2606.03249•Leibniz international proceedings in informatics•Jun 3, 2026•0 citations

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Scott Aaronson, Andris Ambainis, Jānis Iraids +2 more

We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries.

arXiv:1511.08682•Leibniz international proceedings in informatics•Nov 27, 2015•31 citations

Communication Lower Bounds Using Dual Polynomials

Alexander A. Sherstov

Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x_1,...,x_n) that approximates or sign-represents a given Boolean function f(x_1,...,x_n). This article surveys a new and growing body of work in communication complexity that centers around the dual objects, i.e., polynomials that certify the difficulty of approximating or sign-representing a given function. We provide a unified guide to the following results, complete with all the key proofs: (1) Sherstov's Degree/Discrepancy Theorem, which translates lower bounds on the threshold degree of a Boolean function into upper bounds on the discrepancy of a related function; (2) Two different methods for proving lower bounds on bounded-error communication based on the approximate degree: Sherstov's pattern matrix method and Shi and Zhu's block composition method; (3) Extension of the pattern matrix method to the multiparty model, obtained by Lee and Shraibman and by Chattopadhyay and Ada, and the resulting improved lower bounds for DISJOINTNESS; (4) David and Pitassi's separation of NP and BPP in multiparty communication complexity for k=(1-eps)log n players.

arXiv:0805.2135•Electronic colloquium on computational complexity•May 14, 2008•56 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 informatics•Jan 1, 2021•5 citations

Quantum lower bounds by polynomials

Robert Beals, Harry Buhrman, Richard Cleve +2 more

We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on {0,1} N in the black-box model. We show that the exponential quantum speed-up obtained for partial functions (i.e., problems involving a promise on the input) by Deutsch and Jozsa, Simon, and Shor cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with small error probability using T black-box queries, then there is a classical deterministic algorithm that computes f exactly with O ( Ts 6 ) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.

arXiv:quant-ph/9802049•Journal of the ACM•Jul 1, 2001•922 citations

On the Probabilistic Degree of an nnn-variate Boolean Function

Srikanth Srinivasan, S. Venkitesh

Nisan and Szegedy (CC 1994) showed that any Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ that depends on all its input variables, when represented as a real-valued multivariate polynomial $P(x_1,\ldots,x_n)$, has degree at least $\log n - O(\log \log n)$. This was improved to a tight $(\log n - O(1))$ bound by Chiarelli, Hatami and Saks (Combinatorica 2020). Similar statements are also known for other Boolean function complexity measures such as Sensitivity (Simon (FCT 1983)), Quantum query complexity, and Approximate degree (Ambainis and de Wolf (CC 2014)). In this paper, we address this question for \emph{Probabilistic degree}. The function $f$ has probabilistic degree at most $d$ if there is a random real-valued polynomial of degree at most $d$ that agrees with $f$ at each input with high probability. Our understanding of this complexity measure is significantly weaker than those above: for instance, we do not even know the probabilistic degree of the OR function, the best-known bounds put it between $(\log n)^{1/2-o(1)}$ and $O(\log n)$ (Beigel, Reingold, Spielman (STOC 1991); Tarui (TCS 1993); Harsha, Srinivasan (RSA 2019)). Here we can give a near-optimal understanding of the probabilistic degree of $n$-variate functions $f$, \emph{modulo} our lack of understanding of the probabilistic degree of OR. We show that if the probabilistic degree of OR is $(\log n)^c$, then the minimum possible probabilistic degree of such an $f$ is at least $(\log n)^{c/(c+1)-o(1)}$, and we show this is tight up to $(\log n)^{o(1)}$ factors.

arXiv:2107.03171•Leibniz international proceedings in informatics•Jan 1, 2021•0 citations
Exact and point-wise approximating representations of Boolean functions by real polynomials have been of great interest in the theory of computing. We focus on the study of sparsity of such representations. Our results include the following: First, we show that for every total Boolean function, its exact and approximate sparsity in the De Morgan basis are polynomially related to each other in the log scale, ignoring poly-log(n) factors. This answers an open question posed by Knop, Lovett, McGuire and Yuan (STOC 2021). It builds on and is analogous to the seminal result of Nisan and Szegedy (Computational Complexity 1994) who proved the same for degree and approximate degree. Second, we consider more powerful representations using generalized monomials, where each monomial is an indicator of a sub-cube. There are 3n such monomials, where n is the number of variables. We prove that even for these representations, the sparsity and approximate sparsity of total Boolean functions remain polynomially related to each other in the log scale, ignoring poly-log(n) factors. Third, we show that for every total Boolean function f, the log of its De Morgan sparsity characterizes up to polynomial loss and ignoring poly-log(n) factors, the quantum and classical 2-party bounded-error communication complexity of f ∘ EQ4, where EQ4 is Equality of two 2-bit strings, one held by Alice and the other by Bob. As a consequence, we show that bounded-error quantum protocols cannot exhibit super-polynomial cost advantage over their classical counterparts, for computing such functions.
A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form F(x,y)=f(x1∧y1,…,xn∧yn), F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), F(x,y)=f(x1​∧y1​,…,xn​∧yn​), when the outer function fff is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function fff, the bounded-error quantum and classical deterministic communication complexities of the function f∘AND2f \circ \mathrm{AND}_2f∘AND2​ are polynomially related, up to polylogarithmic factors in nnn. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of fff. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.
We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries.
Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x_1,...,x_n) that approximates or sign-represents a given Boolean function f(x_1,...,x_n). This article surveys a new and growing body of work in communication complexity that centers around the dual objects, i.e., polynomials that certify the difficulty of approximating or sign-representing a given function. We provide a unified guide to the following results, complete with all the key proofs: (1) Sherstov's Degree/Discrepancy Theorem, which translates lower bounds on the threshold degree of a Boolean function into upper bounds on the discrepancy of a related function; (2) Two different methods for proving lower bounds on bounded-error communication based on the approximate degree: Sherstov's pattern matrix method and Shi and Zhu's block composition method; (3) Extension of the pattern matrix method to the multiparty model, obtained by Lee and Shraibman and by Chattopadhyay and Ada, and the resulting improved lower bounds for DISJOINTNESS; (4) David and Pitassi's separation of NP and BPP in multiparty communication complexity for k=(1-eps)log n players.
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).
We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on {0,1} N in the black-box model. We show that the exponential quantum speed-up obtained for partial functions (i.e., problems involving a promise on the input) by Deutsch and Jozsa, Simon, and Shor cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with small error probability using T black-box queries, then there is a classical deterministic algorithm that computes f exactly with O ( Ts 6 ) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
Nisan and Szegedy (CC 1994) showed that any Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow \{0,1\}f:{0,1}n→{0,1} that depends on all its input variables, when represented as a real-valued multivariate polynomial P(x1,…,xn)P(x_1,\ldots,x_n)P(x1​,…,xn​), has degree at least log⁡n−O(log⁡log⁡n)\log n - O(\log \log n)logn−O(loglogn). This was improved to a tight (log⁡n−O(1))(\log n - O(1))(logn−O(1)) bound by Chiarelli, Hatami and Saks (Combinatorica 2020). Similar statements are also known for other Boolean function complexity measures such as Sensitivity (Simon (FCT 1983)), Quantum query complexity, and Approximate degree (Ambainis and de Wolf (CC 2014)). In this paper, we address this question for \emph{Probabilistic degree}. The function fff has probabilistic degree at most ddd if there is a random real-valued polynomial of degree at most ddd that agrees with fff at each input with high probability. Our understanding of this complexity measure is significantly weaker than those above: for instance, we do not even know the probabilistic degree of the OR function, the best-known bounds put it between (log⁡n)1/2−o(1)(\log n)^{1/2-o(1)}(logn)1/2−o(1) and O(log⁡n)O(\log n)O(logn) (Beigel, Reingold, Spielman (STOC 1991); Tarui (TCS 1993); Harsha, Srinivasan (RSA 2019)). Here we can give a near-optimal understanding of the probabilistic degree of nnn-variate functions fff, \emph{modulo} our lack of understanding of the probabilistic degree of OR. We show that if the probabilistic degree of OR is (log⁡n)c(\log n)^c(logn)c, then the minimum possible probabilistic degree of such an fff is at least (log⁡n)c/(c+1)−o(1)(\log n)^{c/(c+1)-o(1)}(logn)c/(c+1)−o(1), and we show this is tight up to (log⁡n)o(1)(\log n)^{o(1)}(logn)o(1) factors.