Computing the Partition Function for Cliques in a Graph

by Alexander Barvinok

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(n14) 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]