Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-098 | 4th July 2020 06:39

Impossibility of Derandomizing the Isolation Lemma for all Families

RSS-Feed




TR20-098
Authors: Manindra Agrawal, Rohit Gurjar, Thomas Thierauf
Publication: 5th July 2020 09:22
Downloads: 1329
Keywords: 


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.



ISSN 1433-8092 | Imprint