Sharper bounds on the Fourier concentration of DNFs
share
In 1992 Mansour proved that every size-s DNF formula is Fourier-concentrated on s^O(loglog s) coefficients. We improve this to s^O(loglog 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 Θ̃(loglog s), we further improve our bound to the optimal poly(s); previously no such bound was known for any k = ω_s(1). Our techniques involve new connections between the term structure of a DNF, viewed as a set system, and its Fourier spectrum.
READ FULL TEXT