The threshold degree of a Boolean functionf:01n−1+1 is the least degree of a realpolynomial p such that f(x)sgnp(x) Weconstruct two halfspaces on 01n whose intersection hasthreshold degree (n) an exponential improvement onprevious lower bounds. This solves an open problem due to Klivans(2002) and rules out the use of perceptron-based techniques forPAC learning the intersection of two halfspaces, a centralunresolved challenge in computational learning. We also provethat the intersection of two majority functions has thresholddegree (logn) which is tight and settles a conjectureof O'Donnell and Servedio (2003).

Our proof consists of two parts. First, we show thatfor any nonconstant Boolean functions f and g theintersection f(x)g(y) has threshold degreeO(d) if and only if f−F+g−G1 for some rational functions F G of degreeO(d) Second, we settle the least degree required forapproximating a halfspace and a majority function toany given accuracy by rational functions.

Our technique further allows us to make progress onAaronson's challenge (2008) and contribute direct sumtheorems for polynomial representations of composed Boolean functionsof the form F(f1fn) In particular, we give an improvedlower bound on the approximate degree of the AND-OR tree