Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DERANDOMIZATION OF ROBUST SUNFLOWER LEMMAS:
Reports tagged with Derandomization of Robust Sunflower lemmas:
TR26-220 | 28th September 2026
Bruno Pasqualotto Cavalar, Théo Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff

Derandomized Sunflowers and Radical Lower Bounds

Robust Sunflower lemmas imply that any large enough monotone DNF of width $w$ contains a sunflower, i.e., a DNF equivalent to the conjunction of a common core with a DNF that is heavily biased towards $1$. While these lemmas are typically proved in the context of the uniform distribution or ... more >>>




ISSN 1433-8092 | Imprint