Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems --geometric problems and computations; G.3 [Probability and Statistics] --probabilistic algorithms (including Monte Carlo)

General Terms: Algorithms

Additional Key Words and Phrases: Convex sets, random walks, sampling, volume

Selected papers that cite this one

- Russ Bubley and Martin Dyer. Faster random generation of linear extensions. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 350-354, San Francisco, California, 25-27 January 1998.

- Russ Bubley and Martin Dyer. Path coupling: a technique for proving rapid mixing in Markov chains. In 38th Annual Symposium on Foundations of Computer Science, pages 223-231, Miami Beach, Florida, 20-22 October 1997. IEEE.

- Russ Bubley, Martin Dyer, and Catherine Greenhill. Beating the 2\Delta bound for approximately counting colourings: A computer-assisted proof of rapid mixing. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 355-363, San Francisco, California, 25-27 January 1998.

- Jin-Yi Cai and Ajay P. Nerurkar. An improved worst-case to average-case connection for lattice problems (extended abstract). In 38th Annual Symposium on Foundations of Computer Science, pages 468-477, Miami Beach, Florida, 20-22 October 1997. IEEE.

- P. Diaconis and L. Saloff-Coste. What do we know about the Metropolis algorithm? Journal of Computer and System Sciences, 57(1):20-36, August 1998.

- Persi Diaconis and Laurent Saloff-Coste. What do we know about the Metropolis algorithm? In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 112-129, Las Vegas, Nevada, 29 May-1 June 1995.

- Martin Dyer, Alan Frieze, and Mark Jerrum. Approximately counting Hamilton paths and cycles in dense graphs. SIAM Journal on Computing, 27(5):1262-1272, October 1998.

- Martin Dyer, Peter Gritzmann, and Alexander Hufnagel. On the complexity of computing mixed volumes. SIAM Journal on Computing, 27(2):356-400, March 1998.

- Ravi Kannan and Guangxing Li. Sampling according to the multivariate normal density. In 37th Annual Symposium on Foundations of Computer Science, pages 204-212, Burlington, Vermont, 14-16 October 1996. IEEE.

- Ravi Kannan and Santosh Vempala. Sampling lattice points. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 696-700, El Paso, Texas, 4-6 May 1997.

- David R. Karger. A randomized fully polynomial time approximation scheme for the all terminal network reliability problem. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 11-17, Las Vegas, Nevada, 29 May-1 June 1995.

- Ji\v{r}í Matou\v{s}ek. Derandomization in computational geometry. Journal of Algorithms, 20(3):545-580, May 1996.

- Sanjeev Saluja, K. V. Subrahmanyam, and Madhukar N. Thakur. Descriptive complexity of #P functions. Journal of Computer and System Sciences, 50(3):493-505, June 1995.

- Santosh Vempala. A random sampling based algorithm for learning the intersection of half-spaces (extended abstract). In 38th Annual Symposium on Foundations of Computer Science, pages 508-513, Miami Beach, Florida, 20-22 October 1997. IEEE.

- D. Zuckerman. Simulating BPP using a general weak random source. Algorithmica, 16(4/5):367-391, October/November 1996.

Selected references

- Imre Bárány and Zoltán Füredi. Computing the volume is difficult. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 442-447, Berkeley, California, 28-30 May 1986.

- Andrei Z. Broder. How hard is to marry at random? (On the approximation of the permanent). In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 50-58, Berkeley, California, 28-30 May 1986.

- Mark Jerrum and Alistair Sinclair. Conductance and the rapid mixing property for Markov chains: the approximation of the permanent resolved (preliminary version). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 235-244, Chicago, Illinois, 2-4 May 1988.

- Richard M. Karp and Michael Luby. Monte-Carlo algorithms for enumeration and reliability problems. In 24th Annual Symposium on Foundations of Computer Science, pages 56-64, Tucson, Arizona, 7-9 November 1983. IEEE.

- Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82(1):93-133, July 1989.