The intersection of two halfspaces has high threshold degree

DOI10.1137/100785260MaRDI QIDQ5408769zbMATH OpenOpenAlexFDO

Authors Alexander A. Sherstov

Publication date 11 April 2014

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

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

zbMATH Keywords

rational approximationPAC learningintersections of halfspacesdirect sum theoremspolynomial representations of Boolean functions

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: The threshold degree of a Boolean function f:{0,1}^n->{-1,+1} is the least degree of a real polynomial p such that f(x)=sgn p(x). We construct two halfspaces on {0,1}^n whose intersection has threshold degree Theta(sqrt n), an exponential improvement on previous lower bounds. This solves an open problem due to Klivans (2002) and rules out the use of perceptron-based techniques for PAC learning the intersection of two halfspaces, a central unresolved challenge in computational learning. We also prove that the intersection of two majority functions has threshold degree Omega(log n), which is tight and settles a conjecture of O'Donnell and Servedio (2003). Our proof consists of two parts. First, we show that for any nonconstant Boolean functions f and g, the intersection f(x)^g(y) has threshold degree O(d) if and only if ||f-F||_infty + ||g-G||_infty < 1 for some rational functions F, G of degree O(d). Second, we settle the least degree required for approximating a halfspace and a majority function to any given accuracy by rational functions. Our technique further allows us to make progress on Aaronson's challenge (2008) and contribute strong direct product theorems for polynomial representations of composed Boolean functions of the form F(f_1,...,f_n). In particular, we give an improved lower bound on the approximate degree of the AND-OR tree.

Recommendations

• New degree bounds for polynomial threshold functions
• New degree bounds for polynomial threshold functions
• Learning intersections and thresholds of halfspaces

Cited in

(16)

• Separation of unbounded-error models in multi-party communication complexity
• The hardest halfspace
• Approximate degree and the complexity of depth three circuits
• The power of asymmetry in constant-depth circuits
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
• On XOR lemmas for the weight of polynomial threshold functions
• The large-error approximate degree of \(\mathrm{AC}^0\)
• Sign-rank can increase under intersection
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• The large-error approximate degree of \(\mathrm{AC}^0\)
• New degree bounds for polynomial threshold functions
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Lifting uniform learners via distributional decomposition
• Approximate Degree in Classical and Quantum Computing
• Fooling Polytopes

This page was built for publication: The intersection of two halfspaces has high threshold degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408769)