Sharper bounds on the Fourier concentration of DNFs

Victor Lecomte, Li-Yang Tan

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 num…