Separating ${AC}^0$ from Depth-2 Majority Circuits
From MaRDI portal
Publication:3654371
DOI10.1137/08071421XzbMath1188.68149MaRDI QIDQ3654371
Publication date: 6 January 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ The Range of Topological Effects on Communication ⋮ 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 ⋮ The unbounded-error communication complexity of symmetric functions ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Unnamed Item ⋮ The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions ⋮ Algorithmic Polynomials ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ The hardest halfspace ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Simulation theorems via pseudo-random properties ⋮ Rectangles Are Nonnegative Juntas ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Communication Lower Bounds Using Directional Derivatives ⋮ Unnamed Item ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities ⋮ Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors
This page was built for publication: Separating ${AC}^0$ from Depth-2 Majority Circuits
