Thursday, October 23, 2014 - 2:30pm to 3:30pm

Location:

32-G575

Speaker:

Avishai Tal

Biography:

Weizmann Institute

Seminar group:

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*:{*n*→{0,1}*x*1*x**n**p**O*(*p*2

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.