Approximately counting up to four (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximately counting up to four (extended abstract)

Full text

Pdf (939 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 682 - 687

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Michael Luby	Digital Equipment Corporation, Systems Research Center, Pato Alto, CA and Computer Science Division, University of California at Berkeley
Eric Vigoda	Computer science Division, University of California at Berkeley and International Computer Science Institute

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 34, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/258533.258663 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D.J. Aldous. Random walks on finite groups and rapidly mixing Markov chains. In Seminaire de Probabilites XVII, pages 243-297. Springer-Vefiag, 1983. Lecture Notes in Math. 986.
	2	J. van den Berg and J.E. Steif. Percolation and the hard-core lattice gas model. Stochastic Processes and their Applications, 49:179-197, 1994.
	3	Russ Bubley and Martin Dyer. Path coupling, Dobrushin uniqueness, and approximate counting. Preprint, 1996.
	4	Russ Bubley, Martin Dyer, and Mark Jerrum. A new approach to polynomial-time generation of random points in convex bodies. Technical Report 343, Edinburgh University, 1996.
	5	Neil J. Calkin , Herbert S. Wilf, The Number of Independent Sets in a Grid Graph, SIAM Journal on Discrete Mathematics, v.11 n.1, p.54-60, Feb. 1998 [doi>10.1137/S089548019528993X]
	6	J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
	7	Mark Jerrum, A very simple algorithm for estimating the number of k-colorings of a low-degree graph, Random Structures & Algorithms, v.7 n.2, p.157-165, September 1995 [doi>10.1002/rsa.3240070205]
	8	M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
	9	Richard M. Karp and Michael Luby. Monte-Carlo algorithms for enumeration and reliability problems. In 24th AnnualSymposium on Foundations of Computer Science, pages 56-64, Tucson, Arizona, 7-9 November 1983. IEEE.
	10	Frank Kelly. Loss networks. Annals of Applied Probability, 1(3):319-378, 1991.
	11	Graham Louth. Stochastic Networks: Complexity, dependence, and routing. PhD thesis, Univ. Cambridge, 1990.
	12	M. Luby , D. Randall , A. Sinclair, Markov chain algorithms for planar lattice structures, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.150, October 23-25, 1995
	13	Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62233]
	14	Alistair Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Verlag, Basel, Switzerland, 1993
	15	Salil Vadhan. The complexity of counting. Undergraduate Thesis, Harvard University, 1995.

CITED BY 6

	Mark Huber, Exact sampling and approximate counting techniques, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.31-40, May 24-26, 1998, Dallas, Texas, United States
	Martin Dyer , Catherine Greenhill, The complexity of counting graph homomorphisms (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.246-255, January 09-11, 2000, San Francisco, California, United States
	Antar Bandyopadhyay , David Gamarnik, Counting without sampling: new algorithms for enumeration problems using statistical physics, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.890-899, January 22-26, 2006, Miami, Florida
	Dror Weitz, Counting independent sets up to the tree threshold, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Martin Dyer , Leslie Ann Goldberg , Catherine Greenhill , Gabriel Istrate , Mark Jerrum, Convergence of the Iterated Prisoner's Dilemma Game, Combinatorics, Probability and Computing, v.11 n.2, p.135-147, March 2002
	Antar Bandyopadhyay , David Gamarnik, Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models, Random Structures & Algorithms, v.33 n.4, p.452-479, December 2008