Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-160 | 12th September 2018 09:29

Cubic Formula Size Lower Bounds Based on Compositions with Majority


Authors: Anna Gal, Avishay Tal, Adrian Trejo Nuñez
Publication: 12th September 2018 09:30
Downloads: 1967


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 majority function (or its negation) on the middle slices of the Boolean cube, as well as iterated compositions of such functions.
As a consequence, we obtain $n^{3}/polylog(n)$ lower bounds on the (non-monotone) formula size of an explicit monotone function by combining the monotone address function with the majority function. To the best of our knowledge, previously, super-quadratic formula size lower bounds for explicit functions have been obtained only for non-monotone functions.

ISSN 1433-8092 | Imprint