Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses

by Holger Dell and Dieter van Melkebeek

Oded's comments

(Yes, I only happened to notice this work now...)

My main interest in this paper is due to an application to the study of PCPs. Known constructions of PCPs for $k$-SAT over $n$ variables and $m$ clauses use a proof of length that is greater than $\min(n^k,m)$, and my feeling was that this is an artifact of the first step in the construction (i.e., either summing over all $k$-tuples of variables (and the $m$ clauses) or routing auxiliary variables that correspond to the $m$ clauses). But this work shows that, under a widely believed conjecture (i.e., coNP not having small non-determionistic circuits), no PCP construction can be significantly better (i.e., in the worst case the oracle must have length $n^{k-0.001}$).

The main focus of the paper is on ``compression'' of instances of hard problems, in the context of parameterized complexity. The question if whether, for a fixed parameter $k$, one can efficiently transform $n$-bit long instances (for the $k$-parameterized problem) to $f(k)$-bit long instances such that a solution of the large instance can be efficiently obtained from the solution of the compressed instance; whenever the answer is positive, one obtains a algorithm that runs in time that is polynomial in $n$ and (typically) exponential in $f(k)$, whereas the obvious algorithms run in time $n^k$. One of the results in the paper is an almost quadratic lower bound on $f(k)$ for the $k$-Vertex Cover problem, where a compression obtaining a quadratic $f$ is known. Prior lower bounds on $f$ for other problems have referred to problems for which a polynomial upper bound on $f$ is not known.

The original abstract

See either JACM, Vol. 61(4), Art. 23, 2014 or ECCC TR10-038.


Back to list of Oded's choices.