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

arXiv:1907.06731 · ACM Transactions on Computation Theory

Lower Bounding the AND-OR Tree via Symmetrization

William Kretschmer

Published Jan 21, 2021• 2 citations
arXivHTMLPDF

Abstract

We prove a simple, nearly tight lower bound on the approximate degree of the two-level AND-OR tree using symmetrization arguments. Specifically, we show that ˜ deg(AND m ˆ OR n ) = ˜ Ω(√ mn ). We prove this lower bound via reduction to the OR function through a series of symmetrization steps, in contrast to most other proofs that involve formulating approximate degree as a linear program [6, 10, 21]. Our proof also demonstrates the power of a symmetrization technique involving Laurent polynomials (polynomials with negative exponents) that was previously introduced by Aaronson et al. [2].

DOI
10.1145/3434385

Related papers

Approximate Degree, Weight, and Indistinguishability

Xuangui Huang, Emanuele Viola

We prove that the OR function on {-1,1\} n can be pointwise approximated with error ε by a polynomial of degree O ( k ) and weight 2 O ( n log (1/ε)/k) , for any k ≥ √ n log (1/ε). This result is tight for any k ≤ (1-Ω (1)) n . Previous results were either not tight or had ε = Ω (1). In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width CNF. For these two classes no such result was known. We prove that the \( \mathsf {OR} \) function on \( \lbrace -1,1\rbrace ^n \) can be pointwise approximated with error \( \epsilon \) by a polynomial of degree \( O(k) \) and weight \( 2^{O(n \log (1/\epsilon) /k)} \) , for any \( k \ge \sqrt {n \log (1/\epsilon)} \) . This result is tight for any \( k \le (1-\Omega (1))n \) . Previous results were either not tight or had \( \epsilon = \Omega (1) \) . In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width \( \mathsf {CNF} \) . For these two classes no such result was known. One motivation for such results comes from the study of indistinguishability. Two distributions \( P \) , \( Q \) over \( n \) -bit strings are \( (k,\delta) \) -indistinguishable if their projections on any \( k \) bits have statistical distance at most \( \delta \) . The above approximations give values of \( (k,\delta) \) that suffice to fool \( \mathsf {OR} \) , symmetric functions, and bounded-width \( \mathsf {CNF} \) , and the first result is tight for all \( k \) while the second result is tight for \( k \le (1-\Omega (1))n \) . We also show that any two \( (k, \delta) \) -indistinguishable distributions are \( O(n^{k/2}\delta) \) -close to two distributions that are \( (k,0) \) -indistinguishable, improving the previous bound of \( O(n)^k \delta \) . Finally, we present proofs of some known approximate degree lower bounds in the language of indistinguishability, which we find more intuitive.

ACM Transactions on Computation Theory•Mar 4, 2022•4 citations

Approximating the AND-OR Tree.

Alexander A. Sherstov

ABSTRACT. The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f within 1=3 at every point. We prove that the functionVn iD1 Wn jD1 xij, known as the AND-OR tree, has approximate degree˝.n/: This lower bound is tight and closes a line of research on the problem, the best previous bound being ˝.n0:75/. More generally, we prove that the function

Electronic colloquium on computational complexity•Jan 1, 2013•5 citations

A Nearly Optimal Lower Bound on the Approximate Degree of AC^0

Mark Bun, Justin Thaler

The approximate degree of a Boolean function f : {-1, 1}n→ {-1, 1} is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function f with approximate degree d into a function F on O(n · polylog(n)) variables with approximate degree at least D = Ω(n1/3· d2/3). In particular, if d = n1-Ω(1), then D is polynomially larger than d. Moreover, if f is computed by a constant-depth polynomial-size Boolean circuit, then so is F. By recursively applying our transformation, for any constant δ > 0 we exhibit an AC0function of approximate degree Ω(n1-δ). This improves over the best previous lower bound of Ω(n2/3) due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of n that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: · For any constant δ > 0, an Ω(n1-δ) lower bound on the quantum communication complexity of a function in AC0. · A Boolean function f with approximate degree at least C(f)2-o(1), where C(f) is the certificate complexity of f. This separation is optimal up to the o(1) term in the exponent. · Improved secret sharing schemes with reconstruction procedures in AC0.

Annual Symposium on Foundations of Computer Science•Oct 1, 2017•26 citations

