[@valiant84pac] and extensively studied over the past two decades. The fastest known algorithm for PAC learning DNF formulas runs in time $\exp\{\tilde O(n^{1/3})\}$ and is due to Klivans and Servedio [@KS01dnf]. Specifically, the authors of [@KS01dnf] prove an upper bound of $O(n^{1/3}\log n)$ on the threshold degree of polynomial-size DNF formulas, which essentially matches a classical lower bound of $\Omega(n^{1/3})$ due to Minsky and Papert [@minsky88perceptrons].

Another success story of the perceptron-based approach is the concept class of Boolean formulas, i.e., Boolean circuits with fan-out $1$ at every gate. O’Donnell and Servedio [@odonnell03degree] proved an upper bound of $\sqrt s\log^{O(d)} s$ on the threshold degree of Boolean formulas of size $s$ and depth $d,$ giving the first subexponential algorithm for a family of formulas of superconstant depth. This upper bound on the threshold degree was improved to $s^{0.5+o(1)}$ for any depth $d$ by Ambainis et al. [@ACRSZ07nand], building on a quantum query algorithm of Farhi et al. [@FGG08nand]. More recently, Lee [@lee09formulas] sharpened the upper bound to $O(\sqrt s),$ which is tight. This line of research gives the fastest known algorithm for PAC learning Boolean formulas.

Another extensively studied problem in computational learning theory, and the subject of this paper, 