3 Search Results for "Backens, Miriam"

Document
DOI: 10.4230/LIPIcs.MFCS.2020.36
The Complexity of Approximating the Complex-Valued Potts Model

Authors: Andreas Galanis, Leslie Ann Goldberg, and Andrés Herrera-Poyatos

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q ≥ 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations.
Cite as

Andreas Galanis, Leslie Ann Goldberg, and Andrés Herrera-Poyatos. The Complexity of Approximating the Complex-Valued Potts Model. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{galanis_et_al:LIPIcs.MFCS.2020.36,
  author =	{Galanis, Andreas and Goldberg, Leslie Ann and Herrera-Poyatos, Andr\'{e}s},
  title =	{{The Complexity of Approximating the Complex-Valued Potts Model}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.36},
  URN =		{urn:nbn:de:0030-drops-127038},
  doi =		{10.4230/LIPIcs.MFCS.2020.36},
  annote =	{Keywords: approximate counting, Potts model, Tutte polynomial, partition function, complex numbers}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.12
A Complete Dichotomy for Complex-Valued Holant^c

Authors: Miriam Backens

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holant^c denotes a subfamily of those problems, where any function set considered must contain the two unary functions pinning inputs to values 0 or 1. The complexity classification of Holant problems usually takes the form of dichotomy theorems, showing that for any set of functions in the family, the problem is either #P-hard or it can be solved in polynomial time. Previous such results include a dichotomy for real-valued Holant^c and one for Holant^c with complex symmetric functions, i.e. functions which only depend on the Hamming weight of the input. Here, we derive a dichotomy theorem for Holant^c with complex-valued, not necessarily symmetric functions. The tractable cases are the complex-valued generalisations of the tractable cases of the real-valued Holant^c dichotomy. The proof uses results from quantum information theory, particularly about entanglement. This full dichotomy for Holant^c answers a question that has been open for almost a decade.
Cite as

Miriam Backens. A Complete Dichotomy for Complex-Valued Holant^c. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{backens:LIPIcs.ICALP.2018.12,
  author =	{Backens, Miriam},
  title =	{{A Complete Dichotomy for Complex-Valued Holant^c}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.12},
  URN =		{urn:nbn:de:0030-drops-90168},
  doi =		{10.4230/LIPIcs.ICALP.2018.12},
  annote =	{Keywords: computational complexity, counting complexity, Holant problems, dichotomy, entanglement}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.16
A New Holant Dichotomy Inspired by Quantum Computation

Authors: Miriam Backens

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Holant problems are a framework for the analysis of counting complexity problems on graphs. This framework is simultaneously general enough to encompass many counting problems on graphs and specific enough to allow the derivation of dichotomy results, partitioning all problems into those which are in FP and those which are #P-hard. The Holant framework is based on the theory of holographic algorithms, which was originally inspired by concepts from quantum computation, but this connection appears not to have been explored before. Here, we employ quantum information theory to explain existing results in a concise way and to derive a dichotomy for a new family of problems, which we call Holant^+. This family sits in between the known families of Holant^*, for which a full dichotomy is known, and Holant^c, for which only a restricted dichotomy is known. Using knowledge from entanglement theory -- both previously existing work and new results of our own -- we prove a full dichotomy theorem for Holant^+, which is very similar to the restricted Holant^c dichotomy and may thus be a stepping stone to a full dichotomy for that family.
Cite as

Miriam Backens. A New Holant Dichotomy Inspired by Quantum Computation. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{backens:LIPIcs.ICALP.2017.16,
  author =	{Backens, Miriam},
  title =	{{A New Holant Dichotomy Inspired by Quantum Computation}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.16},
  URN =		{urn:nbn:de:0030-drops-74383},
  doi =		{10.4230/LIPIcs.ICALP.2017.16},
  annote =	{Keywords: computational complexity, counting complexity, Holant, dichotomy, entanglement}
}
  • Refine by Author
  • 2 Backens, Miriam
  • 1 Galanis, Andreas
  • 1 Goldberg, Leslie Ann
  • 1 Herrera-Poyatos, Andrés

  • Refine by Classification
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 2 computational complexity
  • 2 counting complexity
  • 2 dichotomy
  • 2 entanglement
  • 1 Holant
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2017
  • 1 2018
  • 1 2020

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