Monotone circuit lower bounds from robust sunflowers
From MaRDI portal
Publication:5970784
DOI10.1007/s00453-022-01000-3OpenAlexW3109005260MaRDI QIDQ5970784
Mrinal Kumar, Benjamin Rossman, Bruno Pasqualotto Cavalar
Publication date: 8 December 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-022-01000-3
computational complexityextremal combinatoricscircuit complexitymonotone arithmetic circuitsmonotone circuit complexitysunflowersarithmetic circuit complexityrobust sunflower lemma
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- DNF sparsification and a faster deterministic counting algorithm
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- A 4n-lower bound on the monotone network complexity of a one-output Boolean function
- The monotone circuit complexity of Boolean functions
- A method for obtaining efficient lower bounds for monotone complexity
- A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound
- Note on sunflowers
- Higher lower bounds on monotone size
- Intersection Theorems for Systems of Sets
- Algebraic Function Fields and Codes
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Poisson approximation for large deviations
- A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
- Strongly exponential lower bounds for monotone computation
- Coding for Sunflowers
- Improved bounds for the sunflower lemma
- Separating monotone VP and VNP
- DNF sparsification beyond sunflowers
- Explicit binary tree codes with polylogarithmic size alphabet
- The Monotone Complexity of $k$-Clique on Random Graphs
- Combinatorics of monotone computations
