We show a connection between the De Morgan formula size of a Boolean function $f:\{0,1\}^n\to\{0,1\}$ and the noise stability of the function. Specifically, we prove that for $0< p\leq 1/2$ it holds that
\[ \mathbf{NS}_{p}(f) \geq 1- 2p\sqrt{L(f)\cdot||f||^2\cdot(1-||f||^2)} \]
where $\mathbf{NS}_p(f)$ is the noise stability of $f$ with noise parameter $p$, $||f||$ is the $\mathcal L_2$ norm of $f$, and $L(f)$ is the De Morgan formula size of $f$. This result stems from a generalization of Khrapchenko's bound, that might be of independent interest.

Our main result implies the following lower bound:
\[ \sum_{S\subseteq [n]} \delta^{|S|}\widehat f(S)^2 \geq ||f||^2-\frac{1-\delta}{2}\sqrt{L(f)||f||^2(1-||f||^2)} \]
for $0 \leq \delta \leq 1$, where $\widehat f(S)$ is the Fourier coefficient of $f$ at $S$. In particular, this bound implies a concentration result on the spectrum of Boolean functions that can be computed by small De Morgan formulas. Specifically, for any $\varepsilon>0$, we show that $\sum_{S\subseteq [n],|S| < k} \widehat{f}(S)^2 \geq ||f||^2\left(1-\varepsilon\right)$ where $k$ is roughly $\frac{1}{2\varepsilon}\sqrt{L(f)\frac{1-||f||^2}{||f||^2}}$. We observe that this concentration result also stems from a relation between the average sensitivity of $f$ and the original Khrapcheko bound.

In addition, we show that the De Morgan formula size in the results mentioned above can be replaced by the square of the non-negative quantum adversary bound, thus giving a (possibly) tighter bound.

We show a connection between the deMorgan formula size of a Boolean function and the noise stability of the function. Using this connection, we show that the Fourier spectrum of any balanced Boolean function computed by a deMorgan formula of size $s$ is concentrated on coefficients of degree up to $O(\sqrt s)$.

These results have several applications that apply to any function $f$ that can be computed by a deMorgan formula of size $s$. First, we get that $f$ can be approximated (in $\mathcal L_2$-norm) with constant error by a polynomial of degree $O(\sqrt s)$. Second, we show an upper bound of $O(\sqrt s)$ on the average sensitivity of $f$.

Our main result stems from a generalization of Khrapchenko's bound (Mat. Zametki, 1971), that might be of independent interest, and some Fourier analysis on the Boolean cube.

Previous works prove that any function $f:\{0,1\}^n\to\{0,1\}$ that can be computed by a deMorgan formula of size $s$, can be approximated point-wise by a polynomial of degree $O(s^{1/2+o(1)})$ with constant point-wise error. We note that this result can be easily extended to have a polynomial of degree $O(t\cdot s^{1/2+o(1)})$ that approximates $f$ with point wise error $2^{-t}$, for any $t > 0$. This was shown in a long line of results in quantum complexity.