Publications [#354208] of Benjamin Rossman

Papers Published

1. 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 [doi]
   (last updated on 2024/04/19)

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