## A simple proof of the Isolation Lemma

by Noam Ta-Shma

#### Oded's comments

The proof may not be simpler than the standard one (and no such claim is
made), but it is definitely simple and nice, let alone that it gives better
parameters and offers a different perspective.

The presentation is very nice, almost perfect. In light of the latter fact,
I would suggest the following three minor edits.

- Use the notation $S_w$ rather than $S_0$,
since $S_0$ depends on $w$.
- Strengthen the statement of first item of the claim
by asserting that the (single) minimal set is $S_w$.
- When proving the first item,
clarify that $w\in W_{>1}$ is fixed and recall that $w'=\phi(w)$.
Also, replace "for all $S_0 \neq S \in {\cal F}$
by "for all $S\in{\cal F}$ s.t. $S\neq S_w$".

#### The original abstract

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

See ECCC TR15-080.

Back to
list of Oded's choices.