Derandomizing Algorithms


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.

Pairwise Independence and Derandomization (406K)
Michael Luby, Avi Wigderson
ICSI Tech Report No. TR-95-035, July 1995.
UC Berkeley Tech Report UCB/CSD-95-880, July 1995.

On Deterministic Approximation of DNF (250K)
Michael Luby, Boban Velickovic
Preliminary version in 23rd STOC, 1991, pp. 430-438.
Final version in Algorithmica, Vol. 16, No. 4/5, Oct/Nov 1996, pp. 415-433.

Deterministic Approximate Counting of Depth-2 Circuits (177K)
Michael Luby, Avi Wigderson, Boban Velickovic
Proceedings of the Second Israeli Symposium on Theory of Computing and Systems, 1993, pp. 18-24.

Approximations of General Independent Distributions (168K)
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic
24th STOC, 1992.

Efficient Approximation of Product Distributions (235K)
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic
accepted to Random Structures and Algorithms, February 1998.

Efficient construction of a small hitting set for combinatorial rectangles in high dimension (172K)
Nati Linial, Michael Luby, Michael Saks, David Zuckerman
25th STOC, 1993.