for which $f$ admits such a representation is called the *threshold degree* of $f,$ denoted $\degthr(f).$ In other words, $\degthr(f)$ is the least degree of a real polynomial that agrees with $f$ in sign. Perceptrons are appealing from a learning standpoint because they immediately lead to efficient learning algorithms. In more detail, let $f\colon\zoon\to\moo$ be an unknown function of threshold degree $d.$ Then by definition, $f$ has a representation of the form $$\begin{aligned}
f(x) \equiv \sign {\left(
\sum_{\substack{\abs{S}\leq d}}
^{\phantom{\abs{S}\leq d}}
\lambda_S \prod_{i\in S} x_i\right)} \end{aligned}$$ for some reals $\lambda_S$ and is thus a halfspace in $N={n\choose 0}+{n\choose 1}+\cdots+{n\choose d}$ dimensions. As a result, $f$ can be PAC learned in time polynomial in $N,$ using any of a variety of halfspace learning algorithms. (Throughout this paper, the term “PAC learning” refers to Valiant’s standard model [@valiant84pac] of learning under arbitrary distributions.)

The study of perceptrons dates back forty years to the seminal monograph of Minsky and Papert [@minsky88perceptrons], who examined the threshold degree of several common functions. Today, the perceptron-based approach yields the fastest known PAC learning algorithms for several concept classes. One such is the class of DNF formulas of polynomial size, posed a challenge in Valiant’s original paper 