Sparsification Lemma for k-SAT and Exponential Time Hypothesis

Question

According to R. Impagliazzo, R. Paturi and F. Zane, 2001 an instance of $k$-SAT is called sparse if $m = O(n)$ where $m$ denotes the number of clauses and $n$ the number of variables. The Sparsifiction Lemma, as mentioned in R. Impagliazzo, R. Paturi, 2001 says:

[...] that an arbitrary $k$-CNF can be expressed (in subexponential time) as the disjunction of a subexponential number of linear size $k$-CNFs. More precisely [...]

For all $\varepsilon > 0$, $k$-CNF $F$ can be written as the disjunction of at most $2^{\varepsilon n}$ $k$-CNF $F_i$ such that $F_i$ contains each variable in at most $c(k,\varepsilon)$ clauses for some function $c$. Moreover, this reduction takes at most $poly(n) 2^{\varepsilon n}$ time.

In the above reduction, each $k$-CNF $F_i$ has at most $c(k,\varepsilon)n$ many clauses, hence is sparse in the above sense. According to this talk, the Exponential Time Hypothesis (ETH) says:

$3$-SAT instances (with $n$ variables and $m$ clauses) cannot be solved in time $O(poly(n) 2^{o(n)})$.

(the $O^{\ast}$-star notation just suppresses polynomials). And it says that the Sparsification Lemma is equivalent to:

If ETH holds, then $3$-SAT instances cannot be solved in time $O(poly(n) 2^{o(n+m)})$.

I do not understand the second claim, so I am asking if anyone could please explain why this is a statement of the Sparsification Lemma, what has it to do with the Lemma as stated before?

Answer 1

I think your confusion might come from misquoting the statement of ETH.

$3$-SAT instances (with $n$ variables and $m$ clauses) cannot be solved in time $poly(n)\cdot 2^{o(n)}$.

This statement is not ETH, but rather its weak (but often very useful) corollary. The ETH claims the following:

There exists a $\delta>0$ such that no algorithm with running time $poly(m)\cdot 2^{\delta n}$ can solve $3$-SAT.

Now we can actually use the Sparsification Lemma to prove the following:

If ETH holds, then $3$-SAT instances cannot be solved in time $poly(m)\cdot 2^{o(n+m)}$.

Assume that there is an algorithm $A$ which solves $3$-SAT in time $poly(m)\cdot 2^{o(n+m)}$. For any $\delta>0$, we'll construct an algorithm $B_\delta$ which solves $3$-SAT in time $poly(m)\cdot 2^{\delta n+o(n)}$. (This contradicts ETH and finishes the proof.)

First, the algorithm $B_\delta$ takes an input formula $\phi$, applies the Sparsification Lemma with $\varepsilon=\delta$, and in time $poly(m)\cdot 2^{\delta n}$ produces $2^{\delta n}$ formulas $\phi_i$, such that $\phi$ is satisfiable if and only if $\exists i\colon \phi_i$ is satisfiable. Now the algorithm $B_\delta$ solves each of $\phi_i$ using the algorithm $A$. Note that by Sparsification Lemma the number of clauses in $\phi_i$ is $O(n)$, thus, each $\phi_i$ is solved by $A$ in time $2^{o(n)}$. Now the total running time of $B_\delta$ is $$poly(m)\cdot 2^{\delta n} + poly(m)\cdot 2^{\delta n}2^{o(n)}=poly(m)\cdot 2^{\delta n+o(n)}\; .$$