The Taub Faculty of Computer Science Events and Talks

We 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: \{0,1\}^n \to \{0,1\}$, setting each variable out of $x_1, ..., 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 Hastad [SIAM J. C., 1998] by removing logarithmic factors.

As a consequence of our results, we strengthen the best formula size lower bounds for functions in P.

The proof mainly uses discrete Fourier analysis, and relies on a result from quantum query complexity by Laplante et al. [CC, 2006], Hoyer et al. [STOC, 2007] and Reichardt [SODA, 2011].

No prior knowledge about quantum computing is assumed.