Approximating the AND-OR Tree

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 function V n i=1 W n j=1 xi j, known as the AND-OR tree, has approximate degree W(n). This lower bound is tight and closes a line of research on the problem, the best previous bound being W(n 0:75 ). More generally, we prove that the function V m=1 W n j=1 xi j has approximate degree W( p mn); which is tight. The same lower bound was obtained independently by Bun and Thaler (2013) using related techniques.

• Publication year

  2013

• Venue

  Theory of Computing

• Publication date

  2013-06-19

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4086/toc.2013.v009a020
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Dual lower bounds for approximate degree and Markov-Bernstein inequalities

  2013cited by this paper
• Making polynomials robust to noise

  2012cited by this paper
• The multiparty communication complexity of set disjointness

  2012cited by this paper
• Strong direct product theorems for quantum communication and query complexity

  2010cited by this paper
• A Separation of NP and coNP in Multiparty Communication Complexity

  2010cited by this paper
• Reflections for quantum query algorithms

  2010cited by this paper
• The Sign-Rank of AC0

  2010cited by this paper
• SeparatingAC0 from Depth-2 Majority Circuits

  2009cited by this paper
• BQP and the polynomial hierarchy

  2009cited by this paper
• The Pattern Matrix Method (Journal Version)

  2009cited by this paper
• The Intersection of Two Halfspaces Has High Threshold Degree

  2009cited by this paper
• The Polynomial Method in Quantum and Classical Computing

  2008cited by this paper
• Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions

  2008cited by this paper
• The Sign-rank of Ac

  2008cited by this paper
• A note on quantum algorithms and the minimal degree of ε-error polynomials for symmetric functions

  2008cited by this paper
• Electronic Colloquium on Computational Complexity, Report No. 57 (2008) Communication Lower Bounds Using Dual Polynomials ∗

  2008cited by this paper
• The Sign-Rank of AC^O

  2008cited by this paper
• On Computation and Communication with Small Bias

  2007cited by this paper
• Separating AC0 from depth-2 majority circuits

  2007cited by this paper
• Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer

  2007cited by this paper
• Agnostically learning halfspaces

  2005cited by this paper
• Quantum lower bounds for the collision and the element distinctness problems

  2004cited by this paper
• Quantum and classical strong direct product theorems and optimal time-space tradeoffs

  2004cited by this paper
• Learning DNF in time 2Õ(n1/3)

  2004cited by this paper
• New degree bounds for polynomial threshold functions

  2003cited by this paper
• Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range

  2003cited by this paper
• Quantum Search on Bounded-Error Inputs

  2003cited by this paper
• Complexity measures and decision tree complexity: a survey

  2002cited by this paper
• Approximating linear restrictions of Boolean functions

  2002cited by this paper
• Quantum communication complexity of symmetric predicates

  2002cited by this paper
• Learning DNF in time 2 Õ(n 1/3 ) .

  2001cited by this paper
• Quantum lower bounds for the collision and the element distinctness problems

  2001cited by this paper
• Bounds for small-error and zero-error quantum algorithms

  1999cited by this paper
• Communication complexity lower bounds by polynomials

  1999cited by this paper
• Learning DNF by approximating inclusion-exclusion formulae

  1999cited by this paper
• Quantum lower bounds by polynomials

  1998cited by this paper
• Computing Boolean functions by polynomials and threshold circuits

  1998cited by this paper
• Inclusion-exclusion: Exact and approximate

  1996cited by this paper
• Approximating Threshold Circuits by Rational Functions

  1994cited by this paper
• Rational approximation techniques for analysis of neural networks

  1994cited by this paper
• On the computational power of depth 2 circuits with threshold and modulo gates

  1994cited by this paper
• The polynomial method in circuit complexity

  1993cited by this paper
• Slicing the hypercube

  1993cited by this paper
• Perceptrons, PP, and the polynomial hierarchy

  1992cited by this paper
• On the degree of boolean functions as real polynomials

  1992cited by this paper
• The expressive power of voting polynomials

  1991cited by this paper
• Approximate Inclusion-Exclusion

  1990cited by this paper
• Review: Marvin Minsky and Seymour Papert, Perceptrons, An Introduction to Computational Geometry

  1972cited by this paper
• Threshold logic and its applications

  1971cited by this paper
• Perceptrons: An Introduction to Computational Geometry

  1969cited by this paper

• Approximate Degree Composition for Recursive Functions

  2024influential citation
• A Direct Reduction from the Polynomial to the Adversary Method

  2023cites this paper
• On the Composition of Randomized Query Complexity and Approximate Degree

  2023cites this paper
• Approximate Degree, Weight, and Indistinguishability

  2022cites this paper
• The approximate degree of DNF and CNF formulas

  2022cites this paper
• Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring

  2022cites this paper
• Research Statement

  2021cites this paper
• Bounded Indistinguishability for Simple Sources

  2021cites this paper
• One-way communication complexity and non-adaptive decision trees

  2021cites this paper
• Guest Column

  2020cites this paper
• Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem

  2020cites this paper
• Semidefinite programming formulations for the completely bounded norm of a tensor

  2019cites this paper
• Approximate degree, secret sharing, and concentration phenomena

  2019cites this paper
• Lower Bounding the AND-OR Tree via Symmetrization

  2019influential citation
• Classical Lower Bounds from Quantum Upper Bounds

  2018influential citation
• A Nearly Optimal Lower Bound on the Approximate Degree of AC^0

  2017cites this paper
• The polynomial method strikes back: tight quantum query bounds via dual polynomials

  2017influential citation
• A Composition Theorem for Randomized Query Complexity

  2017cites this paper
• Approximate Degree and the Complexity of Depth Three Circuits

  2016cites this paper
• A Composition Theorem for Conical Juntas

  2016cites this paper
• Dual Polynomials for Collision and Element Distinctness

  2015cites this paper
• Quantum Computing: Lecture Notes

  2015cites this paper
• The Power of Asymmetry in Constant-Depth Circuits

  2015cites this paper
• Separations in query complexity using cheat sheets

  2015cites this paper
• Approximate Degree of ANDOR trees

  2014cites this paper
• Applications of Adversary Method in Quantum Query Algorithms

  2014cites this paper
• Breaking the minsky-papert barrier for constant-depth circuits

  2014cites this paper
• Distribution-independent Reliable Learning

  2014influential citation
• Lower Bounds for the Approximate Degree of Block-Composed Functions

  2014influential citation
• Hardness Amplification and the Approximate Degree of Constant-Depth Circuits

  2013influential citation
• Dual lower bounds for approximate degree and Markov-Bernstein inequalities

  2013influential citation