to the analysis in [@sherstov09hshs]. To prove that in fact $D(n)=\Theta(n),$ we pursue a rather different approach.

The intuition behind our work is as follows. Let $\alpha_1,\alpha_2,\dots,\alpha_n$ be given nonzero integers, and let $f\colon\zoon\to\moo$ be a given Boolean function such that $f(x)$ is completely determined by the sum $\sum \alpha_ix_i.$ When approximating $f$ pointwise by polynomials and rational functions of a given degree, can one restrict attention to those approximants that are, like $f,$ functions of the sum $\sum\alpha_ix_i$ alone rather than the individual bits $x_1,x_2,\dots,x_n$? If true, this claim would dramatically simplify the analysis of the threshold degree of $f$ by reducing it to a univariate question. Minsky and Papert [@minsky88perceptrons] showed that the claim is indeed true in the highly special case $\alpha_1=\alpha_2=\cdots=\alpha_n.$ For the purposes of this paper, however, the nonzero coefficients $\alpha_1,\alpha_2,\dots,\alpha_n$ must be of increasing orders of magnitude and in particular must satisfy $$\begin{aligned}
\max_{i,j} \ABS{\frac{\alpha_i}{\alpha_j}}>\exp\{\Omega(n)\}.\end{aligned}$$ Minsky and Papert’s argument breaks down completely in this setting, and with good reason: coefficients $\alpha_1,\dots,\alpha_n$ are easily constructed [@beigel94perceptrons] for which the passage to univariate approximation increases the degree requirement from $1$ to $n.$

To overcome this difficulty, we use techniques from Fourier analysis and matrix perturbation theory. 