The Sparsification Lemma via Measure and Conquer

The Sparsification Lemma of Impagliazzo, Paturi, and Zane [FOCS 1998; JCSS 2001] is a foundational result which enables the extensive use of the Exponential Time Hypothesis (ETH) to giveasymptotically tight lower bounds for exponential-time algorithms and parameterized algorithms. The lemma states that, for every positive integer \(d\) and every real \(\varepsilon \gt 0\), every boolean \(d\)-CNF formula can be expressed as a disjunction of \(2^{\varepsilon n}\) \(d\)-CNF formulas, each of which is \(C_{(\varepsilon,d)}\)-sparse, which means that every variable appears in at most \(C_{(\varepsilon,d)}\) clauses. While the original proof establishes the lemma with \(C_{(\varepsilon,d)}\) upper bounded by a double exponential function in \(d\), subsequent refinements by Calabro et al. [CCC 2006] and Zeijlemaker [M.Sc. Thesis, Eindhoven University of Technology, 2020] improve the sparsity \(C_{(\varepsilon,d)}\) to \((d/\varepsilon)^{\mathcal{O}(d)}\). The existing proofs of the Sparsification Lemma rely on intricate analysis of recursion trees. In this work, we present a short and self-contained proof of the Sparsification Lemma that matches the best known bounds. Our analysis avoids all non-trivial recursion-tree arguments used in prior work and instead applies an inductive argument based on the Measure and Conquer framework. This results in a modular and (in our opinion) conceptually simpler proof.