A simple proof of the Isolation Lemma

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.

1. Use the notation $S_w$ rather than $S_0$, since $S_0$ depends on $w$.
2. Strengthen the statement of first item of the claim by asserting that the (single) minimal set is $S_w$.
3. 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.