$$

Adapted from Lecture 12 of Ryan O’Donnell’s Fall 2017 graduate complexity class.

Say you have some formula or circuit $f:{\{0,1\}}^n\to \{0,1\}$ and you want to figure out roughly how many satisfying assignments it has: let’s denote this

$$\mathrm{\#}f:=\mathrm{\#}\{x\mid f(x)=1\}.$$

Say you want to know $\mathrm{\#}f$ up to a factor $100$. Well, that’s a hard problem: in particular, that would tell you whether $f$ is satisfiable or not. But what if you had a very clever friend named Merlin, who is able to solve $\mathrm{SAT}$?

The issue is that Merlin is only good at telling whether $\mathrm{\#}f=0$ or $\mathrm{\#}f\ge 1$, whereas you want to figure out whether $\mathrm{\#}f<\frac{1}{10}M$ or $\mathrm{\#}f>10M$ for some $M$. So you would love to have some transformation $f\mapsto f^{\prime }$ that reliably “divides $\mathrm{\#}f$ by a factor $M$”, so that if $\mathrm{\#}f<\frac{1}{10}M$, then $\mathrm{\#}{f}^{\prime }\approx \frac{1}{10}$ (so $f^{\prime }$ is unsatisfiable), but if $\mathrm{\#}f>10M$, then $\mathrm{\#}{f}^{\prime }\approx 10$ (so $f^{\prime }$ is satisfiable).

Reliably dividing the number of satisfying assignments

The most natural way to do this would be to let $f^{\prime }$ be $f$ restricted to a $1/M$ fraction of the inputs. Concretely, you could pick a random subset $S\subseteq {\{0,1\}}^n$ of $\approx \frac{2^n}{M}$ strings and just ask your friend Merlin if “$f(x)\wedge x\in S$” is satisfiable.

However, even just drawing the random subset $S$ and sending it to Merlin would take exponential time. But let’s sweep that issue under the rug for now and see what happens if you can somehow do it.

Let’s draw $S$ by picking every string independently with probability $1/M$, and let $X$ be the number of satisfying assignments that end up in $S$. We want $X$ to be mostly $0$ when $\mathrm{\#}f\le \frac{1}{10}M$ and mostly $\ne 0$ when $\mathrm{\#}f\ge 10M$.

First, suppose that $\mathrm{\#}f\le \frac{1}{10}M$. Then

$$\mathrm{Pr}[X\ne 0]\le \mathrm{E}[X]=\frac{\mathrm{\#}f}{M}\le \frac{1}{10}.$$

Now, suppose that $f$ has $\ge 10M$ satisfying assignments. We have $\mathrm{E}[X]\ge 10$, but that doesn’t necessarily mean that $X$ isn’t often $0$. However, $X$ is a sum of independent Bernoullis, and Bernoulli sums vary like they average (i.e. $\mathrm{Var}[X]\le \mathrm{E}[X]$). This means that when $X=0$ it is $\mathrm{E}[X]/\sqrt{\mathrm{Var}[X]}\ge \sqrt{\mathrm{E}[X]}$ standard deviations from average, so by Chebyshev

$$\mathrm{Pr}[X=0]\le \frac{1}{\mathrm{E}[X]}\le \frac{1}{10}.$$

Works great! Now let’s try to replace this magical “$x\in S$” test by something tractable.

Derandomization

Perhaps instead of sending $S$, you could send a small circuit that recognizes $S$? For example, you could pick a random hash function $h:{\{0,1\}}^n\to {\{0,1\}}^l$ with $l:=\log M$ and let $S:=\{x\mid h(x)=0^l\}$. Well, a truly random hash function is still intractable to draw and send, but maybe we don’t really need true randomness?

All we really needed of the variable $X$ above was that:

• it had the right average: $\mathrm{E}[X]=\frac{\mathrm{\#}f}{M}$;
• it’s variance wasn’t too big: $\mathrm{Var}[X]\le \mathrm{E}[X]$.

Both of these fact continue to be true as long as the events “$h(x)=0^l$” each have the correct probability $2^{-l}=1/M$ and are merely pairwise independent (since variance depends only on pairwise correlations). That is, all we need is for $h$ to be a pairwise uniform hash function.

We saw in k-wise uniformity that pairwise uniform hash functions from ${\{0,1\}}^n$ to $\{0,1\}$ can be sampled using seed length $O(n)$ and computed in linear time. To get $l$ bits of input instead of just $1$, we can just sample $l$ independent copies, for a total seed length of $O(nl)\le O(n^2)$.¹ Concretely, this corresponds to sampling $l$ random “parity check” strings $r^{(1)},\dots ,r^{(l)}\in {\{0,1\}}^n$ and $l$ random bits $b_1,\dots b_l$, and defining $h(x):=((r^{(1)}\cdot x)\oplus b_1,\dots ,(r^{(l)}\cdot x)\oplus b_l)$, which means $x\in S$ iff each of the parity checks $r^{(i)}\cdot x$ has the value indicated by $b_i$.

Overall, we’ve shown that the problem of distinguishing between $\le \frac{1}{10}M$ satisfying assignments and $\ge 10M$ satisfying assignments can be randomly reduced in polynomial time to a $\mathrm{SAT}$ question, which places the problem in (promise) $\mathsf{AM}$.

Boosting the precision

The above only tells us the answer up to a factor $100$. As it turns out, if you can do that, you can get any approximation factor bigger than $1$, just by asking Merlin a slightly bigger question. Indeed, if you consider the “$k^{\text{th}}$ tensor power” of $f$, which is a function over $kn$ bits defined as

$$f^{\otimes k}(x^{(1)},\dots ,x^{(k)}):=f(x^{(1)})\wedge \cdots \wedge f(x^{(k)}),$$

then $\mathrm{\#}{f}^{\otimes k}=(\mathrm{\#}f{)}^k$. So if we figure out $\mathrm{\#}{f}^{\otimes k}$ up to a factor $100$, we know $\mathrm{\#}f$ up to a factor ${100}^{1/k}$.

Valiant-Vazirani: reducing $\mathrm{SAT}$ to $\mathrm{UniqueSAT}$

Using this trick of “dividing $\mathrm{\#}f$ by a factor $M$” you can also solve $\mathrm{SAT}$ assuming you only have a (weaker) $\mathrm{UniqueSAT}$ oracle: a $\mathrm{SAT}$ oracle that is only guaranteed to give the right answer when $\mathrm{\#}f$ is either $0$ or $1$.

The intuition is that if $\mathrm{\#}f$ is, say, $(1\pm ϵ)M$, then a random subset $S\subseteq {\{0,1\}}^n$ of $\frac{2^n}{M}$ strings should contain roughly one satisfying assignment, and there will be a reasonable chance that $S$ contains exactly one satisfying assignment, in which case the $\mathrm{UniqueSAT}$ oracle “works”. Then it suffices to try this out with $M$ going from $1$ to $2^n$, increasing by a factor $(1\pm ϵ)$ every time:

• if $\mathrm{\#}f=0$, then “$f(x)\wedge x\in S$” will never be satisfiable, so the oracle will always answer no;
• if $\mathrm{\#}f\ge 1$, then when $M$ gets close to $\mathrm{\#}f$, there will be a non-zero chance that “$f(x)\wedge x\in S$” is uniquely satisfiable, in which case the oracle would say yes (and we don’t care what the oracle says for the other values of $M$).

This has one-sided error, so are happy with any constant probability that the oracle says yes when $\mathrm{\#}f\ge 1$.

To make this work when $S:=\{x\mid h(x)=0^l\}$ is selected by a pairwise uniform hash function $h$ (instead of completely at random), we need to be just a bit more careful, because we don’t know the distribution of $X$ in full detail. Concretely we will show that if $aM\le \mathrm{\#}f\le bM$ for two small constants $0<a<b<1$ which we will choose later, then $\mathrm{Pr}[X=1]\ge \mathrm{\Omega }(1)$.

We’ll again use the fact that Bernoulli sums vary like they average, i.e. $\mathrm{Var}[X]\le \mathrm{E}[X]$. The idea is that values $X\ge 2$ contribute an inordinate amount to the variance of $X$, so they cannot account for too much of the mean of $X$. Therefore, we must have $X=1$ at least some of the time, in order to contribute to the rest of the mean.

We have $\mathrm{Var}[X]\le \mathrm{E}[X]\le b$ and $\mathrm{Var}[X]:=\mathrm{E}[X^2]-\mathrm{E}[X{]}^2$, so

$$\mathrm{E}\left[X^2\right]\le \mathrm{E}[X]+\mathrm{E}[X{]}^2\le \mathrm{E}[X]+b^2,$$

which intuitively shows that we cannot have too much weight on high values of $X$. Formally, we have $X^2\ge 2X$ all the time except when $X=1$ (in which case $X^2$ is $2X-1$), so

$$\mathrm{E}\left[X^2\right]\ge \mathrm{E}[2X]-\mathrm{Pr}[X=1].$$

Combining the two, we get

$$\mathrm{Pr}[X=1]\ge \mathrm{E}[X]-b^2\ge a-b^2,$$

so setting $a:=\frac{1}{8}$ and $b:=\frac{1}{4}$ will guarantee that $\mathrm{Pr}[X=1]\ge \frac{1}{16}$.

1. I think this is not the most efficient but whatever, it’s polynomial. ↩