Approximate Degree in Classical and Quantum Computing

Mark Bun, Justin Thaler

The approximate degree of a Boolean function f captures how well f can be approximated pointwise by low-degree polynomials. This monograph surveys what is known about approximate degree and illustrates its applications in theoretical computer science. A particular focus of the survey is a method of proving lower bounds via objects called dual polynomials. These represent a reformulation of approximate degree using linear programming duality. We discuss in detail a recent, powerful technique for constructing dual polynomials, called “dual block composition”.

Foundations and Trends® in Theoretical Computer Science•Dec 30, 2022•11 citations

A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function $f$ with approximate degree $d$ into a function $F$ on $O(n \cdot \mathrm{polylog}(n))$ variables with approximate degree at least $D = \Omega(n^{1/3} \cdot d^{2/3})$. In particular, if $d= n^{1-\Omega(1)}$, then $D$ is polynomially larger than $d$. Moreover, if $f$ is computed by a polynomial-size Boolean circuit of constant depth, then so is $F$. By recursively applying our transformation, for any constant $\delta > 0$ we exhibit an AC$^0$ function of approximate degree $\Omega(n^{1-\delta})$. This improves upon the best previous lower bound of $\Omega(n^{2/3})$ due to Aaronson and Shi [ J. ACM, 51 (2004), pp. 595--605] and nearly matches the trivial upper bound of $n$ that holds for any function. Our lower bounds also apply to (quasipolynomial-size) disjunctive normal forms of polylogarithmic width. We describe several applications of these results and provide the following: (i) for any constant $\delta > 0$, an $\Omega(n^{1-\delta})$ lower bound on the quantum communication complexity of a function in AC$^0$; (ii) a Boolean function $f$ with approximate degree at least $C(f)^{2-o(1)}$, where $C(f)$ is the certificate complexity of $f$; this separation is optimal up to the $o(1)$ term in the exponent; (iii) improved secret sharing schemes with reconstruction procedures in AC$^0$.

arXiv:1703.05784•SIAM Journal on Computing•Oct 22, 2019•18 citations

Classical lower bounds from quantum upper bounds

Shalev Ben-David, Adam Bouland, Ankit Garg +1 more

We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt{n}) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma_2 norm) of F: X x Y -> {0,1} grows by a factor of Omega~(sqrt{n}) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrt{n}) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.

