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

DOI10.1137/17M1161737zbMath1471.68092arXiv1703.05784OpenAlexW2981639918MaRDI QIDQ5117375

Justin Thaler, Mark Bun

Publication date: 25 August 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.05784

zbMATH Keywords

Boolean functionsecret-sharing schemeapproximate degreeconstant-depth circuitcertificate complexityquantum communication complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Authentication, digital signatures and secret sharing (94A62) Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11)

Related Items (4)

Approximate Degree in Classical and Quantum Computing ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Algorithmic Polynomials ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate inclusion-exclusion for arbitrary symmetric functions
• Disjointness is hard in the multiparty number-on-the-forehead model
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• On the degree of Boolean functions as real polynomials
• Perceptrons, PP, and the polynomial hierarchy
• Inclusion-exclusion: exact and approximate
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Dual lower bounds for approximate degree and Markov-Bernstein inequalities
• One-way functions and the nonisomorphism of NP-complete sets
• Bounded Indistinguishability and the Complexity of Recovering Secrets
• Faster Algorithms for Privately Releasing Marginals
• Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
• The Quantum Query Complexity of Read-Many Formulas
• Faster private release of marginals on small databases
• The Sign-Rank of AC$^0$
• Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
• The Pattern Matrix Method
• Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
• Quantum lower bounds for the collision and the element distinctness problems
• A Uniform Lower Bound on Weights of Perceptrons
• Agnostically Learning Halfspaces
• Separating ${AC}^0$ from Depth-2 Majority Circuits
• Deterministic Communication vs. Partition Number
• Improved Bounds on the Sign-Rank of AC^0
• Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation
• Separations in Query Complexity Based on Pointer Functions
• Formula lower bounds via the quantum method
• The log-approximate-rank conjecture is false
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Algorithmic polynomials
• Breaking the minsky-papert barrier for constant-depth circuits
• Separations in query complexity using cheat sheets
• The Intersection of Two Halfspaces Has High Threshold Degree
• The multiparty communication complexity of set disjointness
• Quantum lower bounds by polynomials
• Communication lower bounds using directional derivatives
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
• Improved Separations between Nondeterministic and Randomized Multiparty Communication
• New degree bounds for polynomial threshold functions

This page was built for publication: A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$