期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-19
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity [21], DNF sparsification [9], randomness extractors [14], and recent advances on the Erd˝os-Rado sunflower conjecture [3,15,18]. The recent breakthrough of Alweiss, Lovett, Wu and Zhang [3] 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 [5] and Harnik and Raz [10]. 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 6 n 1/3−o(1), strengthening the bound of Alon and Boppana [1].
