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