the maximum threshold degree of a function of the form $f(x)\wedge g(x),$ where $f,g\colon\zoon\to\moo$ are halfspaces. Then $$\begin{aligned}
D(n) = \Theta(n).\end{aligned}$$

To be more precise, we give a randomized algorithm which with probability at least constructs two halfspaces on $\zoon$ whose intersection has threshold degree $\Theta(n).$ In Section \[sec:main\], we develop several refinements of Theorem \[thm:main\]. For example, we show that the intersection of two halfspaces on $\zoon$ requires a perceptron with $\exp\{\Theta(n)\}$ monomials, i.e., does not have a sparse sign-representation. We also give an essentially tight lower bound on the threshold degree of the intersection of a halfspace and a majority function, improving quadratically on the previous bound in [@sherstov09hshs].

In summary, unlike DNF formulas and read-once Boolean formulas, the intersection of two halfspaces does not admit a nontrivial sign-representation. Apart from computational learning theory, lower bounds on the threshold degree have played a key role in several works on circuit complexity [@paturi-saks94rational; @siu-roy-kailath94rational; @krause94depth2mod; @KP98threshold; @sherstov07ac-majmaj], Turing complexity classes [@aspnes91voting; @beigel91rational; @beigel94perceptrons], and communication complexity [@sherstov07ac-majmaj; @sherstov07quantum; @sherstov07symm-sign-rank; @RS07dc-dnf]. For this reason, we consider Theorem \[thm:main\] and the techniques used to obtain it to be of interest outside of computational learning.

Theorem \[thm:main\] and much previous work suggest 