## 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.