Impossibility of Derandomizing the Isolation Lemma for all Families

by Manindra Agrawal, Rohit Gurjar, and Thomas Thierauf

Oded's comments

This text provides a nice survey to the limitations of derandomizing the isolation lemma.

The original abstract

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

Available from ECCC TR20-098.

Back to list of Oded's choices.