DNF sparsification beyond sunflowers

DOI10.1145/3313276.3316323zbMATH Open1433.68176OpenAlexW2952968766MaRDI QIDQ5212786FDOQ5212786

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

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

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)

Cited In (4)

• Title not available (Why is that?)
• 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)