Back to Search
Start Over
Sharper bounds on the Fourier concentration of DNFs
- Publication Year :
- 2021
-
Abstract
- In 1992 Mansour proved that every size-$s$ DNF formula is Fourier-concentrated on $s^{O(\log\log s)}$ coefficients. We improve this to $s^{O(\log\log k)}$ where $k$ is the read number of the DNF. Since $k$ is always at most $s$, our bound matches Mansour's for all DNFs and strengthens it for small-read ones. The previous best bound for read-$k$ DNFs was $s^{O(k^{3/2})}$. For $k$ up to $\tilde{\Theta}(\log\log s)$, we further improve our bound to the optimal $\mathrm{poly}(s)$; previously no such bound was known for any $k = \omega_s(1)$. Our techniques involve new connections between the term structure of a DNF, viewed as a set system, and its Fourier spectrum.<br />Comment: 19 pages; to appear at FOCS 2021
- Subjects :
- Computer Science - Computational Complexity
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2109.04525
- Document Type :
- Working Paper