Math @ Duke

Publications [#354208] of Benjamin Rossman
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. 311322, ISBN 9783030617912 [doi]
(last updated on 2022/01/23)
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ősRado 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 wset system that excludes a robust sunflower. In this paper, we use this result to obtain an exp (n1/2o(1)) lower bound on the monotone circuit size of an explicit nvariate monotone function, improving the previous record exp (n1/3o(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 cliquesunflowers and use this to prove an nΩ(k) lower bound on the monotone circuit size of the CLIQUE function for all k≤ n1/3o(1), strengthening the bound of Alon and Boppana[1].


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

