On the Limits of Sparsification

Rahul Santhanam, Srikanth Srinivasan

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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 2n−n CNFs each having a linear number of clauses for any 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 nk which cannot be 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 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)=(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 generator does 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 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(2n) for some fixed 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(+o(1))n).
Original languageEnglish
Pages (from-to)131-143
Number of pages12
JournalElectronic Colloquium on Computational Complexity (ECCC)
Publication statusPublished - 29 Nov 2011


Dive into the research topics of 'On the Limits of Sparsification'. Together they form a unique fingerprint.

Cite this