We give the first representation-independent hardness results for PAC learning intersections of halfspaces, a central concept class in computational learning theory. Our hardness results are derived from two public-key cryptosystems due to Regev, which are based on the worst-case hardness of well-studied lattice problems. Specifically, we prove that a polynomial-time ... more >>>

The threshold degree of a Boolean function $f\colon\{0,1\}\to\{-1,+1\}$ is the least degree of a real polynomial $p$ such $f(x)\equiv\mathrm{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 ... more >>>

Let $X$ be randomly chosen from $\{-1,1\}^n$, and let $Y$ be randomly chosen from the standard spherical Gaussian on $\R^n$. For any (possibly unbounded) polytope $P$ formed by the intersection of $k$ halfspaces, we prove that $$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k \cdot \Delta,$$ where $\Delta$ is ... more >>>

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 ... more >>>