Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
From MaRDI portal
Publication:5891428
DOI10.1145/1806689.1806762zbMath1293.68155arXiv0910.4224MaRDI QIDQ5891428
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
PAC learning; halfspaces; intersections of halfspaces; sign-representing; polynomial representations of Boolean functions
68Q32: Computational learning theory
68T05: Learning and adaptive systems in artificial intelligence
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, Breaking the Minsky--Papert Barrier for Constant-Depth Circuits, The Power of Asymmetry in Constant-Depth Circuits, Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits, Unnamed Item, Unnamed Item, Unnamed Item, Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$, Approximate Degree in Classical and Quantum Computing, Fooling Polytopes, A Short List of Equalities Induces Large Sign-Rank, A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$, Sign rank vs discrepancy, The hardest halfspace, Unnamed Item, Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
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
