Theory Seminar: Shrinkage of De Morgan Formulae by Spectral Techniques

Speaker:
Avishay Tal (Weizmann Institute of Science)
Date:
Wednesday, 3.12.2014, 12:30
Place:
Taub 401

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.

Back to the index of events