7 Search Results for "Backens, Miriam"

Document
DOI: 10.4230/LIPIcs.CCC.2025.23
From an Odd Arity Signature to a Holant Dichotomy

Authors: Boning Meng, Juqiu Wang, Mingji Xia, and Jiayi Zheng

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Holant is an essential framework in the field of counting complexity. For over fifteen years, researchers have been clarifying the complexity classification for complex-valued Holant on Boolean domain, a challenge that remains unresolved. In this article, we prove a complexity dichotomy for complex-valued Holant on Boolean domain when a non-trivial signature of odd arity exists. This dichotomy is based on the dichotomy for #EO, and consequently is an FP^NP vs. #P dichotomy as well, stating that each problem is either in FP^NP or #P-hard. Furthermore, we establish a generalized version of the decomposition lemma for complex-valued Holant on Boolean domain. It asserts that each signature can be derived from its tensor product with other signatures, or conversely, the problem itself is in FP^NP. We believe that this result is a powerful method for building reductions in complex-valued Holant, as it is also employed as a pivotal technique in the proof of the aforementioned dichotomy in this article.
Cite as

Boning Meng, Juqiu Wang, Mingji Xia, and Jiayi Zheng. From an Odd Arity Signature to a Holant Dichotomy. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{meng_et_al:LIPIcs.CCC.2025.23,
  author =	{Meng, Boning and Wang, Juqiu and Xia, Mingji and Zheng, Jiayi},
  title =	{{From an Odd Arity Signature to a Holant Dichotomy}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{23:1--23:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.23},
  URN =		{urn:nbn:de:0030-drops-237177},
  doi =		{10.4230/LIPIcs.CCC.2025.23},
  annote =	{Keywords: Complexity dichotomy, Counting, Holant problem, #P}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.118
P-Time Algorithms for Typical #EO Problems

Authors: Boning Meng, Juqiu Wang, and Mingji Xia

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this article, we study the computational complexity of counting weighted Eulerian orientations, denoted as #EO. This problem is considered a pivotal scenario in the complexity classification for Holant, a counting framework of great significance. Our results consist of three parts. First, we prove a complexity dichotomy theorem for #EO defined by a set of binary and quaternary signatures, which generalizes the previous dichotomy for the six-vertex model. Second, we prove a dichotomy for #EO defined by a set of so-called pure signatures, which possess the closure property under gadget construction. Finally, we present a polynomial-time algorithm for #EO defined by specific rebalancing signatures, which extends the algorithm for pure signatures to a broader range of problems, including #EO defined by non-pure signatures such as f_40. We also construct a signature f_56 that is not rebalancing, and whether #EO(f_56) is computable in polynomial time remains open.
Cite as

Boning Meng, Juqiu Wang, and Mingji Xia. P-Time Algorithms for Typical #EO Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 118:1-118:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{meng_et_al:LIPIcs.ICALP.2025.118,
  author =	{Meng, Boning and Wang, Juqiu and Xia, Mingji},
  title =	{{P-Time Algorithms for Typical #EO Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{118:1--118:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.118},
  URN =		{urn:nbn:de:0030-drops-234953},
  doi =		{10.4230/LIPIcs.ICALP.2025.118},
  annote =	{Keywords: Counting complexity, Eulerian orientation, Holant, #P-hardness, Dichotomy theorem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.7
Parameterised Holant Problems

Authors: Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth, and Johannes Schmitt

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We investigate the complexity of parameterised holant problems p-Holant(𝒮) for families of symmetric signatures 𝒮. The parameterised holant framework has been introduced by Curticapean in 2015 as a counter-part to the classical and well-established theory of holographic reductions and algorithms, and it constitutes an extensive family of coloured and weighted counting constraint satisfaction problems on graph-like structures, encoding as special cases various well-studied counting problems in parameterised and fine-grained complexity theory such as counting edge-colourful k-matchings, graph-factors, Eulerian orientations or, more generally, subgraphs with weighted degree constraints. We establish an exhaustive complexity trichotomy along the set of signatures 𝒮: Depending on the signatures, p-Holant(𝒮) is either 1) solvable in "FPT-near-linear time", i.e., in time f(k)⋅ 𝒪̃(|x|), or 2) solvable in "FPT-matrix-multiplication time", i.e., in time f(k)⋅ {𝒪}(n^{ω}), where n is the number of vertices of the underlying graph, but not solvable in FPT-near-linear time, unless the Triangle Conjecture fails, or 3) #W[1]-complete and no significant improvement over the naive brute force algorithm is possible unless the Exponential Time Hypothesis fails. This classification reveals a significant and surprising gap in the complexity landscape of parameterised Holants: Not only is every instance either fixed-parameter tractable or #W[1]-complete, but additionally, every FPT instance is solvable in time (at most) f(k)⋅ {𝒪}(n^{ω}). We show that there are infinitely many instances of each of the types; for example, all constant signatures yield holant problems of type (1), and the problem of counting edge-colourful k-matchings modulo p is of type (p) for p ∈ {2,3}. Finally, we also establish a complete classification for a natural uncoloured version of parameterised holant problem p-UnColHolant(𝒮), which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of p-UnColHolant(𝒮) is different: Depending on 𝒮 all instances are either solvable in FPT-near-linear time, or #W[1]-complete, that is, there are no instances of type (2).
Cite as

Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth, and Johannes Schmitt. Parameterised Holant Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aivasiliotis_et_al:LIPIcs.ICALP.2025.7,
  author =	{Aivasiliotis, Panagiotis and G\"{o}bel, Andreas and Roth, Marc and Schmitt, Johannes},
  title =	{{Parameterised Holant Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.7},
  URN =		{urn:nbn:de:0030-drops-233842},
  doi =		{10.4230/LIPIcs.ICALP.2025.7},
  annote =	{Keywords: holant problems, counting problems, parameterised algorithms, fine-grained complexity theory, homomorphisms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.86
Eulerian Orientations and Hadamard Codes: A Novel Connection via Counting

Authors: Shuai Shao and Zhuxiao Tang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We discover a novel connection between two classical mathematical notions, Eulerian orientations and Hadamard codes by studying the counting problem of Eulerian orientations (#EO) with local constraint functions imposed on vertices. We present two special classes of constraint functions and a chain reaction algorithm, and show that the #EO problem defined by each class alone is polynomial-time solvable by the algorithm. These tractable classes of functions are defined inductively, and quite remarkably the base level of these classes is characterized perfectly by the well-known Hadamard code. Thus, we establish a novel connection between counting Eulerian orientations and coding theory. We also prove a #P-hardness result for the #EO problem when constraint functions from the two tractable classes appear together.
Cite as

Shuai Shao and Zhuxiao Tang. Eulerian Orientations and Hadamard Codes: A Novel Connection via Counting. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 86:1-86:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{shao_et_al:LIPIcs.ITCS.2025.86,
  author =	{Shao, Shuai and Tang, Zhuxiao},
  title =	{{Eulerian Orientations and Hadamard Codes: A Novel Connection via Counting}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{86:1--86:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.86},
  URN =		{urn:nbn:de:0030-drops-227146},
  doi =		{10.4230/LIPIcs.ITCS.2025.86},
  annote =	{Keywords: Eulerian orientations, Hadamard codes, Counting problems, Tractable classes}
}
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.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.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.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 Type
  • 7 Document/PDF
  • 4 Document/HTML

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

  • Refine by Author
  • 2 Backens, Miriam
  • 2 Meng, Boning
  • 2 Wang, Juqiu
  • 2 Xia, Mingji
  • 1 Aivasiliotis, Panagiotis
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Problems, reductions and completeness
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Complexity classes
  • Show More...

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

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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