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.