论文标题
从强大的向日葵的单调电路下限
Monotone Circuit Lower Bounds from Robust Sunflowers
论文作者
论文摘要
强大的向日葵是对单调电路复杂性，DNF稀疏性，随机性提取器以及Erdős-Rado Sunflower猜想的最新进展的组合向日葵的概括。 Alweiss，Lovett，Wu和Zhang最近的突破对$ W $ set系统的最大尺寸进行了改进，不包括强大的向日葵。 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.我们还显示了相关多项式的单调算术电路大小上的$ \ exp（ω（n））$下限。最后，我们介绍了一个强大的集团刺激器的概念，并使用它来证明所有$ n^{ω（k）} $下限在所有$ k \ le n^{1/3-o（1）} $的单调电路大小上的单调电路大小，从而增强了Alon和Boppana的界限。
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ő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(Ω(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^{Ω(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.
