Document Open Access Logo

Computational Complexity and Partition Functions (Invited Talk)

Author Leslie Ann Goldberg

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.1.pdf
  • Filesize: 294 kB
  • 3 pages

Document Identifiers

Author Details

Leslie Ann Goldberg
  • Department of Computer Science, University of Oxford, Oxford, UK

Funding

The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) ERC grant agreement no. 334828. The paper reflects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.

Cite AsGet BibTex

Leslie Ann Goldberg. Computational Complexity and Partition Functions (Invited Talk). In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 1:1-1:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.STACS.2019.1

Abstract

This paper is an extended abstract of my STACS 2019 talk "Computational Complexity and Partition Functions".

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • partition functions
  • approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Barvinok. Combinatorics and Complexity of Partition Functions. Algorithms and Combinatorics. Springer International Publishing, 2017. Google Scholar
  2. A. I. Barvinok. Computing the Permanent of (Some) Complex Matrices. Foundations of Computational Mathematics, 16(2):329-342, 2016. Google Scholar
  3. M. Bayati, D. Gamarnik, D. A. Katz, C. Nair, and P. Tetali. Simple deterministic approximation algorithms for counting matchings. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 122-127, 2007. Google Scholar
  4. Ferenc Bencs and Péter Csikvári. Note on the zero-free region of the hard-core model. arXiv e-prints, page arXiv:1807.08963, July 2018. URL: http://arxiv.org/abs/1807.08963.
  5. I. Bezáková, A. Galanis, L. A. Goldberg, and D. Štefankovič. Inapproximability of the independent set polynomial in the complex plane. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1234-1240, 2018. Full version available from URL: https://arxiv.org/abs/1711.00282.
  6. Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic. The complexity of approximating the matching polynomial in the complex plane. CoRR, abs/1807.04930, 2018. URL: http://arxiv.org/abs/1807.04930.
  7. Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič. Inapproximability of the Independent Set Polynomial Below the Shearer Threshold. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 28:1-28:13, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.28.
  8. Nicholas J. A. Harvey, Piyush Srivastava, and Jan Vondrák. Computing the Independence Polynomial: from the Tree Threshold down to the Roots. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1557-1576, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.102.
  9. O. J. Heilmann and E. H. Lieb. Theory of monomer-dimer systems. Communications in Mathematical Physics, 25(3):190-232, 1972. Google Scholar
  10. M. Jerrum and A. Sinclair. Approximating the Permanent. SIAM J. Comput., 18(6):1149-1178, 1989. Google Scholar
  11. Viresh Patel and Guus Regts. Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials. SIAM J. Comput., 46(6):1893-1919, 2017. URL: http://dx.doi.org/10.1137/16M1101003.
  12. Han Peters and Guus Regts. On a conjecture of Sokal concerning roots of the independence polynomial. CoRR, abs/1701.08049, 2017. URL: http://arxiv.org/abs/1701.08049.
  13. A. Sinclair, P. Srivastava, D. Štefankovič, and Y. Yin. Spatial mixing and the connective constant: optimal bounds. Probability Theory and Related Fields, 168(1):153-197, 2017. Google Scholar
  14. Allan Sly and Nike Sun. Counting in two-spin models on d-regular graphs. Ann. Probab., 42(6):2383-2416, November 2014. URL: http://dx.doi.org/10.1214/13-AOP888.
  15. Piyush Srivastava. Approximating the hard core partition function with negative activities. Manuscript, available at https://www.its.caltech.edu/~piyushs/, April 2015.
  16. Dror Weitz. Counting Independent Sets Up to the Tree Threshold. In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC '06, pages 140-149, New York, NY, USA, 2006. ACM. URL: http://dx.doi.org/10.1145/1132516.1132538.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact