is the problem of learning *intersections of halfspaces*, i.e., conjunctions of functions of the form $f(x)=\sign(\sum \alpha_ix_i - \theta)$ for some reals $\alpha_1,\dots,\alpha_n,\theta.$ While solutions are known to several restrictions of this problem [@blum-kannan97intersection-of-halfspaces; @KwekPitt:98; @Vempala:97; @arriaga98proj; @KOS:02; @KlivansServedio:04coltmargin; @KLT09intersections-of-halfspaces], no algorithm has been discovered for PAC learning the intersection of even two halfspaces in time faster than $2^{\Theta(n)}.$ Progress on proving hardness results has also been scarce. Indeed, all known hardness results [@blum92trainingNN; @ABFKP:04; @focs06hardness; @khot-saket08hs-and-hs] either require polynomially many halfspaces or assume *proper* learning. In particular, we are not aware of any representation-independent hardness results for PAC learning the intersection of $O(1)$ halfspaces.

Our Results {#our-results .unnumbered}
-----------

Since the perceptron-based approach yields the fastest known algorithms for PAC learning DNF formulas and read-once Boolean formulas, it is natural to wonder whether it can yield any nontrivial results for the intersection of two halfspaces. Letting $D(n)$ stand for the maximum threshold degree over all intersections of two halfspaces on $\zoon,$ the question becomes whether $D(n)$ is a nontrivial (sublinear) function of the dimension $n.$ This question has been studied by several authors, as summarized in Table \[tab:history\]. Forty years ago, Minsky and Papert [@minsky88perceptrons] used a compactness argument 