2021/09/09 by Victor Lecomte, Lecomte, Victor, Li-Yang Tan +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2109.04525
openalex publication_date 2021/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1992 Mansour proved that every size-s DNF formula is Fourier-concentrated on sO(loglog s) coefficients. We improve this to sO(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(k3/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.