Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > FORMULA LOWER BOUNDS:
Reports tagged with formula lower bounds:
TR18-160 | 12th September 2018
Anna Gal, Avishay Tal, Adrian Trejo Nuñez

#### Cubic Formula Size Lower Bounds Based on Compositions with Majority

We define new functions based on the Andreev function and prove that they require $n^{3}/polylog(n)$ formula size to compute. The functions we consider are generalizations of the Andreev function using compositions with the majority function. Our arguments apply to composing a hard function with any function that agrees with the ... 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: 3

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