Monte Carlo Algorithms for Hard Counting Problems


Monte-Carlo Algorithms for Enumeration and Reliability Problems
Richard Karp, Michael Luby
24th STOC, 1983, pp. 56-64.

Monte-Carlo Approximation Algorithms for Enumeration Problems
Richard Karp, Michael Luby, Neal Madras
J. of Algorithms, Vol. 10, No. 3, Sept. 1989, pp. 429-448.

Monte-Carlo Methods for Estimating System Reliability
Michael Luby,
Ph.D. thesis, U.C. Berkeley, September 1983.

Monte-Carlo Algorithms for the Planar Multiterminal Network Reliability Problem
Richard Karp, Michael Luby
J. of Complexity, 1, pp. 45-64, 1985.

A Monte-Carlo Algorithm for Estimating the Permanent (189K)
Narindra Karmarkar, Richard Karp, Richard Lipton, Laslo Lovasz, Michael Luby
SIAM J. on Computing, 1993, Vol. 22, No. 2, pp. 284-293.

Polytopes, Permanents and Graphs with Large Factors
Paul Dagum, Michael Luby, Milena Mihail, Umesh Vazirani
29th FOCS, 1988.

Approximating the Permanent of Graphs with Large Factors (333K)
Paul Dagum, Michael Luby
Theretical Computer Science, Part A, Vol. 102, Nov. 1992, pp. 283-305.

A Survey of Approximation Algorithms for the Permanent
Michael Luby
Proceedings of the Advanced International Workshop on Sequences:
Combinatorics, Compression, Security and Transmission
, Springer-Verlag, 1988.

Approximating the Number of Solutions to a GF[2] Formula (134K)
Marek Karpinski, Michael Luby
Preliminary version in 2nd Annual Symposium on Discrete Algorithms, 1991.
Final version in Journal of Algorithms, Vol. 14, No. 2, March 1993, pp. 280-287.

Markov Chain Algorithms for Planar Lattice Structures
Michael Luby, Dana Randall, Alistair Sinclair
36th FOCS, 1995, pp. 150-159.

Approximately Counting Up To Four (177K)
Michael Luby, Eric Vigoda
To appear in 29th STOC, May 1997.