DNF sparsification beyond sunflowers

DOI10.1145/3313276.3316323zbMath1433.68176OpenAlexW2952968766MaRDI QIDQ5212786

Shachar Lovett, Jiapeng Zhang

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3313276.3316323

zbMATH Keywords

sunflower conjectureDNF sparsificationapproximate sunflowers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal set theory (05D05) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items

Unnamed Item, Coding for Sunflowers, Monotone circuit lower bounds from robust sunflowers