Approximating the AND-OR tree

DOI10.4086/TOC.2013.V009A020MaRDI QIDQ3191590zbMATH OpenOpenAlexFDO

Authors Alexander A. Sherstov

Publication date 6 October 2014

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2013.v009a020

zbMATH Keywords

AND-OR treeapproximate degreepolynomial approximationpolynomial representations of Boolean functions

Mathematics Subject Classification ID

Boolean functions (06E30) Approximation by polynomials (41A10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Lower bounding the AND-OR tree via symmetrization
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Lower bounds for the approximate degree of block-composed functions

Cites work

• Reflections for quantum query algorithms
• The Intersection of Two Halfspaces Has High Threshold Degree

Cited in

(15)

• Finding optimal satisficing strategies for and-or trees
• Hardness amplification and the approximate degree of constant-depth circuits
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• The power of asymmetry in constant-depth circuits
• Approximate degree and the complexity of depth three circuits
• Approximate Degree in Classical and Quantum Computing
• Lower bounding the AND-OR tree via symmetrization
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• A composition theorem for randomized query complexity
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Approximate degree, weight, and indistinguishability
• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• A direct reduction from the polynomial to the adversary method
• Approximate degree composition for recursive functions
• The approximate degree of DNF and CNF formulas

This page was built for publication: Approximating the AND-OR tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3191590)