ECCC-Report TR20-181https://eccc.weizmann.ac.il/report/2020/181Comments and Revisions published for TR20-181en-usFri, 05 Aug 2022 17:15:28 +0300
Revision 2
| Monotone Circuit Lower Bounds from Robust Sunflowers |
Bruno Pasqualotto Cavalar,
Mrinal Kumar,
Benjamin Rossman
https://eccc.weizmann.ac.il/report/2020/181#revision2Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity, DNF sparsification, randomness extractors, and recent advances on the Erd\H{o}s-Rado sunflower conjecture. The recent breakthrough of Alweiss, Lovett, Wu and Zhang gives an improved bound on the maximum size of a $w$-set system that excludes a robust sunflower. In this paper, we use this result to obtain an $\exp(n^{1/2-o(1)})$ lower bound on the monotone circuit size of an explicit $n$-variate monotone function, improving the previous best known $\exp(n^{1/3-o(1)})$ due to Andreev and Harnik and Raz. We also show an $\exp(\Omega(n))$ lower bound on the monotone arithmetic circuit size of a related polynomial. Finally, we introduce a notion of robust clique-sunflowers and use this to prove an $n^{\Omega(k)}$ lower bound on the monotone circuit size of the CLIQUE function for all $k \le n^{1/3-o(1)}$, strengthening the bound of Alon and Boppana.
Fri, 05 Aug 2022 17:15:28 +0300https://eccc.weizmann.ac.il/report/2020/181#revision2
Revision 1
| Monotone Circuit Lower Bounds from Robust Sunflowers |
Bruno Pasqualotto Cavalar,
Mrinal Kumar,
Benjamin Rossman
https://eccc.weizmann.ac.il/report/2020/181#revision1Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity, DNF sparsification, randomness extractors, and recent advances on the Erd\H{o}s-Rado sunflower conjecture. The recent breakthrough of Alweiss, Lovett, Wu and Zhang gives an improved bound on the maximum size of a $w$-set system that excludes a robust sunflower. In this paper, we use this result to obtain an $\exp(n^{1/2-o(1)})$ lower bound on the monotone circuit size of an explicit $n$-variate monotone function, improving the previous best known $\exp(n^{1/3-o(1)})$ due to Andreev and Harnik and Raz. We also show an $\exp(\Omega(n))$ lower bound on the monotone arithmetic circuit size of a related polynomial. Finally, we introduce a notion of robust clique-sunflowers and use this to prove an $n^{\Omega(k)}$ lower bound on the monotone circuit size of the CLIQUE function for all $k \le n^{1/3-o(1)}$, strengthening the bound of Alon and Boppana.
Mon, 07 Dec 2020 19:29:50 +0200https://eccc.weizmann.ac.il/report/2020/181#revision1
Paper TR20-181
| Monotone Circuit Lower Bounds from Robust Sunflowers |
Bruno Pasqualotto Cavalar,
Mrinal Kumar,
Benjamin Rossman
https://eccc.weizmann.ac.il/report/2020/181Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity, DNF sparsification, randomness extractors, and recent advances on the Erd\H{o}s-Rado sunflower conjecture. The recent breakthrough of Alweiss, Lovett, Wu and Zhang gives an improved bound on the maximum size of a $w$-set system that excludes a robust sunflower. In this paper, we use this result to obtain an $\exp(n^{1/2-o(1)})$ lower bound on the monotone circuit size of an explicit $n$-variate monotone function, improving the previous best known $\exp(n^{1/3-o(1)})$ due to Andreev and Harnik and Raz. We also show an $\exp(\Omega(n))$ lower bound on the monotone arithmetic circuit size of a related polynomial. Finally, we introduce a notion of robust clique-sunflowers and use this to prove an $n^{\Omega(k)}$ lower bound on the monotone circuit size of the CLIQUE function for all $k \le n^{1/3-o(1)}$, strengthening the bound of Alon and Boppana.
Fri, 04 Dec 2020 21:54:54 +0200https://eccc.weizmann.ac.il/report/2020/181