**Papers Published**

- Cavalar, BP; Kumar, M; Rossman, B,
*Monotone Circuit Lower Bounds from Robust Sunflowers*, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12118 LNCS (January, 2020), pp. 311-322, ISBN 9783030617912

(last updated on 2022/05/24)**Abstract:**

Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity[14], DNF sparsification[6], randomness extractors[8], and recent advances on the Erdős-Rado sunflower conjecture[3, 9, 12]. 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 (n1/2-o(1)) lower bound on the monotone circuit size of an explicit n-variate monotone function, improving the previous record exp (n1/3-o(1)) of Harnik and Raz[7]. 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≤ n1/3-o(1), strengthening the bound of Alon and Boppana[1].