Name
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/978-3-030-61792-9_25 | LATIN |
DocType | Volume | Citations |
Conference | 27 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bruno Pasqualotto Cavalar | 1 | 0 | 0.34 |
| Mrinal Kumar | 2 | 37 | 7.11 |
| Benjamin Rossman | 3 | 4 | 4.28 |