# Isolation lemma

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Isolation_lemma
> Markdown URL: https://mediated.wiki/source/Isolation_lemma.md
> Source: https://en.wikipedia.org/wiki/Isolation_lemma
> Source revision: 1334599690
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [theoretical computer science](/source/Theoretical_computer_science), the term **isolation lemma** (or **isolating lemma**) refers to [randomized algorithms](/source/Randomized_algorithm) that reduce the number of solutions to a problem to one, should a solution exist. This is achieved by constructing random constraints such that, with non-negligible probability, exactly one solution satisfies these additional constraints if the solution space is not empty. Isolation lemmas have important applications in computer science, such as the [Valiant–Vazirani theorem](/source/Valiant%E2%80%93Vazirani_theorem) and [Toda's theorem](/source/Toda's_theorem) in [computational complexity theory](/source/Computational_complexity_theory).

The first isolation lemma was introduced by Valiant & Vazirani (1986), albeit not under that name. Their isolation lemma chooses a random number of random hyperplanes, and has the property that, with non-negligible probability, the intersection of any fixed non-empty solution space with the chosen hyperplanes contains exactly one element. This suffices to show the [Valiant–Vazirani theorem](/source/Valiant%E2%80%93Vazirani_theorem): there exists a randomized [polynomial-time reduction](/source/Polynomial-time_reduction) from the [satisfiability problem for Boolean formulas](/source/Boolean_satisfiability_problem) to the problem of detecting whether a Boolean formula has a unique solution. Mulmuley, Vazirani & Vazirani (1987) introduced an isolation lemma of a slightly different kind: Here every coordinate of the solution space gets assigned a random weight in a certain range of integers, and the property is that, with non-negligible probability, there is exactly one element in the solution space that has minimum weight. This can be used to obtain a randomized [parallel algorithm](/source/Parallel_algorithm) for the [maximum matching](/source/Maximum_matching) problem.

Stronger isolation lemmas have been introduced in the literature to fit different needs in various settings. For example, the isolation lemma of Chari, Rohatgi & Srinivasan (1993) has similar guarantees as that of Mulmuley et al., but it uses fewer random bits. In the context of the [exponential time hypothesis](/source/Exponential_time_hypothesis), Calabro et al. (2008) prove an isolation lemma for [k-CNF formulas](/source/Boolean_satisfiability_problem). Noam Ta-Shma[1] gives an isolation lemma with slightly stronger parameters, and gives non-trivial results even when the size of the weight domain is smaller than the number of variables.

## The isolation lemma of Mulmuley, Vazirani, and Vazirani

- **Lemma.** Let n and N be positive integers, and let \mathcal F be an arbitrary nonempty family of subsets of the universe \{1,\dots,n\}. Suppose each element x\in\{1,\dots,n\} in the universe receives an integer weight w(x), each of which is chosen independently and uniformly at random from \{1,\dots,N\}. The weight of a set *S* in \mathcal F is defined as - w(S) = \sum_{x \in S} w(x)\,.
- Then, with probability at least 1-n/N, there is a *unique* set in \mathcal F that has the minimum weight among all sets of \mathcal F.

It is remarkable that the lemma assumes nothing about the nature of the family \mathcal F: for instance \mathcal F may include *all* 2^n-1 nonempty subsets. Since the weight of each set in \mathcal F is between 1 and nN on average there will be (2^n-1) / (nN) sets of each possible weight. Still, [with high probability](/source/With_high_probability), there is a unique set that has minimum weight.

### Mulmuley, Vazirani, and Vazirani's proof

Suppose we have fixed the weights of all elements except an element *x*. Then *x* has a *threshold* weight *α*, such that if the weight *w*(*x*) of *x* is greater than *α*, then it is not contained in any minimum-weight subset, and if w(x) \le \alpha, then it is contained in some sets of minimum weight. Further, observe that if w(x) < \alpha, then *every* minimum-weight subset must contain *x* (since, when we decrease *w(x)* from *α*, sets that do not contain *x* do not decrease in weight, while those that contain *x* do). Thus, ambiguity about whether a minimum-weight subset contains *x* or not can happen only when the weight of *x* is exactly equal to its threshold; in this case we will call *x* "singular". Now, as the threshold of *x* was defined only in terms of the weights of the *other* elements, it is independent of *w(x)*, and therefore, as *w*(*x*) is chosen uniformly from {1, …, *N*},

- \Pr[x\text{ is singular}] = \Pr[w(x) = \alpha] \le 1/N

