Is Valiant-Vazirani's Isolation Probability Improvable?

by Holger Dell, Valentine Kabanets, Dieter van Melkebeek, and Osamu Watanabe

Oded's comments

This paper presents several results that indicate that the celebrated isolation lemma of Valiant and Vazirani is quite optimal in various senses. One of these results shows that even a non-uniform randomized (polynomial-time) reduction cannot succeed with probability noticeably greater than $2/3$ (where a function is noticeable if it grows at least as fast as the reciprocal of some positive polynomial). (Recall that the VV isolation procedure succeeds w.p. $1/n$.) Another result is about black-box reductions, and here it is shown that success probability of $O(1/n)$ is optimal.

Following is a simplified sketch of the treatment of (non-uniform) deterministic reductions, where it is shown that if such reductions can perform isolation (as defined below -- see the two conditions re $A$), then NP has small non-uniform circuits. It suffices to show that such a reduction implies that the promise problem $(\uSAT,\cSAT)$ has small circuits, where $\uSAT$ is the set of uniquely satisfied circuits and $\cSAT$ is the set of unsatisfied circuits (in both cases of size $s(n)=poly(n)$, where $n$ is the number of input bits). Let $A$ be an algorithm mapping circuits $C$ to circuits $C'$ such that (1) $C'$ has same number of variables as $C$ and $C'(x) \leq C(x)$ for every $x$, and (2) if $C$ is in SAT, then $C'$ is in $\uSAT$.

Now consider a directed graph $G_s$ with vertex set $\uSAT$ such that there is a directed edge from $C_1$ to $C_2$ if either (i) $C_1 \and C_2$ is satisfiable (i.e., they have the same (unique) satisfying-assignment) or (ii) $A(C_1 \or C_2) \and C_1$ is unsatisfiable, which happens when they have different satisfying-assignments and $A$ outputs a circuit that is computationally equivalent to $C_2$. (Note that $A(C_1 \or C_2)$ must be computatiionally equivalent to either $C_1$ or $C_2$, and thus $G_s$ contains at least one directed edge between each two vertices.) Let $D_s$ be a dominating set of size $\leq|\log_2|\uSAT|$ of $G_s$, which exists since any tournament has a dominating set of log size (e.g., consider a greedy algorithm that iteratively selects a vertex of highest out-degree).

Our non-uniform advice consists of all circuits in $D_s$, denoted $C_1,...,C_t$, as well as their unique sat-assignments, denoted $x_1,...,x_t$. On input a circuit $C$ (which is either in $\uSAT$ or in $\cSAT$), the advice-taking machine accepts iff there exists an $i\in[t]$ such that either (i) $C(x_i)=\true$ or (ii) $A(C_i \or C)(x_i) = \false$. [Note that these conditions are equivalent to (i) $C_i\and C$ is satisfied, and (ii) $A(C_i \or C) \and C_i$ is unsatisfiable, resp.]

Then, if $C\in\uSAT$, there exists an $i$ such that there exists an edge from $C_i$ to $C$, which means that either (i) or (ii) holds. On the other hand, if $C\in\cSAT$, then for every $C'\in\SAT$ (which is satisfied by some $x'$) both conditions are violated (specifically, $A(C' \or C) \equiv C'$ and so it is satified (by $x'$)).

The argument can be extended to randomized reductions that succeed in obtaining isolation with probability noticeablly larger than $2/3$. Suppose that $A$ is such a reduction that works w.p. $p = 2/3 +2\eps$. Redefine the graph $G_s$ such that item (ii) is replaced by $\prob[A(C_1 \or C_2)\and C_1 \in\cSAT] \geq p/2$. Note that if for every two circuits $C_1$ and $C_2$ either $C_1\equiv C_2$, which implies that (i) holds in both directions, or $\prob[A(C_1 \or C_2)\equiv C_1] + \prob[A(C_1 \or C_2)\equiv C_2] \geq p$, which implies the existence of an edge in at least one direction. On input a circuit $C$ (and using advice analogous to the above), the machine will check (for each $i$) whether (i) $C(x_i)=\true$ (as before) or (ii) $\prob[A(C_i \or C)(x_i)=\false]\geq p/2 -\eps = 1/3$ holds. (As we shall see, it suffices for the machine to approximate the probability $\prob[A(C_i \or C)(x_i)]$ up to an additive term of $\eps$.) Note that if $C\in\uSAT$ and $C_i$ dominates $C$, then either $C(x_i)=\true$ (if $C\equiv C_i$) or $\prob[A(C_i \or C)(x_i)=\false] \geq p/2 = 1/3 +\eps$ (since $x_i$ is the unique sat-assignment of $C_i$). On the other hand, for any unsatisfiable $C$ and any uniquely-satified $C'$ it holds that $\prob[A(C' \or C) \equiv C'] \geq p$, and so for $x'$ that satisfies $C'$ it holds that $\prob[A(C' \or C)(x')=\false] \leq 1-p = 1/3 -2\eps$.

Turning to a different result in the paper, the black-box model refers to augmenting the circuit $C$ by a randomly constructed circuit $D$ (which is essentially constructed obliviously of $C$); that is, the isolated circuit is $C'(x) = C(x) \and D(x)$. The lower bound considers a distribution of circuits $C$, and shows that each fixed circuit $D$ successeds in isolation w.r.t this distribution with probability $O(1/n)$. The idea is that isolation occurs iff $|D^{-1}(1)|\cdot|C^{-1}(1)|$ is approximately $2^n$. So selecting $C$ at random among all circuits having $2^i$ satisfying assignments, whereas $i$ is selected uniformly in $[n]$, will do.

The original abstract

The Isolation Lemma of Valiant and Vazirani (1986) provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: Given a Boolean circuit C on n input variables, the procedure outputs a new circuit C' on the same n input variables such that (i) every satisfying assignment of C' also satisfies C, and (ii) if C is satisfiable, then C' has exactly one satisfying assignment. In particular, if C is unsatisfiable, then (i) implies that C' is unsatisfiable. The Valiant-Vazirani procedure is randomized, and when C is satisfiable it produces a uniquely satisfiable circuit C' with probability Omega(1/n).

Is it possible to have an efficient deterministic witness-isolating procedure? Or, at least, is it possible to improve the success probability of a randomized procedure to a large constant? We prove that there exists a non-uniform randomized polynomial-time witness-isolating procedure with success probability bigger than 2/3 if and only if NP has polynomial-size circuits. We establish similar results for other variants of witness isolation, such as reductions that remove all but an odd number of satisfying assignments of a satisfiable circuit.

We also consider a blackbox setting of witness isolation that generalizes the setting of the Valiant-Vazirani Isolation Lemma, and give an upper bound of O(1/n) on the success probability for a natural class of randomized witness-isolating procedures.

See ECCC TR11-151

Back to list of Oded's choices. .