Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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: 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