ECCC-Report TR10-025https://eccc.weizmann.ac.il/report/2010/025Comments and Revisions published for TR10-025en-usThu, 25 Feb 2010 02:07:10 +0200
Paper TR10-025
| Optimal bounds for sign-representing the intersection of two halfspaces by polynomials |
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2010/025The 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.Thu, 25 Feb 2010 02:07:10 +0200https://eccc.weizmann.ac.il/report/2010/025