Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR20-181 | 5th August 2022 17:15

#### Monotone Circuit Lower Bounds from Robust Sunflowers

Revision #2
Authors: Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman
Accepted on: 5th August 2022 17:15
Keywords:

Abstract:

Robust 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.

Changes to previous version:

Journal version.

Revision #1 to TR20-181 | 7th December 2020 19:29

#### Monotone Circuit Lower Bounds from Robust Sunflowers

Revision #1
Authors: Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman
Accepted on: 7th December 2020 19:29
Keywords:

Abstract:

Robust 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.

Changes to previous version:

Added references to previous work on arithmetic circuit complexity.

### Paper:

TR20-181 | 4th December 2020 20:51

#### Monotone Circuit Lower Bounds from Robust Sunflowers

TR20-181
Authors: Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman
Publication: 4th December 2020 21:54