Paper Info
Title
On the limits of sparsification
Abstract
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 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)=ω(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 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 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αn) for some fixed αO(2(α+o(1))n).
Year
DOI
Venue
2012
10.1007/978-3-642-31594-7_65
international colloquium on automata languages and programming
Keywords
DocType
Volume
cnfs sparsify,depth-3 circuit,seed length,n cnfs,constant-depth circuit,sub-exponential size disjunction,linear-size constant-width cnfs,bounded-depth circuit,linear number,size nk
Conference
18
ISSN
Citations 
PageRank 
0302-9743
7
0.55
References 
Authors
14
2
Name
Order
Citations
PageRank
Rahul Santhanam139538.31
Srikanth Srinivasan213221.31