Dual lower bounds for approximate degree and Markov-Bernstein inequalities

DOI10.1016/j.ic.2014.12.003zbMath1327.68117arXiv1302.6191OpenAlexW2138096767MaRDI QIDQ2347795

Justin Thaler, Mark Bun

Publication date: 9 June 2015

Published in: Information and Computation, Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Related Items

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits, Approximate Degree in Classical and Quantum Computing, Breaking the Minsky--Papert Barrier for Constant-Depth Circuits, Weighted Sobolev spaces: Markov-type inequalities and duality, The Power of Asymmetry in Constant-Depth Circuits, Unnamed Item, A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$, Unnamed Item, Approximate Degree, Secret Sharing, and Concentration Phenomena, Unnamed Item, Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$, Bounded Indistinguishability and the Complexity of Recovering Secrets, Unnamed Item, Lupaş-type inequality and applications to Markov-type inequalities in weighted Sobolev spaces, Unnamed Item, A Composition Theorem for Randomized Query Complexity, On separation between the degree of a Boolean function and the block sensitivity

Uses Software

• Wolfram Functions Site

Cites Work

• Approximate inclusion-exclusion for arbitrary symmetric functions
• Lower bounds for agnostic learning via approximate rank
• On the degree of Boolean functions as real polynomials
• Perceptrons, PP, and the polynomial hierarchy
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• 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
• Agnostically Learning Halfspaces
• Separating ${AC}^0$ from Depth-2 Majority Circuits
• Isometries on L p,1
• The Intersection of Two Halfspaces Has High Threshold Degree
• The multiparty communication complexity of set disjointness
• Making polynomials robust to noise
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Quantum lower bounds by polynomials
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item