Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KHRAPCHENKO:
Reports tagged with Khrapchenko:
TR12-174 | 12th December 2012
Anat Ganor, Ilan Komargodski, Ran Raz

#### The Spectrum of Small DeMorgan Formulas

Revisions: 1

We 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 ... more >>>

TR20-180 | 2nd December 2020
Yuval Filmus, Or Meir, Avishay Tal

#### Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathbf{AC}^0$

Revisions: 2

Håstad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of $O(p^{2})$ under a random restriction that leaves each variable alive independently with probability $p$ [SICOMP, 1998]. Using this result, he gave an $\widetilde{\Omega}(n^{3})$ formula size lower bound for the Andreev function, ... more >>>

ISSN 1433-8092 | Imprint