Computing the Partition Function for Cliques in a Graph
Theory of Computing, Volume 11(13), pp. 339-355, 2015
Bibliography with links to cited articles
[1] Robert Azencott: Simulated annealing. Astérisque, 1987/88(161-162):223–237, 1988. Séminaire Bourbaki 30 No. 697. Available at Numdam.
[2] Antar Bandyopadhyay and David Gamarnik: Counting without sampling: A symptotics of the log-partition function for certain statistical physics models. Random Structures & Algorithms, 33(4):452–479, 2008. [doi:10.1002/rsa.20236]
[3] Alexander Barvinok: Computing the permanent of (some) complex matrices. Foundations of Computational Mathematics, pp. 1–14, 2015. [doi:10.1007/s10208-014-9243-7, arXiv:1405.1303]
[4] Alexander Barvinok and Pablo Soberón: Computing the partition function for graph homomorphisms with multiplicities. J. Combinat. Theory, Ser. A, 137:1–26, 2016. [doi:10.1016/j.jcta.2015.08.001, arXiv:1410.1842]
[5] Alexander Barvinok and Pablo Soberón: Computing the partition function for graph homomorphisms. Combinatorica, to appear. [arXiv:1406.1771]
[6] Mohsen Bayati, David Gamarnik, Dimitriy Katz, Chandra Nair, and Prasad Tetali: Simple deterministic approximation algorithms for counting matchings. In Proc. 39th STOC, pp. 122–127, New York, 2007. ACM Press. [doi:10.1145/1250790.1250809]
[7] Aditya Bhaskara: Finding Dense Structures in Graphs and Matrices. Ph. D. thesis, Princeton University, 2012. Available at author’s website.
[8] Aditya Bhaskara, Moses Charikar, Eden Chlamtác, Uriel Feige, and Aravindan Vijayaraghavan: Detecting high log-densities – an O(n1∕4) approximation for densest k-subgraph. In Proc. 42nd STOC, pp. 201–210, New York, 2010. ACM Press. [doi:10.1145/1806689.1806719, arXiv:1001.2891]
[9] Boris Bukh: Personal communication, 2015.
[10] Andrei A. Bulatov and Martin Grohe: The complexity of partition functions. Theoret. Comput. Sci., 348(2-3):148–186, 2005. Preliminary version in ICALP’04. [doi:10.1016/j.tcs.2005.09.011]
[11] Uriel Feige, Guy Kortsarz, and David Peleg: The dense k-subgraph problem. Algorithmica, 29(3):410–421, 2001. [doi:10.1007/s004530010050]
[12] Alan Frieze and Ravi Kannan: Quick approximation to matrices and applications. Combinatorica, 19(2):175–220, 1999. [doi:10.1007/s004930050052]
[13] Oded Goldreich, Shafi Goldwasser, and Dana Ron: Property testing and its connection to learning and approximation. J. ACM, 45(4):653–750, 1998. Preliminary versions in FOCS’96 and ECCC. [doi:10.1145/285055.285060]
[14] Johan Håstad: Clique is hard to approximate within n1-ϵ. Acta Mathematica, 182(1):105–142, 1999. Preliminary version in FOCS’96. [doi:10.1007/BF02392825]
[15] Ole J. Heilmann and Elliott H. Lieb: Theory of monomer-dimer systems. Comm. Math. Phys., 25(3):190–232, 1972. Available at project euclid. [doi:10.1007/BF01877590]
[16] Mark Jerrum and Alistair Sinclair: Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput., 22(5):1087–1116, 1993. Preliminary version in ICALP’90. [doi:10.1137/0222066]
[17] Pieter Willem Kasteleyn: Dimer statistics and phase transitions. J. Math. Phys., 4(2):287–293, 1963. [doi:10.1063/1.1703953]
[18] Tsung-Dao Lee and Chen-Ning Yang: Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model. Phys. Rev., 87(3):410–419, 1952. [doi:10.1103/PhysRev.87.410]
[19] László Lovász and Michael D. Plummer: Matching Theory. AMS Chelsea Publishing, Providence, RI, corrected reprint of the 1986 original edition, 2009.
[20] Alexander D. Scott and Alan D. Sokal: The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma. J. Stat. Phys., 118(5-6):1151–1261, 2005. [doi:10.1007/s10955-004-2055-4, arXiv:cond-mat/0309352]
[21] Dror Weitz: Counting independent sets up to the tree threshold. In Proc. 38th STOC, pp. 140–149, New York, 2006. ACM Press. [doi:10.1145/1132516.1132538]
[22] Chen-Ning Yang and Tsung-Dao Lee: Statistical theory of equations of state and phase transitions. I. Theory of condensation. Phys. Rev., 87(3):404–409, 1952. [doi:10.1103/PhysRev.87.404]
[23] David Zuckerman: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(6):103–128, 2007. Preliminary version in STOC’06. [doi:10.4086/toc.2007.v003a006]