## 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.