Search Results

Documents authored by Xia, Mingji

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
DOI: 10.4230/LIPIcs.STACS.2011.249
The Complexity of Weighted Boolean #CSP Modulo k

Authors: Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer $k>1$. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k.
Cite as

Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia. The Complexity of Weighted Boolean #CSP Modulo k. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 249-260, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.STACS.2011.249,
  author =	{Guo, Heng and Huang, Sangxia and Lu, Pinyan and Xia, Mingji},
  title =	{{The Complexity of Weighted Boolean #CSP Modulo k}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{249--260},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.249},
  URN =		{urn:nbn:de:0030-drops-30158},
  doi =		{10.4230/LIPIcs.STACS.2011.249},
  annote =	{Keywords: #CSP, dichotomy theorem, counting problems, computational complexity}
}
Document
Extended Abstract
DOI: 10.4230/LIPIcs.STACS.2008.1368
A Theory for Valiant's Matchcircuits (Extended Abstract)

Authors: Angsheng Li and Mingji Xia

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
The computational function of a matchgate is represented by its character matrix. In this article, we show that all nonsingular character matrices are closed under matrix inverse operation, so that for every $k$, the nonsingular character matrices of $k$-bit matchgates form a group, extending the recent work of Cai and Choudhary (2006) of the same result for the case of $k=2$, and that the single and the two-bit matchgates are universal for matchcircuits, answering a question of Valiant (2002).
Cite as

Angsheng Li and Mingji Xia. A Theory for Valiant's Matchcircuits (Extended Abstract). In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 491-502, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.STACS.2008.1368,
  author =	{Li, Angsheng and Xia, Mingji},
  title =	{{A Theory for Valiant's Matchcircuits}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{491--502},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1368},
  URN =		{urn:nbn:de:0030-drops-13686},
  doi =		{10.4230/LIPIcs.STACS.2008.1368},
  annote =	{Keywords: Pfaffian, Matchgate, Matchcircuit}
}
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