2026-07-21T20:03:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23525 2025-10-02T12:57:46Z ddc:004 open_access

Holant* Dichotomy on Domain Size 3: A Geometric Perspective Cai, Jin-Yi Ihm, Jin Soo Holant problem Complexity dichotomy Higher domain Holant problems are a general framework to study the computational complexity of counting problems. It is a more expressive framework than counting constraint satisfaction problems (CSP) which are in turn more expressive than counting graph homomorphisms (GH). In this paper, we prove the first complexity dichotomy of Holant^*₃(ℱ) where ℱ is an arbitrary set of symmetric, real valued constraint functions on domain size 3. We give an explicit tractability criterion and prove that, if ℱ satisfies this criterion then Holant^*₃(ℱ) is polynomial time computable, and otherwise it is #P-hard, with no intermediate cases. We show that the geometry of the tensor decomposition of the constraint functions plays a central role in the formulation as well as the structural internal logic of the dichotomy. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jin-Yi Cai and Jin Soo Ihm 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.148 urn:nbn:de:0030-drops-235254 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.148 eng https://creativecommons.org/licenses/by/4.0/legalcode