ECCC-Report TR20-098https://eccc.weizmann.ac.il/report/2020/098Comments and Revisions published for TR20-098en-usSun, 05 Jul 2020 09:22:25 +0300
Paper TR20-098
| Impossibility of Derandomizing the Isolation Lemma for all Families |
Rohit Gurjar,
Thomas Thierauf,
Manindra Agrawal
https://eccc.weizmann.ac.il/report/2020/098The Isolation Lemma states that when random weights are assigned to the elements of a finite set $E$, then in any given family of subsets of $E$, exactly one set has the minimum weight, with high probability. In this note, we present two proofs for the fact that it is impossible to efficiently derandomize the Isolation Lemma for arbitrary families.
The first proof is from Chari, Rohatgi and Srinivasan and uses the potential method. An alternate proof is due to the first author of this note. It uses the polynomial method. However, it is not written anywhere. The main purpose of this note is to present that proof. Additionally we show that the above lower bounds are almost tight with respect to various parameters.
Sun, 05 Jul 2020 09:22:25 +0300https://eccc.weizmann.ac.il/report/2020/098