__
TR10-025 | 24th February 2010 23:05
__

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

**Abstract:**
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.