Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-025 | 24th February 2010 23:05

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



The threshold degree of a function
$f\colon\{0,1\}^n\to\{-1,+1\}$ is the least degree of a
real polynomial $p$ with $f(x)\equiv\mathrm{sgn}\; p(x).$ We
prove that the intersection of two halfspaces on
$\{0,1\}^n$ 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\}^n$
only admits a trivial $2^{\Theta(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.

ISSN 1433-8092 | Imprint