A simple proof of the Isolation Lemma.
Noam Ta-Shma · Electronic colloquium on computational complexity · 2015
We give a new simple proof for the Isolation Lemma, with slightly better parameters, that also gives non-trivial results even when the weight domain m is smaller than the number of variables n. 1 The lemma and its proof Let n,m be two natural numbers, F ⊆ P([n]), where [n] = {1, . . . , n} and P([n]) is the set of all subsets of [n]. A weight function is a function w : [n] → [m]. Given a weight function w, we extend it to sets by defining the weight of a set to be the sum of the weights of its elements, i.e., w(S) = ∑ x∈S w(x). Let minw(F) be the family of sets with the smallest weight amongst F with respect to w, i.e., minw(F) = {A ∈ F | w(A) is minimal} . When |minw(F)| = 1 the minimum weight under w is attained uniquely. Mulmuley, Vazirani and Vazirani [MVV87] proved: Theorem 1. [MVV87] (The isolation lemma original version) For every F ⊆ P([n]), Pr w:[n]→[m] (|minw(F)| = 1) ≥ 1− n m , where the probability is over w that is uniformly distributed over all functions from [n] to [m]. We give a new proof for the isolation lemma with slightly better parameters. Unlike Theorem 1 our proof gives non-trivial results even when m ≤ n: Theorem 2. For every F ⊆ P([n]), Pr w:[n]→[m] (|minw(F)| = 1) ≥ ( 1− 1 m )n . Proof. Fix a family F ⊆ P([n]). W.l.o.g. no set S ∈ F is a superset of another set T ∈ F , as the weight of S is always strictly bigger than the weight of T and thus S never affects whether there is a unique minimum or not and therefor we can drop it. Let W = {w : [n]→ [m]} denote the set of all weight functions and W>1 = {w : [n]→ {2, . . . ,m}} denote the set of all weight functions that assign each element a weight that is strictly larger than 1. We ∗Ironi D High School, Tel-Aviv, ISRAEL. Email: [email protected].