and the probability that *some* *x* is singular is at most *n/N*. As there is a unique minimum-weight subset [iff](/source/Iff) no element is singular, the lemma follows.

Remark: The lemma holds with \le (rather than =) since it is possible that some *x* has no threshold value (i.e., *x* will not be in any minimum-weight subset even if *w*(*x*) gets the minimum possible value, 1).

### Joel Spencer's proof

This is a restatement version of the above proof, due to [Joel Spencer](/source/Joel_Spencer) (1995).[2]

For any element *x* in the set, define

- \alpha(x) = \min_{S \in \mathcal F, x \not\in S}w(S) - \min_{S\in\mathcal F, x\in S}w(S\setminus\{x\}).

Observe that \alpha(x) depends only on the weights of elements other than *x*, and not on *w*(*x*) itself. So whatever the value of \alpha(x), as *w*(*x*) is chosen uniformly from {1, …, *N*}, the probability that it is equal to \alpha(x) is at most 1/*N*. Thus the probability that w(x) = \alpha(x) for *some* *x* is at most *n/N*.

Now if there are two sets *A* and *B* in \mathcal F with minimum weight, then, taking any *x* in *A\B*, we have

- \begin{align} \alpha(x) &= \min_{S \in \mathcal F, x \not\in S}w(S) - \min_{S\in\mathcal F, x\in S}w(S\setminus\{x\}) \\ &= w(B) - (w(A)-w(x)) \\ &= w(x), \end{align}

and as we have seen, this event happens with probability at most *n/N*.

## Examples/applications

- The original application was to minimum-weight (or maximum-weight) perfect matchings in a graph. Each edge is assigned a random weight in {1, …, 2*m*}, and \mathcal F is the set of perfect matchings, so that with probability at least 1/2, there exists a unique [perfect matching](/source/Perfect_matching). When each indeterminate x_{ij} in the [Tutte matrix](/source/Tutte_matrix) of the graph is replaced with 2^{w_{ij}} where w_{ij} is the random weight of the edge, we can show that the determinant of the matrix is nonzero, and further use this to find the matching.
- More generally, the paper also observed that any search problem of the form "Given a set system (S,\mathcal F), find a set in \mathcal F" could be reduced to a decision problem of the form "Is there a set in \mathcal F with total weight at most *k*?". For instance, it showed how to solve the following problem posed by Papadimitriou and Yannakakis, for which (as of the time the paper was written) no deterministic polynomial-time algorithm is known: given a graph and a subset of the edges marked as "red", find a perfect matching with exactly *k* red edges.
- The [Valiant–Vazirani theorem](/source/Valiant%E2%80%93Vazirani_theorem), concerning unique solutions to NP-complete problems, has a simpler proof using the isolation lemma. This is proved by giving a randomized reduction from [CLIQUE](/source/Clique_problem) to UNIQUE-CLIQUE.[3]
- Ben-David, Chor & Goldreich (1989) use the proof of Valiant-Vazirani in their search-to-decision reduction for [average-case complexity](/source/Average-case_complexity).
- [Avi Wigderson](/source/Avi_Wigderson) used the isolation lemma in 1994 to give a randomized reduction from [NL](/source/NL_(complexity)) to UL, and thereby prove that NL/poly ⊆ ⊕L/poly.[4] Reinhardt and Allender later used the isolation lemma again to prove that NL/poly = UL/poly.[5]
- The book by Hemaspaandra and Ogihara has a chapter on the isolation technique, including generalizations.[6]
- The isolation lemma has been proposed as the basis of a scheme for [digital watermarking](/source/Digital_watermarking).[7]
- There is ongoing work on derandomizing the isolation lemma in specific cases[8] and on using it for identity testing.[9]

## Notes

1. Noam Ta-Shma (2015); [*A simple proof of the Isolation Lemma*](http://eccc.hpi-web.de/report/2015/080/), in *eccc*

1. Jukna (2001)

1. Mulmuley, Vazirani & Vazirani (1987)

1. Wigderson (1994)

1. Reinhardt & Allender (2000)

1. Hemaspaandra & Ogihara (2002)

1. Majumdar & Wong (2001)

1. Arvind & Mukhopadhyay (2008)

1. Arvind, Mukhopadhyay & Srinivasan (2008)

## References

- Arvind, V. & Mukhopadhyay, Partha (2008). [*Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size*](http://portal.acm.org/citation.cfm?id=1429791.1429816). Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques. Boston, MA, USA: Springer-Verlag. pp. 276–289. [arXiv:0804.0957](https://arxiv.org/abs/0804.0957). [Bibcode:2008arXiv0804.0957A](https://ui.adsabs.harvard.edu/abs/2008arXiv0804.0957A). ISBN 978-3-540-85362-6. Retrieved 2010-05-10.
- Arvind, V.; Mukhopadhyay, Partha; Srinivasan, Srikanth (2008). [*New Results on Noncommutative and Commutative Polynomial Identity Testing*](http://portal.acm.org/citation.cfm?id=1380843.1380966). Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity. IEEE Computer Society. pp. 268–279. [arXiv:0801.0514](https://arxiv.org/abs/0801.0514). [Bibcode:2008arXiv0801.0514A](https://ui.adsabs.harvard.edu/abs/2008arXiv0801.0514A). ISBN 978-0-7695-3169-4. Retrieved 2010-05-10.
- Ben-David, S.; Chor, B.; Goldreich, O. (1989). *On the theory of average case complexity*. Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89. p. 204. [doi:10.1145/73007.73027](https://doi.org/10.1145/73007.73027). ISBN 0897913078.
- Calabro, C.; Impagliazzo, R.; Kabanets, V.; Paturi, R. (2008). "The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs". *Journal of Computer and System Sciences*. **74** (3): 386. [doi:10.1016/j.jcss.2007.06.015](https://doi.org/10.1016/j.jcss.2007.06.015)
- Chari, S.; Rohatgi, P.; Srinivasan, A. (1993). *Randomness-optimal unique element isolation, with applications to perfect matching and related problems*. Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93. p. 458. [doi:10.1145/167088.167213](https://doi.org/10.1145/167088.167213). [hdl:1813/6129](https://hdl.handle.net/1813/6129). ISBN 0897915917.
- Hemaspaandra, Lane A. & Ogihara, Mitsunori (2002). ["Chapter 4. The Isolation Technique"](https://archive.org/details/complexitytheory0000hema). *The complexity theory companion*. Springer. ISBN 978-3-540-67419-1.
- Majumdar, Rupak & Wong, Jennifer L. (2001). *Watermarking of SAT using combinatorial isolation lemmas*. Proceedings of the 38th annual Design Automation Conference. Las Vegas, Nevada, United States: ACM. pp. 480–485. [CiteSeerX 10.1.1.16.9300](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.9300). [doi:10.1145/378239.378566](https://doi.org/10.1145/378239.378566). ISBN 1-58113-297-2.
- Reinhardt, K. & Allender, E. (2000). ["Making Nondeterminism Unambiguous"](ftp://128.6.25.4/http/pub/allender/nlul.pdf). Vol. 29, no. 4. p. 1118. [doi:10.1137/S0097539798339041](https://doi.org/10.1137/S0097539798339041)
- Mulmuley, Ketan; Vazirani, Umesh; Vazirani, Vijay (1987). "Matching is as easy as matrix inversion". *Combinatorica*. **7** (1): 105–113. [CiteSeerX 10.1.1.70.2247](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.70.2247). [doi:10.1007/BF02579206](https://doi.org/10.1007/BF02579206)
- Jukna, Stasys (2001). [*Extremal combinatorics: with applications in computer science*](https://web.archive.org/web/20110716131718/http://lovelace.thi.informatik.uni-frankfurt.de/%7Ejukna/EC_Book/index.html). Springer. pp. 147–150. ISBN 978-3-540-66313-3. Archived from [the original](http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/EC_Book/index.html) on 2011-07-16. Retrieved 2010-05-09.
- Valiant, L. & Vazirani, V. (1986). ["NP is as easy as detecting unique solutions"](http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf). *Theoretical Computer Science*. **47**: 85–93. [doi:10.1016/0304-3975(86)90135-0](https://doi.org/10.1016/0304-3975(86)90135-0)
- Wigderson, Avi (1994). [*NL/poly ⊆ ⊕L/poly*](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W94/proc.pdf). Proceedings of the 9th Structures in Complexity Conference. pp. 59–62.

## External links

- [Favorite Theorems: Unique Witnesses](http://blog.computationalcomplexity.org/2006/09/favorite-theorems-unique-witnesses.html) by [Lance Fortnow](/source/Lance_Fortnow)
- [The Isolation Lemma and Beyond](http://rjlipton.wordpress.com/2009/07/01/the-isolation-lemma-and-beyond/) by [Richard J. Lipton](/source/Richard_J._Lipton)

---
Adapted from the Wikipedia article [Isolation lemma](https://en.wikipedia.org/wiki/Isolation_lemma) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Isolation_lemma?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.