ECCC-Report TR14-048https://eccc.weizmann.ac.il/report/2014/048Comments and Revisions published for TR14-048en-usTue, 19 Apr 2016 21:08:45 +0300
Revision 1
| Shrinkage of de Morgan Formulae by Spectral Techniques |
Avishay Tal
https://eccc.weizmann.ac.il/report/2014/048#revision1We give a new and improved proof that the shrinkage exponent of dDe Morgan formulae is $2$. Namely, we show that for any Boolean function $f: \{0,1\}^n \to \{0,1\}$, setting each variable out of $x_1, \ldots, x_n$ with probability $1-p$ to a randomly chosen constant, reduces the expected formula size of the function by a factor of $O(p^2)$. This result is tight and improves the work of H{\aa}stad [SIAM J. C., 1998] by removing logarithmic factors.
As a consequence of our results, the function defined by Andreev [MUMB., 1987], $A: \{0,1\}^n \to \{0,1\}$, which is in P, has formula size at least $\Omega(\frac{n^3}{\log^2 n \log\log n})$. This lower bound is tight (for the function $A$) up to the $\log\log n$ factor, and is the best known lower bound for functions in P.
In addition, we strengthen the average-case hardness result of Komargodski et al. [FOCS, 2013]; we show that the functions defined by Komargodski et al. , $h_r: \{0,1\}^n \to \{0,1\}$, which are also in P, cannot be computed correctly on a fraction greater than $1/2 + 2^{-r}$ of the inputs, by de Morgan formulae of size at most $\frac{n^3}{r^2 \mathrm{poly}\log n}$, for any parameter $r \le n^{1/3}$.
The proof relies on a result from quantum query complexity by Laplante et al. [CC, 2006], H{\o}yer et al. [STOC, 2007] and Reichardt [SODA, 2011]: for any Boolean function $f$, $Q_2(f) \le O(\sqrt{L(f)})$, where $Q_2(f)$ is the bounded-error quantum query complexity of $f$, and $L(f)$ is the minimal size de Morgan formula computing $f$.Tue, 19 Apr 2016 21:08:45 +0300https://eccc.weizmann.ac.il/report/2014/048#revision1
Paper TR14-048
| Shrinkage of De Morgan Formulae from Quantum Query Complexity |
Avishay Tal
https://eccc.weizmann.ac.il/report/2014/048We give a new and improved proof that the shrinkage exponent of De Morgan formulae is $2$. Namely, we show that for any Boolean function $f: \{-1,1\}^n \to \{-1,1\}$, setting each variable out of $x_1, \ldots, x_n$ with probability $1-p$ to a randomly chosen constant, reduces the expected formula size of the function by a factor of $O(p^2)$. This result is tight and improves the work of H{\aa}stad [SIAM J. C., 1998] by removing logarithmic factors.
As a consequence of our results, the function defined by Andreev [MUMB., 1987], $A: \{-1,1\}^n \to \{-1,1\}$, which is in P, has formula size at least $\Omega(\frac{n^3}{\log^2 n \log^3\log n})$. This lower bound is tight up to the $\log^3\log n$ factor, and is the best known lower bound for functions in P. In addition, the functions defined by Komargodski et al. [FOCS, 2013], $h_r: \{-1,1\}^n \to \{-1,1\}$, which are also in P, cannot be computed correctly on a fraction greater than $1/2 + 2^{-r}$ of the inputs, by De Morgan formulae of size at most $\frac{n^3}{r^2 \mathrm{poly}\log n}$, for any parameter $r \le n^{1/3}$.
The proof relies on a result from quantum query complexity by Laplante et al. [CC, 2006], H{\o}yer et al. [STOC, 2007] and Reichardt [SODA, 2011]: for any Boolean function $f$, $Q_2(f) \le O(\sqrt{L(f)})$, where $Q_2(f)$ is the bounded-error quantum query complexity of $f$, and $L(f)$ is the minimal size De Morgan formula computing $f$.Thu, 10 Apr 2014 17:19:02 +0300https://eccc.weizmann.ac.il/report/2014/048