DNF sparsification beyond sunflowers

DOI10.1145/3313276.3316323MaRDI QIDQ5212786zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• DNF sparsification and a faster deterministic counting algorithm
• Decision List Compression by Mild Random Restrictions
• On the limits of sparsification
• Approximation by DNF: Examples and Counterexamples
• On DNF approximators for monotone Boolean functions

Cited in

(4)

• scientific article; zbMATH DE number 7564405 (Why is no real title available?)
• Monotone circuit lower bounds from robust sunflowers
• Coding for Sunflowers
• DNF sparsification and a faster deterministic counting algorithm

This page was built for publication: DNF sparsification beyond sunflowers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212786)