✦ LIBER ✦

Derandomizing Chebyshev's inequality to find independent sets in uncrowded hypergraphs

✍ Scribed by Andrés D. Fundia

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 817 KB
Volume: 8
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199603)8:2<131::aid-rsa4>3.0.co;2-z

No coin nor oath required. For personal study only.

✦ Synopsis

In [l] it is proved that an uncrowded (k + 1)-hypergraph of average degree t" contains an independent set of size (cnlt)(ln t ) ' l k . We present a polynomial time algorithm that finds such an independent set by derandomizing the original probabilistic proof. The technique that we use can be applied to derandomize other random algorithms that use several random variables having sufficiently small variances.