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.