that the nature of a PAC learning problem changes significantly when, instead of Valiant’s original arbitrary-distribution setting, one considers learning with respect to restricted distributions. For example, the uniform distribution on the sphere $\mathbb{S}^{n-1}$ or hypercube $\zoon$ allows the use of tools other than sign-representing polynomials, such as Fourier analysis. In particular, polynomial-time algorithms are known for the uniform-distribution learning of intersections of a constant number of halfspaces on the sphere [@blum-kannan97intersection-of-halfspaces; @Vempala:97] and hypercube [@KOS:02]. Furthermore, if membership queries are allowed, DNF formulas are known to be learnable in polynomial time with respect to the uniform distribution on the hypercube [@jackson94sieve].

Our Techniques {#our-techniques .unnumbered}
--------------

Let $f\wedge f$ denote the conjunction of two copies of a given Boolean function $f,$ each on an independent set of variables. It was shown in [@sherstov09hshs] that the threshold degree of $f\wedge f$ equals, up to a small multiplicative constant, the least degree of a rational function $R$ with $\|f-R\|_\infty\leq 1/3.$ With this characterization in hand, the equality $\degthr(f\wedge
f)=\Theta(\sqrt n)$ was derived in [@sherstov09hshs] by solving the rational approximation problem for the halfspace $$\begin{aligned}
f(x) = \sign{\left(1 +
\sum_{i=1}^{\sqrt n} \sum_{j=1}^{\sqrt n} 2^i x_{ij}\right)}.\end{aligned}$$ Unfortunately, the $\Theta(\sqrt n)$ barrier is fundamental 