- Authors: H. Dell, V. Kabanets, D. van Melkebeek, and O. Watanabe.

- Reference:
*Computational Complexity*, 22: 345-383, 2013.
Special issue for selected papers from the
27th IEEE Conference on Computational Complexity.

- Earlier version:

#### Abstract

The Valiant-Vazirani Isolation Lemma 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 with the property that
(i) every satisfying assignments 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 also unsatisfiable.
The Valiant-Vazirani procedure is *randomized*,
and when *C* is satisfiable it produces a uniquely satisfiable
circuit *C'* with probability Ω(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 is in P/poly.
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 formula.

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.