Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
From MaRDI portal
Publication:3448791
DOI10.1007/978-3-662-47672-7_22zbMath1402.68083arXiv1311.1616OpenAlexW1776408431MaRDI QIDQ3448791
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.1616
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (13)
Approximate Degree in Classical and Quantum Computing ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Unnamed Item ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ On the Power of Statistical Zero Knowledge ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Learning $$AC^0$$ Under k-Dependent Distributions ⋮ Approximate Degree, Secret Sharing, and Concentration Phenomena ⋮ Unnamed Item ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities
Cites Work
- Reliable agnostic learning
- On the computational power of Boolean decision lists
- On the computational power of depth-2 circuits with threshold and modulo gates
- 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})}\)
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities
- 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
- Quantum lower bounds for the collision and the element distinctness problems
- Agnostically Learning Halfspaces
- Separating ${AC}^0$ from Depth-2 Majority Circuits
- Strong Direct Product Theorems for Quantum Communication and Query Complexity
- The Intersection of Two Halfspaces Has High Threshold Degree
- Breaking the minsky-papert barrier for constant-depth circuits
- The multiparty communication complexity of set disjointness
- Quantum lower bounds by polynomials
- Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
- New degree bounds for polynomial threshold functions
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Hardness Amplification and the Approximate Degree of Constant-Depth Circuits