The intersection of two halfspaces has high threshold degree

DOI10.1137/100785260zbMATH Open1350.68161arXiv0910.1862OpenAlexW1981115804MaRDI QIDQ5408769FDOQ5408769

Authors: Alexander A. Sherstov 

Publication date: 11 April 2014

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

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.

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

Recommendations

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

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)

Cited In (17)

• 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$
• The large-error approximate degree of \(\mathrm{AC}^0\)
• On XOR lemmas for the weight of polynomial threshold functions
• 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
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
• Lifting uniform learners via distributional decomposition
• Approximate Degree in Classical and Quantum Computing
• Fooling Polytopes
• Separation of unbounded-error models in multi-party communication complexity

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)