New Proof of the Isolation Lemma

The isolation lemma of Mulmuley, Vazirani and Vazirani says that if we take random weights for elements in a set system, with high probability there will be a unique set of minimum weight. Mulmuley et al. use the isolation lemma to randomly reduce matching to computing the determinant. The isolation lemma also gives an alternative proof to Valiant-Vazirani that show how to randomly reduce NP-complete problems to ones with a unique solution.

Noam Ta-Shma, an Israeli high school student (and son of Amnon), recently posted a new proof of the isolation lemma. The MVV proof is not particularly complicated but it does require feeling very comfortable with independent random variables. Ta-Shma's proof is a more straight-forward combinatorial argument.

Suppose you have a set system over a universe of n elements. Give each element i, a weight w_i uniformly chosen between 1 and m. The weight of a set is the sum of the weights of the elements of that set. Ta-Shma shows that there is a unique minimum weighted set with probability at least (1-1/m)ⁿ, which beats out the bound of (1-n/m) given by MVV.

Here is a sketch of his proof: Suppose all the w_i's had weights between 2 and m. Let S be the lexicographically minimal weight set given these weights. Consider the function φ(w), defined on weights with all the w_i at least 2, as the following:

• φ(w)_i = w_i -1 if i is in S
• φ(w)_i = w_i if i is not in S

Note that S is the unique minimal set now in the weights φ(w)_i. Moreover φ is 1-1 for we can recover w from φ(w) by taking the unique minimal weight set in φ(w) and adding one to the weight of each element in that set.

So we have the probability that random weights yield a unique minimum set is at least

|range(φ)|/mⁿ = |domain(φ)|/mⁿ = (m-1)ⁿ/mⁿ = (1-1/m)ⁿ.

Read all the details in Ta-Shma's paper.