ECCC-Report TR12-174https://eccc.weizmann.ac.il/report/2012/174Comments and Revisions published for TR12-174en-usTue, 03 Sep 2013 10:30:05 +0300
Revision 1
| On the Noise Stability of Small De Morgan Formulas |
Anat Ganor,
Ilan Komargodski,
Ran Raz,
Troy Lee
https://eccc.weizmann.ac.il/report/2012/174#revision1We 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.
Tue, 03 Sep 2013 10:30:05 +0300https://eccc.weizmann.ac.il/report/2012/174#revision1
Paper TR12-174
| The Spectrum of Small DeMorgan Formulas |
Anat Ganor,
Ilan Komargodski,
Ran Raz
https://eccc.weizmann.ac.il/report/2012/174We 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.Wed, 12 Dec 2012 15:52:18 +0200https://eccc.weizmann.ac.il/report/2012/174