Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR20-180 | 29th December 2020 17:13

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

RSS-Feed




Revision #2
Authors: Yuval Filmus, Or Meir, Avishay Tal
Accepted on: 29th December 2020 17:13
Downloads: 23
Keywords: 


Abstract:

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, which, up to lower order improvements, remains the state-of-the-art lower bound for any explicit function.

In this work, we extend the shrinkage result of Håstad to hold under a far wider family of random restrictions and their generalization — random projections. Based on our shrinkage results, we obtain an $\widetilde{\Omega}(n^{3})$ formula size lower bound for an explicit function computed in $\mathbf{AC}^0$. This improves upon the best known formula size lower bounds for $\mathbf{AC}^0$, that were only quadratic prior to our work. In addition, we prove that the KRW conjecture [Karchmer et al., Computational Complexity 5(3/4), 1995] holds for inner functions for which the unweighted quantum adversary bound is tight. In particular, this holds for inner functions with a tight Khrapchenko bound.

Our random projections are tailor-made to the function's structure so that the function maintains structure even under projection --- using such projections is necessary, as standard random restrictions simplify $\mathbf{AC}^0$ circuits. In contrast, we show that any De Morgan formula shrinks by a quadratic factor under our random projections, allowing us to prove the cubic lower bound.

Our proof techniques build on the proof of Håstad for the simpler case of balanced formulas. This allows for a significantly simpler proof at the cost of slightly worse parameters. As such, when specialized to the case of $p$-random restrictions, our proof can be used as an exposition of Håstad's result.



Changes to previous version:

Corrections of some minor errors.


Revision #1 to TR20-180 | 3rd December 2020 20:25

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





Revision #1
Authors: Yuval Filmus, Or Meir, Avishay Tal
Accepted on: 3rd December 2020 20:25
Downloads: 74
Keywords: 


Abstract:

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, which, up to lower order improvements, remains the state-of-the-art lower bound for any explicit function.

In this work, we extend the shrinkage result of Håstad to hold under a far wider family of random restrictions and their generalization — random projections. Based on our shrinkage results, we obtain an $\widetilde{\Omega}(n^{3})$ formula size lower bound for an explicit function computed in $\mathbf{AC}^0$. This improves upon the best known formula size lower bounds for $\mathbf{AC}^0$, that were only quadratic prior to our work. In addition, we prove that the KRW conjecture [Karchmer et al., Computational Complexity 5(3/4), 1995] holds for inner functions for which the unweighted quantum adversary bound is tight. In particular, this holds for inner functions with a tight Khrapchenko bound.

Our random projections are tailor-made to the function's structure so that the function maintains structure even under projection --- using such projections is necessary, as standard random restrictions simplify $\mathbf{AC}^0$ circuits. In contrast, we show that any De Morgan formula shrinks by a quadratic factor under our random projections, allowing us to prove the cubic lower bound.

Our proof techniques build on the proof of Håstad for the simpler case of balanced formulas. This allows for a significantly simpler proof at the cost of slightly worse parameters. As such, when specialized to the case of $p$-random restrictions, our proof can be used as an exposition of Håstad's result.



Changes to previous version:

Fixed a minor typo.


Paper:

TR20-180 | 2nd December 2020 23:20

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





TR20-180
Authors: Yuval Filmus, Or Meir, Avishay Tal
Publication: 3rd December 2020 04:53
Downloads: 104
Keywords: 


Abstract:

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, which, up to lower order improvements, remains the state-of-the-art lower bound for any explicit function.

In this work, we extend the shrinkage result of Håstad to hold under a far wider family of random restrictions and their generalization — random projections. Based on our shrinkage results, we obtain an $\widetilde{\Omega}(n^{3})$ formula size lower bound for an explicit function computed in $\mathbf{AC}^0$. This improves upon the best known formula size lower bounds for $\mathbf{AC}^0$, that were only quadratic prior to our work. In addition, we prove that the KRW conjecture [Karchmer et al., Computational Complexity 5(3/4), 1995] holds for inner functions for which the unweighted quantum adversary bound is tight. In particular, this holds for inner functions with a tight Khrapchenko bound.

Our random projections are tailor-made to the function's structure so that the function maintains structure even under projection --- using such projections is necessary, as standard random restrictions simplify $\mathbf{AC}^0$ circuits. In contrast, we show that any De Morgan formula shrinks by a quadratic factor under our random projections, allowing us to prove the cubic lower bound.

Our proof techniques build on the proof of Håstad for the simpler case of balanced formulas. This allows for a significantly simpler proof at the cost of slightly worse parameters. As such, when specialized to the case of $p$-random restrictions, our proof can be used as an exposition of Håstad's result.



ISSN 1433-8092 | Imprint