Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for $k$-CNFs:
every k-CNF is a sub-exponential size disjunction of $k$-CNFs with a linear
number of clauses. This lemma has subsequently played a key role in the study
of the exact complexity of the satisfiability problem. A natural question is
whether an analogous structural result holds for CNFs or even for broader
non-uniform classes such as constant-depth circuits or Boolean formulae.
We prove a very strong negative result in this connection: For every superlinear
function $f(n)$, there are CNFs of size $f(n)$ which cannot be written as
a disjunction of $2^{n- \varepsilon n}$ CNFs each having a linear number of
clauses for any $\varepsilon > 0$. We also give a hierarchy of such non-sparsifiable CNFs: For every
$k$, there is a $k'$ for which there are CNFs of size $n^{k'}$ which cannot
be written as a sub-exponential size disjunction of CNFs of size $n^{k}$.
Furthermore, our lower bounds hold not just against CNFs but against an {\it arbitrary}
family of functions as long as the cardinality of the family is appropriately
bounded.
As by-products of our result, we make progress both on questions about
circuit lower bounds for depth-3 circuits and satisfiability algorithms for
constant-depth circuits. Improving on a result of Impagliazzo, Paturi and
Zane, for any $f(n) = \omega(n \log(n))$, we define a pseudo-random function generator with seed length $f(n)$
such that with high probability, a function in the output of this generator
does not have depth-3 circuits of size $2^{n-o(n)}$ with bounded bottom fan-in.
We show that if we could decrease the seed length of our generator below
$n$, we would get an explicit function which does not have linear-size
logarithmic-depth series-parallel circuits, solving a long-standing open question.
Motivated by the question of whether CNFs sparsify into bounded-depth circuits,
we show a {\it simplification} result for bounded-depth circuits: any bounded-depth circuit of linear size can be written as a sub-exponential size disjunction of linear-size
constant-width CNFs. As a corollary, we show that if there is an algorithm for
CNF satisfiability which runs in time $O(2^{\alpha n})$ for some fixed
$\alpha < 1$ on CNFs of linear size, then there is an algorithm for
satisfiability of linear-size constant-depth circuits which runs in time
$O(2^{(\alpha + o(1))n})$.