arXiv:1807.06256•Jul 17, 2018•2 citations
We prove a simple, nearly tight lower bound on the approximate degree of the two-level AND-OR tree using symmetrization arguments. Specifically, we show that ˜ deg(AND m ˆ OR n ) = ˜ Ω(√ mn ). We prove this lower bound via reduction to the OR function through a series of symmetrization steps, in contrast to most other proofs that involve formulating approximate degree as a linear program [6, 10, 21]. Our proof also demonstrates the power of a symmetrization technique involving Laurent polynomials (polynomials with negative exponents) that was previously introduced by Aaronson et al. [2].
We prove that the OR function on {-1,1\} n can be pointwise approximated with error ε by a polynomial of degree O ( k ) and weight 2 O ( n log (1/ε)/k) , for any k ≥ √ n log (1/ε). This result is tight for any k ≤ (1-Ω (1)) n . Previous results were either not tight or had ε = Ω (1). In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width CNF. For these two classes no such result was known. We prove that the OR \mathsf {OR} OR function on {−1,1}n \lbrace -1,1\rbrace ^n {−1,1}n can be pointwise approximated with error ϵ \epsilon ϵ by a polynomial of degree O(k) O(k) O(k) and weight 2O(nlog⁡(1/ϵ)/k) 2^{O(n \log (1/\epsilon) /k)} 2O(nlog(1/ϵ)/k) , for any k≥nlog⁡(1/ϵ) k \ge \sqrt {n \log (1/\epsilon)} k≥nlog(1/ϵ)​ . This result is tight for any k≤(1−Ω(1))n k \le (1-\Omega (1))n k≤(1−Ω(1))n . Previous results were either not tight or had ϵ=Ω(1) \epsilon = \Omega (1) ϵ=Ω(1) . In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width CNF \mathsf {CNF} CNF . For these two classes no such result was known. One motivation for such results comes from the study of indistinguishability. Two distributions P P P , Q Q Q over n n n -bit strings are (k,δ) (k,\delta) (k,δ) -indistinguishable if their projections on any k k k bits have statistical distance at most δ \delta δ . The above approximations give values of (k,δ) (k,\delta) (k,δ) that suffice to fool OR \mathsf {OR} OR , symmetric functions, and bounded-width CNF \mathsf {CNF} CNF , and the first result is tight for all k k k while the second result is tight for k≤(1−Ω(1))n k \le (1-\Omega (1))n k≤(1−Ω(1))n . We also show that any two (k,δ) (k, \delta) (k,δ) -indistinguishable distributions are O(nk/2δ) O(n^{k/2}\delta) O(nk/2δ) -close to two distributions that are (k,0) (k,0) (k,0) -indistinguishable, improving the previous bound of O(n)kδ O(n)^k \delta O(n)kδ . Finally, we present proofs of some known approximate degree lower bounds in the language of indistinguishability, which we find more intuitive.
The approximate degree of a Boolean function f : {-1, 1}n→ {-1, 1} is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function f with approximate degree d into a function F on O(n · polylog(n)) variables with approximate degree at least D = Ω(n1/3· d2/3). In particular, if d = n1-Ω(1), then D is polynomially larger than d. Moreover, if f is computed by a constant-depth polynomial-size Boolean circuit, then so is F. By recursively applying our transformation, for any constant δ > 0 we exhibit an AC0function of approximate degree Ω(n1-δ). This improves over the best previous lower bound of Ω(n2/3) due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of n that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: · For any constant δ > 0, an Ω(n1-δ) lower bound on the quantum communication complexity of a function in AC0. · A Boolean function f with approximate degree at least C(f)2-o(1), where C(f) is the certificate complexity of f. This separation is optimal up to the o(1) term in the exponent. · Improved secret sharing schemes with reconstruction procedures in AC0.
The approximate degree of a Boolean function f captures how well f can be approximated pointwise by low-degree polynomials. This monograph surveys what is known about approximate degree and illustrates its applications in theoretical computer science. A particular focus of the survey is a method of proving lower bounds via objects called dual polynomials. These represent a reformulation of approximate degree using linear programming duality. We discuss in detail a recent, powerful technique for constructing dual polynomials, called “dual block composition”.
A Nearly Optimal Lower Bound on the Approximate Degree of AC0^00
The approximate degree of a Boolean function f ⁣:{−1,1}n→{−1,1}f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}f:{−1,1}n→{−1,1} is the least degree of a real polynomial that approximates fff pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function fff with approximate degree ddd into a function FFF on O(n⋅polylog(n))O(n \cdot \mathrm{polylog}(n))O(n⋅polylog(n)) variables with approximate degree at least D=Ω(n1/3⋅d2/3)D = \Omega(n^{1/3} \cdot d^{2/3})D=Ω(n1/3⋅d2/3). In particular, if d=n1−Ω(1)d= n^{1-\Omega(1)}d=n1−Ω(1), then DDD is polynomially larger than ddd. Moreover, if fff is computed by a polynomial-size Boolean circuit of constant depth, then so is FFF. By recursively applying our transformation, for any constant δ>0\delta > 0δ>0 we exhibit an AC0^00 function of approximate degree Ω(n1−δ)\Omega(n^{1-\delta})Ω(n1−δ). This improves upon the best previous lower bound of Ω(n2/3)\Omega(n^{2/3})Ω(n2/3) due to Aaronson and Shi [ J. ACM, 51 (2004), pp. 595--605] and nearly matches the trivial upper bound of nnn that holds for any function. Our lower bounds also apply to (quasipolynomial-size) disjunctive normal forms of polylogarithmic width. We describe several applications of these results and provide the following: (i) for any constant δ>0\delta > 0δ>0, an Ω(n1−δ)\Omega(n^{1-\delta})Ω(n1−δ) lower bound on the quantum communication complexity of a function in AC0^00; (ii) a Boolean function fff with approximate degree at least C(f)2−o(1)C(f)^{2-o(1)}C(f)2−o(1), where C(f)C(f)C(f) is the certificate complexity of fff; this separation is optimal up to the o(1)o(1)o(1) term in the exponent; (iii) improved secret sharing schemes with reconstruction procedures in AC0^00.
We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt{n}) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma_2 norm) of F: X x Y -> {0,1} grows by a factor of Omega~(sqrt{n}) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrt{n}) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.