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 linearnumber of clauses. This lemma has subsequently played a key role in the studyof the exact complexity of the satisfiability problem. A natural question iswhether an analogous structural result holds for CNFs or even for broadernon-uniform classes such as constant-depth circuits or Boolean formulae.We prove a very strong negative result in this connection: For every superlinearfunction f(n), there are CNFs of size f(n) which cannot be written asa disjunction of 2n−n CNFs each having a linear number ofclauses for any 0">0. We also give a hierarchy of such non-sparsifiable CNFs: For everyk, there is a k for which there are CNFs of size nk which cannotbe written as a sub-exponential size disjunction of CNFs of size nk. 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 appropriatelybounded.

As by-products of our result, we make progress both on questions about circuit lower bounds for depth-3 circuits and satisfiability algorithms forconstant-depth circuits. Improving on a result of Impagliazzo, Paturi andZane, for any f(n)=(nlog(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 generatordoes not have depth-3 circuits of size 2n−o(n) with bounded bottom fan-in.We show that if we could decrease the seed length of our generator belown, we would get an explicit function which does not have linear-sizelogarithmic-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-sizeconstant-width CNFs. As a corollary, we show that if there is an algorithm forCNF satisfiability which runs in time O(2n) for some fixed1 on CNFs of linear size, then there is an algorithm forsatisfiability of linear-size constant-depth circuits which runs in timeO(2(+o(1))n).