## Parallel and Distributed Computation

*A Simple Parallel Algorithm for the Maximal Independent Set Problem*

Michael Luby

Preliminary version in **17th STOC**, 1985.

Final version in **SIAM J. on Computing**,
November 1986, Vol. 15, No. 4, pp. 1036-1053.

*Removing Randomness in Parallel Computation Without a Processor Penalty*
(412K)

Michael Luby

Preliminary version in **29th FOCS**, 1988.

Final version in **JCSS**, Vol. 47, No. 2, 1993, pp. 250-286.

*Efficient PRAM Simulation on a Distributed Memory Machine*
(315K)

Richard Karp, Michael Luby, Friedhelm Meyer auf de Heide

Preliminary version in **24th STOC**, 1992.

Final version in **Algorithmica**, Vol. 16,
No. 4/5, Oct/Nov 1996, pp. 517-542.

*A Parallel Approximation Algorithm for Positive Linear Programming*
(158K)

Michael Luby, Noam Nisan

**25th STOC**, 1993.

*A Simple Parallel Algorithm for Finding a Satisfying Truth Assignment
to a 2-CNF Formula*

Stephen Cook, Michael Luby

**Information Processing Letters**, Vol. 27, March 1988, pp. 141-145.

*Network Decomposition and Locality in Distributed Computation*
(227K)

Baruch Awerbuch, Andrew Goldberg, Michael Luby, Serge Plotkin

**30th FOCS**, 1989.