Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$

DOI10.1137/20M1312459OpenAlexW3194100245MaRDI QIDQ4957911

Pei Wu, Alexander A. Sherstov

Publication date: 10 September 2021

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

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

zbMATH Keywords

communication complexityconstant-depth circuitssign-rankthreshold degreesign-representation by polynomialsunbounded-error communication

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)

Related Items (1)

A Short List of Equalities Induces Large Sign-Rank

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
• Probabilistic communication complexity
• Learning intersections and thresholds of halfspaces
• Communication complexity under product and nonproduct distributions
• Halfspace matrices
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On the computational power of depth-2 circuits with threshold and modulo gates
• Computing Boolean functions by polynomials and threshold circuits
• The expressive power of voting polynomials
• Approximating threshold circuits by rational functions
• On the degree of Boolean functions as real polynomials
• A linear lower bound on the unbounded error probabilistic communication complexity.
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• PP is closed under intersection
• Dual lower bounds for approximate degree and Markov-Bernstein inequalities
• The unbounded-error communication complexity of symmetric functions
• Extremal properties of polynomial threshold functions
• The Multiparty Communication Complexity of Set Disjointness
• Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
• The Sign-Rank of AC$^0$
• Extremal Combinatorics
• 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
• Separating ${AC}^0$ from Depth-2 Majority Circuits
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Rational approximation techniques for analysis of neural networks
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• The Power of Asymmetry in Constant-Depth Circuits
• Improved Bounds on the Sign-Rank of AC^0
• Communication Complexity
• Strong Direct Product Theorems for Quantum Communication and Query Complexity
• A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
• Algorithmic Polynomials
• The Intersection of Two Halfspaces Has High Threshold Degree
• Communication Lower Bounds Using Directional Derivatives
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
• New degree bounds for polynomial threshold functions

This page was built for publication: Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$