跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.23109 · v1

Derandomized Sunflowers and Radical Lower Bounds

去随机化向日葵引理与根式下界

首次提交 2026-11-18 01:28
版本更新 2026-11-18 01:28
雷达观测 2026-11-18 12:34
arXiv ↗PDF ↗

摘要

Robust Sunflower lemmas imply that any large enough monotone DNF of width ww contains a sunflower, i.e., a DNF equivalent to the conjunction of a common core with a DNF that is heavily biased towards 11. While these lemmas are typically proved in the context of the uniform distribution or i.i.d. distributions, they also hold for O(w2)O(w^2)-wise independent distributions by Bazzi's theorem (Bazzi (SICOMP 2009); Tal (CCC 2017)), which states that width-ww DNFs cannot distinguish between such distributions and the uniform distribution. We prove a derandomization of robust sunflower lemmas for O(w)O(w)-wise independent distributions, which recovers the derandomization above with slightly weaker parameters. Notably, our result also holds for distributions whose marginals are "locally independent" and "approximately identically" distributed. It is not known whether such distributions fool general DNFs, which makes the derandomization via DNF-fooling techniques unavailable. Our proof of this derandomization is via the method of moments, which might be of independent interest. We apply this result to obtain improved separations between non-monotone arithmetic circuits and the radical of monotone circuits. Specifically, we construct an explicit family of multilinear polynomials PnP_n that have small non-monotone arithmetic circuits such that any power of PnP_n cannot be computed by monotone arithmetic circuits of sub-exponential size. This improves on a recent result of Cavalar, Fabris, Mukhopadhyay, Srinivasan and Yehudayoff (STOC 2026), who proved a non-explicit separation that was quasipolynomial. Our construction uses Nisan-Wigderson designs with an additional linear-algebraic expansion property.

作者备注:Full version of FOCS 2026 paper

AI 论文解读

基于摘要 · 非全文审阅

作者通过矩方法证明O(w)阶独立分布下的去随机化稳健向日葵引理,并据此构造显式多项式族,得到非单调算术电路与单调电路根式之间更强的分离。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-18 01:28 · 最新观测版本

Derandomized Sunflowers and Radical Lower Bounds

Robust Sunflower lemmas imply that any large enough monotone DNF of width ww contains a sunflower, i.e., a DNF equivalent to the conjunction of a common core with a DNF that is heavily biased towards 11. While these lemmas are typically proved in the context of the uniform distribution or i.i.d. distributions, they also hold for O(w2)O(w^2)-wise independent distributions by Bazzi's theorem (Bazzi (SICOMP 2009); Tal (CCC 2017)), which states that width-ww DNFs cannot distinguish between such distributions and the uniform distribution. We prove a derandomization of robust sunflower lemmas for O(w)O(w)-wise independent distributions, which recovers the derandomization above with slightly weaker parameters. Notably, our result also holds for distributions whose marginals are "locally independent" and "approximately identically" distributed. It is not known whether such distributions fool general DNFs, which makes the derandomization via DNF-fooling techniques unavailable. Our proof of this derandomization is via the method of moments, which might be of independent interest. We apply this result to obtain improved separations between non-monotone arithmetic circuits and the radical of monotone circuits. Specifically, we construct an explicit family of multilinear polynomials PnP_n that have small non-monotone arithmetic circuits such that any power of PnP_n cannot be computed by monotone arithmetic circuits of sub-exponential size. This improves on a recent result of Cavalar, Fabris, Mukhopadhyay, Srinivasan and Yehudayoff (STOC 2026), who proved a non-explicit separation that was quasipolynomial. Our construction uses Nisan-Wigderson designs with an additional linear-algebraic expansion property.

查看此版本解读 →查看此版本原文 ↗