Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

DOI10.1145/1806689.1806762zbMath1293.68155arXiv0910.4224OpenAlexW1963639340MaRDI QIDQ5891428

Alexander A. Sherstov

Publication date: 13 August 2014

Published in: Combinatorica, Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

PAC learninghalfspacesintersections of halfspacessign-representingpolynomial representations of Boolean functions

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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, Fooling Polytopes, The Power of Asymmetry in Constant-Depth Circuits, A Short List of Equalities Induces Large Sign-Rank, A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$, The hardest halfspace, Unnamed Item, Unnamed Item, Unnamed Item, Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$, Unnamed Item, Sign rank vs discrepancy, Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Learning intersections and thresholds of halfspaces
• On the computational power of depth-2 circuits with threshold and modulo gates
• PAC learning intersections of halfspaces with membership queries
• Computing Boolean functions by polynomials and threshold circuits
• The expressive power of voting polynomials
• Approximating threshold circuits by rational functions
• Perceptrons, PP, and the polynomial hierarchy
• Learning an intersection of a constant number of halfspaces over a uniform distribution
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• PP is closed under intersection
• The unbounded-error communication complexity of symmetric functions
• The complexity of properly learning simple concept classes
• Learning intersections of halfspaces with a margin
• An algorithmic theory of learning: Robust concepts and random projection
• Cryptographic hardness for learning intersections of halfspaces
• Rational approximation to \(|x|\)
• 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
• Baum’s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions
• Separating ${AC}^0$ from Depth-2 Majority Circuits
• A theory of the learnable
• On the Power of Threshold Circuits with Small Weights
• Rational approximation techniques for analysis of neural networks
• The Intersection of Two Halfspaces Has High Threshold Degree
• New degree bounds for polynomial threshold functions