Deconstructing Luby

by Prabhakar Ragde

Published in the Volume 22, Number 2, Spring 1991 issue of SIGACT News.

[All phrases are taken from the FOCS 89 papers by Berger and Rompel; Berger, Rompel, and Shor; and Motwani, Naor, and Naor. The title is not.]
one can and cannot use
a trick used by Luby
the one used by Luby
obtaining the expected
Luby's method to make
what is desired
behavior of the greedy
still adhering
Luby's techniques
take advantage of the freedom
brute force is too
possible with the Luby
give ourselves a fighting chance
observe that Luby