to show that $D(n)=\omega(1),$ the function in question being the intersection of two majorities on disjoint sets variables. O’Donnell and Servedio [@odonnell03degree] studied the same function using a rather different approach and thereby proved that $D(n)=\Omega(\log n/\log\log n).$ No nontrivial upper bounds on $D(n)$ being known, Klivans [@klivans-thesis §7] formally posed the problem of proving a lower bound substantially better than $\Omega(\log n)$ or an upper bound of $o(n).$

  *Result*                           *Reference*
  ---------------------------------- ------------------------
  $D(n)=\omega(1)$                   [@minsky88perceptrons]
  $D(n)=\Omega(\log n/\log\log n)$   [@odonnell03degree]
  $D(n)=\Omega(\sqrt n)$             [@sherstov09hshs]
  $D(n)=\Theta(n)$                   this paper

  : Lower bounds for the intersection of two halfspaces.[]{data-label="tab:history"}

It was recently shown in [@sherstov09hshs] that $D(n)=\Omega(\sqrt n),$ solving Klivans’ problem and ruling out an $n^{o(\sqrt n)}$-time PAC learning algorithm based on perceptrons. It is clear, however, that a PAC learning algorithm for the intersection of two halfspaces in time $n^{\Theta(\sqrt n)}$ would still be a breakthrough in computational learning theory, comparable to the advances in the study of DNF formulas and read-once Boolean formulas. The main contribution of this paper is to prove that $D(n)=\Omega(n),$ which matches the trivial upper bound and definitively rules out the perceptron-based approach for learning the intersection of two halfspaces in nontrivial time.

\[thm:main\] For $n=1,2,3,\dots,$ let $D(n)$ denote 