CS Paper Radar

The Computational Complexity of Holant Problems on 4-regular Graphs from the Stable Subgroup Sequence of $SL(2,\mathbb{C})$

Yuan Huang, Zhiguo Fu

cs.CC ·submitted 2026-09-10 07:22 UTC · v1
theory

Abstract

The Holant framework provides a general setting for studying counting problems and includes graph homomorphisms (\#GH) and counting constraint satisfaction problems (\#CSP) as special cases. Over the past twenty years, a series of computational complexity dichotomies have been established for Holant problems, but the classification for complex-valued signatures is still open. The main obstacle is the case in which all signatures have even arity. In this paper, we establish a dichotomy for Holant problems with a complex-valued 4-ary signature, which is a key base case for the full classification of Holant problems. We present a new strategy by introducing Schur's theorem, the classification of finite subgroups of $\mathrm{SL}(2,\mathbb{C})$ and stable subgroup sequences into the proof. These new techniques are of independent interest.

Closest papers

Nearest neighbours by meaning across the whole index.

A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems

cs.CC ·2026-09-06 ·Chenghua Liu, Boning Meng, Juqiu Wang
theory similarity 0.72
Abstract · 98 pages; proof and exposition revised, Lean repository linked

A Boolean Holant problem evaluates a graph partition function specified by local signatures at its vertices. We prove a complexity dichotomy for arbitrary finite sets of algebraic complex-valued signatures on general graphs: an explicit, decidable criterion characterizes the polynomial-time cases, and every remaining case is $\#\mathsf{P}$-hard under polynomial-time Turing reductions. The proof resolves the all-even case by constructing signatures with nonzero endpoints and all remaining support on the central layer, then classifying them according to half their arity. Binary transfer groups and matching-product reconstruction provide the main tools in the small- and large-height cases, respectively.

0.24

From a finite subgroup of $SO(3)$:$C_2$ leads to a Holant dichotomy

cs.CC cs.CLcs.DM ·2026-11-18 ·Yuxuan Zhou
theory similarity 0.70
Abstract

Counting complexity within the Holant framework has been extensively studied through complexity dichotomy theorems. While substantial progress has been achieved for various restricted settings, the general complex-valued even-arity case without auxiliary unary signatures remains largely open. This paper studies a fundamental case in this program where the binary signatures induce a group structure satisfying \(M(B(\mathcal{F}))\cong C_2\). It is observed that projective equivalence classes of binary signature matrices naturally embed into finite subgroups of \(SO(3)\), providing an algebraic viewpoint for structural classification. This paper further identifies two fundamentally different regimes for the \(C_2\) case, namely the normal and isotropic cases, and analyzes their complexity behavior separately. Combining gadget constructions, decomposition techniques, interpolation arguments, and a realnumberization approach that transforms the complex-valued setting into an equivalent real-structured framework, this paper establishes a complete dichotomy theorem: for every even-arity signature set \(\mathcal{F}\) satisfying \(M(\B(\mathcal{F}))\cong C_2\), the problem \(\mathrm{Holant}(\mathcal{F})\) is either polynomial-time computable or \#P-hard. A Pauli-basis representation for signatures is further introduced as an algebraically natural language for organizing realizable signatures and revealing structural relations that are less transparent in the standard basis.

0.24

A Dichotomy for Complex Boolean Holant with Binary Disequality

cs.CC ·2026-08-31 ·Chenghua Liu, Boning Meng
similarity 0.69
Abstract · 242 pages; proof and exposition revised, corrections made, Lean repository linked

We classify Boolean Holant problems with a supplied binary disequality signature and an arbitrary fixed finite set of algebraic complex-valued signatures. Each problem is polynomial-time computable or $\#\mathsf{P}$-hard, and the tractability criterion is decidable. The proof combines arity reduction with the growth of the available binary transfer group and uses stable pairs to recover the structure of higher-arity signatures. We also prove a dichotomy for the disequality-edge model when the signature set contains an endpoint-nondegenerate irreducible eight-vertex signature, resolving the corresponding arity-four cases in the main proof.

0.33

Group Action and Spin Representation Lead to a Holant* Complexity Dichotomy on Domain Size 3

cs.CC ·2026-10-03 ·Jin-Yi Cai, Jin Soo Ihm
theory similarity 0.67
Abstract

We prove a complexity dichotomy theorem for $\mathrm{Holant}^*$ problems over complex-valued symmetric constraint functions $\mathcal{F}$ on domain size $3$. We give a decidable tractability criterion and prove that if $\mathcal{F}$ satisfies the criterion, then $\mathrm{Holant}^*(\mathcal{F})$ is solvable in polynomial time, and otherwise it is #P-hard. This is the first Holant dichotomy for a set of complex-valued constraint functions on higher domains. We show that complex-valued constraint functions have a rich structure not observed in real-valued constraint functions. This structure is only revealed when we analyze them in a bipartite Holant setting with a non-standard bilinear form and provides the backbone to the proof of the dichotomy. We use group actions and the spin representation of $\mathrm{SL}(2, \mathbb{C})$ in $\mathrm{SO}(3, \mathbb{C})$ and the generalized orthogonal group to facilitate this analysis. We also introduce $\textit{frames}$ and $\textit{shells}$. Frames linearize the group action and provide a unified framework for proving #P-hardness when used in conjunction with shells. Furthermore, we characterize the lower dimensional constraint functions by $\textit{annihilators}$, which makes it possible to analyze $\textit{essentially Boolean domain}$ functions in domain size $3$.

0.18

A Dichotomy for Cubic Bipartite Holant Problems with Complex Algebraic Weights

cs.CC ·2026-09-27 ·Yin Liu
similarity 0.65
Abstract · 87 pages. Supplementary polynomial certificates and verification code included. Corrected author metadata; manuscript unchanged

We classify the exact evaluation of $\operatorname{Holant}(f\mid=_3)$ for every fixed complex algebraic symmetric Boolean ternary signature $f$. An input is a cubic bipartite multigraph: every vertex on one side carries $f$, every vertex on the other side carries ternary equality, and no auxiliary signatures are freely available. The tractable signatures are precisely rank-one tensors, generalized equalities, and equality-preserving cube-root diagonal transformations of six affine signatures, together with nonzero scalings and reversal. Every other signature gives a $\#\mathrm{P}$-hard problem under polynomial-time Turing reductions. We also identify the exact real intersection: it consists of the same tractable families as in the rational classification, with real algebraic parameters. The proof preserves degree exactly three on both sides of every oracle instance. A rank-one matrix extracted by interpolation supplies one unary signature only after its unused factor has been absorbed in triples. Over the complex numbers this absorption has three exceptional projective directions. We combine this constraint with projective matrix-group orbits, explicit ternary replacements, and an exhaustive treatment of finite projective orders. The cases of orders three and five include exact polynomial certificates; the certificate identities and a rational-arithmetic verifier are supplied as supplementary material.

0.13

A Dichotomy for Boolean Complex Holant Problems with Conjugate-Closed Signature Sets

cs.CC ·2026-09-11 ·Jincheng Guan, Shuai Shao, Zhuxiao Tang
theory similarity 0.60
Abstract · 96 pages, 3 figures

We study Boolean Holant problems with complex-valued signature sets closed under conjugation. Such sets arise naturally in tensor-network expressions for classical strong simulation of quantum circuits. We prove a complexity dichotomy for such problems with an explicit tractability criterion. This extends the dichotomy for real-valued Holant problems, with the same four tractability conditions. Our proofs use Xia's projective binary group framework and quantum entanglement theory. The conjugate closure assumption precisely makes $k$-uniformity, directly applicable to the classification of Holant problems, by realizing reduced density matrices via Holant gadgets. We also use the classification of absolutely maximally entangled states to resolve a particular $6$-ary obstruction in our inductive proof of the \#P-hardness.

0.27

Lettericity Is NP-Complete

cs.CC cs.DM ·2026-09-23 ·Henning Fernau, Samuel German, Kevin Mann, Nils Morawietz
theory similarity 0.55
Abstract · After we first posted this paper on arXiv, Vatter posted a proof that Lettericity is NP-complete which he obtained independently of ours (ar…

The lettericity of a graph $G$ is the smallest size of a set $Σ$ such that there exist $w_1, \ldots, w_{|V(G)|} \in Σ$ and a so-called decoder $D \subseteq Σ^2$ for which $G$ is isomorphic to the letter graph $(\{1, \ldots, |V(G)|\}, \{ij : 1 \le i < j \le |V(G)|, w_iw_j \in D\})$. It took around two decades of the study of lettericity for, in the simpler case of paths, a closed-form expression for its lettericity to be derived; this suggests that the question of whether the lettericity of an arbitrary graph can be computed in polynomial time is nontrivial. Indeed, this question has been raised repeatedly as an open problem in recent literature. We solve this problem by showing that the lettericity problem on arbitrary graphs is NP-complete. We also show that each of the natural ways in which a single part of a structure $(Σ, w_1, \ldots, w_{|V(G)|}, D)$ witnessing the lettericity could be constrained corresponds to an NP-complete problem, which resolves an additional three open problems from the literature; in particular, we show that the coloring extension, word extension, and decoder extension problems are NP-complete. Additionally, we use the reduction in the NP-completeness proof to give a lower bound on algorithms for lettericity under the Exponential Time Hypothesis (ETH): unless the ETH is false, there cannot exist a deterministic algorithm to decide whether the lettericity of an $n$-vertex graph is at most $k$ in time $2^{o(n)}$, even when $n = 6k$. Finally, we complement the known result that Lettericity is fixed-parameter tractable when parameterized by the standard parameter $k$ by providing a fixed-parameter algorithm with respect to the dual parameterization by $n-k$ running in $2^{\mathcal{O}((n-k)^2)} + \mathcal{O}(n)$ time.

0.39

Maltsev Constraint Satisfaction Problems and Deterministic Logspace With Counting

cs.CC ·2026-09-25 ·Dejan Delic, Ali Syed
theoryhot direction similarity 0.55
Abstract

In this article, we prove that the problem of solving $\operatorname{CSP}(\mathbf{A})$, where $\mathbf{A}$ is a finite relational template which admits a Maltsev polymorphism is in a specific complexity class DET, which is related to the complexity of computing the determinant of a matrix with integer entries. Such a class is intimately related to well-studied MOD-logspace classes in the theory of computational complexity. To prove this fact, we develop a new algorithm for solving syntactically simple binary instances of Maltsev constraint satisfaction problems, rather different from the well-known Bulatov-Dalmau algorithm, which does not require the explicit use or knowledge of a Maltsev polymorphism of the template but, rather, utilizes a graph whose vertices are 2-generated subuniverses of $\mathbb{A}$, where $\mathbb{A}$ is the Maltsev algebra parametrizing $\operatorname{CSP}(\mathbf{A})$. The theoretical importance of this algorithm is reflected in two facts: (1) it places the problem $ \operatorname{CSP}(\mathbf{A})$ in a complexity class related to the deterministic logspace with counting, which, in itself, has a strong connection to a variety of standard algorithmic problems in linear algebra, and (2) it only makes use of the relational structure of the template without the need for the explicit use of a compatible Maltsev polymorphism, depending entirely on the strong ``symmetry" of constraints compatible with such polymorphisms and the knowledge of 2-generated subuniverses of $\mathbb{A}$.

0.51