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

الأصل · EN

The threshold degree of a function f:0,1ⁿ->-1,+1 is the least degree of a real polynomial p with f(x)=sgn p(x). We prove that the intersection of two halfspaces on 0,1ⁿ has threshold degree Omega(n), which matches the trivial upper bound and completely answers a question due to Klivans (2002). The best previous lower bound was Omega(sqrt n). Our result shows that the intersection of two halfspaces on 0,1ⁿ only admits a trivial 2Theta(n)-time learning algorithm based on sign-representation by polynomials, unlike the advances achieved in PAC learning DNF formulas and read-once Boolean formulas. The proof introduces a new technique of independent interest, based on Fourier analysis and matrix theory.