Delphi.science

Derandomized Sunflowers and Radical Lower Bounds

Source: arxiv.org/abs/2611.23109

Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff

arXivarxiv/2611.23109Nov 17, 2026cs.CCscore 0

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 i.i.d. distributions, they also hold for $O(w^2)$-wise independent distributions by Bazzi's theorem (Bazzi (SICOMP 2009); Tal (CCC 2017)), which states that width-$w$ DNFs cannot distinguish between such distributions and the uniform distribution. We prove a derandomization of robust sunflower lemmas for…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.23109
curl -X POST /api/v1/records/arxiv/2611.23109/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.23109/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'