Abstract 1 Introduction 2 Preliminaries 3 New notations and our results 4 Conclusion References

P-Time Algorithms for Typical #EO Problems

Boning Meng111First authors. ORCID Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
University of Chinese Academy of Sciences, Beijing, China
Juqiu Wang111First authors. ORCID Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
University of Chinese Academy of Sciences, Beijing, China
Mingji Xia111First authors. ORCID Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
University of Chinese Academy of Sciences, Beijing, China
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 f40. We also construct a signature f56 that is not rebalancing, and whether #EO(f56) is computable in polynomial time remains open.

Keywords and phrases:
Counting complexity, Eulerian orientation, Holant, #P-hardness, Dichotomy theorem
Category:
Track A: Algorithms, Complexity and Games
Copyright and License:
[Uncaptioned image] © Boning Meng, Juqiu Wang, and Mingji Xia; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Problems, reductions and completeness
Related Version:
Full Version: https://arxiv.org/abs/2410.11557 [39]
Acknowledgements:
We sincerely thank Yicheng Pan for providing a simplified proof of a lemma in the full version.
Funding:
All authors are supported by National Key R&D Program of China (2023YFA1009500), NSFC 61932002 and NSFC 62272448.
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

In fields such as statistical physics, economics, machine learning, and combinatorics, the role of counting problems is becoming increasingly significant. Three well-founded frameworks have been put forth for the study of the complexity of counting problems: #GH, #CSP, and Holant. These frameworks are capable of expressing a wide range of natural counting problems and are of great significance in counting complexity. For example, counting vertex covers in a graph can be expressed in #GH, while counting perfect matchings is a Holant problem. The definitions of these frameworks are as follows; see [9, Section 1.2] and [16, section 2.1] for details. In this paper, we always restrict the variables in these counting problems to the Boolean domain, where each variable can only take values in {0,1}, by default.

We begin by introducing some basic concepts. A Boolean variable takes values from a Boolean domain consisting of two symbols {0,1}. Sometimes we treat it as 𝔽2, the finite field of size 2, to characterize special tractable classes.

A signature f with r variables is a mapping from {0,1}r to . The value of f on an input α is denoted as fα or f(α). The set of all variables of f is denoted by Var(f), and its size by arity(f).

Definition 1 (#GH).

A counting weighted graph homomorphisms problem #GH() parameterized by a binary signature f is as the following: The input is a directed graph222In this article, graphs refer to multigraphs. It is always permissible for self-loops and parallel edges to be present. G=(V,E). The output is

ZG=σ:V{0,1}(u,v)Ef(σ(u),σ(v))
Definition 2 (#CSP).

A counting constraint satisfaction problem #CSP() parameterized by a set is as the following: The input is an instance of #CSP(), which consists of a finite set of variables {x1,x2,,xn} and a finite set C of clauses. Each clause in C contains a signature f of arity k and a sequence of variables of length k (xi1,xi2,,xik) from {x1,x2,,xn} 333A variable can appear in the sequence more than one time.. The output is

x1,x2,,xn{0,1}(f,xi1,xi2,,xik)Cf(xi1,xi2,,xik)
Definition 3 (Holant).

A Holant problem Holant() parameterized by a set is as the following: The input is an signature grid Ω(G,π) over , denoted by I. Here, G is a graph and π:V×S(E(v)) assigns a signature fv of arity |E(v)| to v and a linear order to E(v) for each vV(G), where E(v) are the edges adjacent to v. The output is the partition function of Ω,

Z(I)=HolantΩ=σ:E(G){0,1}vV(G)fv(σ|E(v))

The bipartite Holant problem Holant(𝒢) is a Holant problem over the signature grid (G,π), where G=(U,V,E) is a bipartite graph, and π assigns signatures from to vertices in U and signatures from 𝒢 to vertices in V.

The framework of Holant is capable of expressing counting weighted graph homomorphisms (#GH) and counting constraint satisfaction problems (#CSP). Consequently, Holant is widely regarded as one of the most general and significant frameworks in counting complexity.

Significant progress has been made in the study of #GH [38, 35, 29, 6, 28, 33, 12, 11], #CSP [6, 8, 27, 5, 22, 31, 34, 4, 7, 30, 25, 13, 10], #EO [19, 16, 43], and Holant [22, 23, 24, 21, 1, 26, 2, 37, 17, 42]. Moreover, the computational complexity of #GH and #CSP has been fully characterized by dichotomy theorems [12, 25]. In contrast, the complexity classification for Holant remains unresolved.

There have been several constructive attempts on Holant. A signature is said to be symmetric if all its values for inputs with the same number of 1’s are identical. A complete dichotomy is established when all signatures are symmetric [21]. When signatures are not restricted to be symmetric, a complete dichotomy has been proven for nonnegative-weighted signatures [37] and real-weighted signatures [42]. Additionally, dichotomies exist for several special forms of complex-weighted Holant, such as Holant [24], Holant+ [1], and Holantc [2], with some given auxiliary signatures.

Recently, counting weighted Eulerian orientation problems (#EO) have also attracted researchers’ attention, as real-weighted Holant can express #EO problems defined by signatures with the ARS property [16] under a holographic transformation by Z=12(11𝔦𝔦), while complex-weighted Holant can express #EO problems under the same transformation. The complexity classification for complex-weighted #EO problems remains open, and therefore this article seeks a more generalized characterization of #EO complexity.

1.1 Counting weighted Eulerian orientation

We first introduce the concept of #EO. We use HW< to denote the set of strings with fewer 1’s than 0’s. For example, 00110HW< since the number of 1’s (which is 2) is strictly less than the number of 0’s (which is 3). We similarly define HW=, HW, HW>, and HW. The support of a signature f, denoted supp(f), is the set of all inputs for which f is non-zero. If supp(f)HW=, we call f an EO signature.

For any Eulerian graph G, let EO(G) denote all Eulerian orientations of G. For a given orientation in EO(G), we assign 0 to the head and 1 to the tail of each edge. Therefore, a Eulerian orientation corresponds to an assignment to both ends of every edge, where for each vertex, the number of adjacent ends assigned 0 equals those assigned 1.

Definition 4 (#EO).

A #EO problem #EO() parameterized by a signature set of EO signatures is as the following: The input is an EO-signature grid Ω(G,π) over , denoted by I. Here, G is a Eulerian graph and π:V×S(E(v)) assigns a signature fv of arity |E(v)| to v and a linear order to E(v) for each vV(G), where E(v) are the edges adjacent to v. The output is the partition function of Ω,

Z(I)=#EOΩ=σEO(G)vVfv(σ|E(v)).

Several complexity results have been established for #EO. In [19], a complexity dichotomy was proved for a single complex-weighted quaternary signature, known as the six-vertex model dichotomy. This result was later extended to planar graphs in [18]. Furthermore, [16] established a complexity dichotomy for signatures satisfying the arrow reversal symmetry (ARS) property, a setting commonly assumed in physics.

There are two motivations for studying #EO problems. First, specific forms of #EO problems appear in many areas such as statistical physics and combinatorics. In statistical physics, both the ice-type model and the six-vertex model [41] are special cases of #EO problems. The latter model, in particular, has emerged as a prominent focus within statistical physics and corresponds exactly to #EO defined on 4-regular graphs. In combinatorics, the resolution of the Alternating Sign Matrix conjecture [3] and the evaluation of the Tutte polynomial at (3,3) [36] both relate to #EO problems defined on specific graphs with particular signatures.

Second, we conjecture that resolving #EO problems is essential for establishing the complete dichotomy for complex-weighted Holant problems. The significance of EO-signatures was first recognized in [21] during the study of vanishing signatures. Furthermore, [37] suggests that classifying #EO problems may complement the tensor decomposition lemma for complex-weighted signatures. Most directly, [42] demonstrates that research on corresponding #EO problems (defined by signatures with ARS property), initially conducted in [16], constitutes a crucial component of the proof for the real-weighted Holant dichotomy. Additionally, the eight-vertex model dichotomy presented in [15], where the problem is defined by a single quaternary signature whose support confined to HW={0000,1111}, builds upon the six-vertex model dichotomy in [19]. We believe that some fundamental obstacles to establishing complete complexity classifications for complex-weighted Holant problems lie hidden within complex-weighted #EO problems.

1.2 Our results

All results in this paper target and hold for complex-weighted #EO by default. The study begins with analyzing low-arity signatures, a prevalent research focus in counting problems. This approach is justified because an EO signature f with arity greater than 4 can generate various quaternary and binary signatures through gadget construction. Our first result is stated below, with its detailed version presented in Theorem 20.

Theorem 5.

Suppose is a finite set of EO signatures with arity less or equal than 4. Then #EO() is either polynomial time computable or #P-hard. The classification criterion is explicit.

To establish a complete complexity classification for #EO problems, we build upon Theorem 5 as a foundation. We note that the tractable cases exhibit a more complex structure compared to those in the six-vertex model dichotomy.

Our second result concerns pure signatures. For a set S of 01-strings with length k, the affine span of S is defined as the minimal affine subspace containing S. Given a signature f, we denote by Span(f) the affine span of its support supp(f). Given the affine span of a signature f’s support, we call f a pure-up (resp. pure-down) signature if it is contained in HW (resp. HW).

Our investigation originates from a quaternary signature f with supp(f)={1100,1010,1001}. Its affine span {1100,1010,1001,1111}HW motivates modifying f to f by assigning a nonzero value at input 1111. Building on [21]’s result that Holant(2[0,0,a,b,c])THolant(2[0,0,a,0,0]) (since HW> strings do not contribute to the partition function), we establish #EO(f)T#EO(f). This support augmentation technique fundamentally motivates our study of pure signatures. Notably, Theorem 6’s tractable cases generalize those in Theorem 5.

Theorem 6.

Suppose is a finite set of pure-up (pure-down) EO signatures. Then #EO() is either polynomial time computable or #P-hard. The classification criterion is explicit.

The detailed statement of Theorem 6 appear in Theorem 23. To achieve tractability, a condition called the type condition must be satisfied in Theorem 6. This condition also plays a crucial role in the subsequent algorithm. Additionally, we define a property called rebalancing. Intuitively, a signature f is 0-rebalancing (or 1-rebalancing) if fixing some of its variables to 0 (respectively 1) naturally forces an equal number of variables to be fixed to 1 (respectively 0). When both the type condition and rebalancing condition are satisfied, a polynomial-time algorithm becomes applicable. We emphasize that this algorithm represents the most significant algorithmic contribution of this paper. Our third result is stated below, with a formal version in Theorem 25.

Theorem 7.

#EO() is polynomial time computable, if every f is 0-rebalancing (or 1-rebalancing), and satisfies the type condition.

We note that very recently, and independently of our work, [43] proposed a polynomial-time algorithm for 01-weighted #EO parameterized by consisting of δ1-affine (resp. δ0-affine) signatures and affine signatures, termed the chain reaction algorithm. Moreover, [43] establishes a novel connection between the base level of δ1-affine and δ0-affine signatures (the δ1-affine and δ0-affine kernels) and the Hadamard code, while proving #P-hardness when δ1-affine and δ0-affine signatures are mixed. Although these results do not constitute a complete dichotomy and primarily apply to 0-1 weighted signatures, they capture some of the significant components of our dichotomy and prove highly valuable, as demonstrated in this work.

Furthermore, building upon this article and utilizing our dichotomy for pure signatures [40], a complete dichotomy for complex-weighted #EO has been established. However, this dichotomy is an FPNP versus #P dichotomy, indicating that #EO problems are either in FPNP or #P-hard. While this dichotomy provides valuable insights and partially clarifies the complexity classification, it does not yield new polynomial-time algorithms for #EO and consequently does not include our algorithm for rebalancing signatures.

1.3 Our methods

As presented in Section 1.2, this article contains three parts. In each part, our main objective is to characterize different classes of signature sets. Indeed, the principal difficulty lies in providing descriptions of tractable cases that are sufficiently precise to capture all tractable scenarios. Following this characterization, we separately prove both tractability and #P-hardness results.

In each part, we perform detailed characterizations of signature sets, including comprehensive classifications and rigorous examinations of their properties. Specifically, we focus on three key aspects: the closure property, the properties of the affine span, and signature reducibility.

We further summarize that each tractable case in this work must satisfy two requirements: the support requirement and the type requirement. The support requirement specifies that each signature’s support must possess a particular form. This specific form enables a receiving-sending mechanism that is necessary for implementing the corresponding algorithm. The type requirement states that after applying the receiving-sending mechanism to an instance, all resulting signatures must form a tractable case in #CSP. A detailed explanation appears in Section 3.

For the hardness results, we prove #P-hardness based on the dichotomies of both the six-vertex model and #CSP, primarily using the gadget construction method introduced in Section 2.3.

1.4 Organization

In Section 2, we introduce preliminaries needed in our proof. We present the detailed version of our main theorem in Section 3. We conclude our result in Section 4. Detailed proofs of theorems in Section 3 can be found in the full version [39].

2 Preliminaries

2.1 Definitions and notations

For a 01-string α, we use α¯ to denote the dual string of α, which is obtained by flipping every bit of α. For s{0,1}, we use #s(α) to denote the number of s’s in α. Under this notation we have:

HW=={α#1(α)=#0(α)},HW={α#1(α)#0(α)}.

A signature f is called a HW= signature (precisely an EO signature) if supp(f)HW=. The term “EO signature” was originally introduced in [16] as shorthand for Eulerian Orientation signature.

If supp(f)HW, we call f an HW signature. Other similar notations are defined analogously by replacing “” with “”, “<”, or “>” in both names and defining formulae.

We use [f0,f1,,fr] to denote a symmetric signature f of arity r, where fi gives the evaluation for all input strings with Hamming weight i.

By exchanging the values of the symbols in the Boolean domain, we obtain the dual signature f~=[f~0,f~1,,f~r]=[fr,fr1,,f0]. A signature f is called self-dual if f=f~. The concepts of “dual” and “self-dual” can be naturally generalized to asymmetric signatures, sets of signatures, Boolean domain counting problems, and tractable classes in dichotomy theorems.

We use [φ] to denote the truth value of a logical statement φ. It takes values from {True,False}, or equivalently the isomorphic integer set {1,0}. For example, [xy] equals True (or 1) when xy, and False (or 0) otherwise. Thus both [xy] and 2(x,y) represent the value of the binary function [0,1,0] evaluated at (x,y).

Several sets of frequently used signatures are defined as follows. Δ0 represents the unary signature [1,0], with its dual Δ1=[0,1]. The binary disequality signature [0,1,0] is denoted by 2 and serves as an example of self-dual signatures. We use 𝒬 to denote the set of equality signatures where 𝒬={=1,=2,,=r,}, with =r denoting an arity-r signature [1,0,,0,1]. In other words, =r evaluates to 1 when the input is all 0s or all 1s, and 0 otherwise.

A disequality signature of arity 2d, denoted by 2d, evaluates to 1 when x1=x2==xdxd+1=xd+2==x2d, and 0 otherwise. We define 𝒟𝒬={2,4,,2n,} as the set of all disequality signatures. Moreover, 𝒟𝒬 is closed under variable permutation. That is, for any πS2d, a signature f that evaluates to 1 when xπ(1)=xπ(2)==xπ(d)xπ(d+1)=xπ(d+2)==xπ(2d) (and 0 otherwise) is also considered a disequality signature.

An alternative definition states that a signature f is a disequality signature if: (1) it is an EO signature of arity 2d, (2) there exists αHW= such that supp(f){α,α¯}, and (3) f(α)=f(α¯)=1. The equivalence of these definitions can be readily verified. Similarly, a signature f is called a generalized disequality signature (denoted by 2da,b) if the signature satisfies (1), (2) and (3’) f(α)=a, f(α¯)=b.

We use to denote tensor multiplication. When no ambiguity arises, we sometimes use f to denote the signature set {f}. We use T and T to respectively denote polynomial-time Turing reductions and equivalences.

2.2 Relationships between counting problems

We say a framework A is more “general” than B, denoted as BA, if each problem in B can be transformed into a problem in A in polynomial time. The relationship between the counting frameworks are concluded in the following lemma.

Lemma 8.
#GH#CSP#EOHolant

Furthermore, Holant constitutes a strictly more expressive framework than #GH, as evidenced by the fact that while counting perfect matchings cannot be represented as a #GH problem [20], it can be formulated as a Holant problem.

Lemma 8 follows directly from Lemmas 912.

Lemma 9.

#GH(f)T#CSP({f}).

Lemma 10 ([16]).

#EO()THolant(2).

Lemma 11 ([42]).

Holant(2)THolant(Z1)

Lemma 12 ([16, Theorem 6.1]).

#CSP()T#EO(π()).

We now clarify the notation used in the preceding lemmas, which will also appear throughout this article. Here, Z1=12(1𝔦1𝔦), and Z1 denotes the signature set derived from via the holographic transformation defined by Z1 [44, 14].

While we omit both the formal definition of holographic transformations and the proof of this lemma since they are not central to our discussion, we strongly recommend readers consult [9][Section 1.3.2] for deeper understanding, as holographic transformations constitute a powerful technique in counting complexity theory.

Let f be an EO signature of arity 2d with variable set Var(f)={x1,x2,,x2d}. For any pairing P={{xi1,xi2},{xi3,xi4},,{xi2d1,xi2d}} of Var(f), we define EOP as the subset of {0,1}2d corresponding to P:

EOP={αα{0,1}2d,αi1αi2,,αi2d1αi2d},

equivalently expressed as EOP=supp([xi1xi2][xi3xi4][xi2d1xi2d]).

When supp(f)EOP, we call f an EOP signature relative to P. If such a pairing P exists, we call f a pairwise opposite signature (identical to Definition 5.5 in [16]), or simply an EOM signature.

For an EOP signature f with EOP=supp([xi1xi2][xi3xi4][xi2d1xi2d]), we define τf (or τ(f)) as the set of arity-d signatures satisfying:

τf={gg(xj1,xj3,,xj2d1)=f(xi1,1xi1,xi3,1xi3,,xi2d1,1xi2d1),
xj1{xi1,xi2},,xj2d1{xi2d1,xi2d}}.

Since P allows swapping variables within pairs, we have |τf|2d.

The inverse mapping π is defined for any arity-d signature g as:

πg(x1,y1,x2,y2,,xd,yd)=g(x1,x2,,xd)[x1y1][xdyd],

where πg (or π(g)) is clearly an EOP signature with P={{x1,y1},{x2,y2},,{xd,yd}}. Extending this to signature sets, we define π()={π(f)f}.

The set τ(π(g)) contains g and all signatures obtainable from g by variable flips using binary disequality. This establishes an equivalence between #EO and #CSP with free binary disequality. As established in [16], Lemma 12 comes from this observation and the complexity equivalence between #CSP and #CSP with free binary disequality.

2.3 Gadget construction and signature matrix

This subsection introduces two key concepts: gadget construction and signature matrices. Gadget construction serves as a fundamental reduction technique in complexity classification, while signature matrices offer an intuitive representation of signatures and reveal connections between gadget construction and matrix multiplication.

Given a signature set , an -gate resembles a signature grid Ω(G,π) from Definition 3, but with G=(V,E,D) where V represents vertices, E denotes internal edges (each connecting two vertices) and D denotes dangling edges (each connecting one vertex). An -gate essentially defines a signature whose variables correspond to edges in D. For |E|=n and |D|=m, with edges in E representing variables {x1,,xn} and edges in D representing {y1,,ym}, the -gate’s signature f satisfies:

f(y1,,ym)=σ:E{0,1}vVfv(σ^|E(v)D(v))

where (y1,,yn){0,1}n assigns values to dangling edge variables, σ^ extends σ with these assignments and fv denotes the signature at vertex v.

We say f is realizable from via gadget construction when f is an -gate’s signature. Crucially, when f is realizable from , [9, Lemma 1.3] establishes:

Holant()THolant({f})

For #EO problems, -gates have a modified definition. Since Lemma 10 shows #EO()THolant(2), we add 2 vertices to internal edges and treat the gadget as a standard Holant gate. Throughout this paper, -gates in #EO contexts follow this definition unless stated otherwise.

Next, we introduce the matrix form of signatures, which provides an orderly way to enumerate all possible values of a signature. Let f be an arbitrary signature mapping from {0,1}r to . First we fix an ordering of the variables as x1,x2,,xr. The matrix form of f (or signature matrix of f [9]) with parameter l is a 2l×2rl matrix for some integer 0lr, where the values of x1,x2,,xl determine the row index and the values of xl+1,xl+2,,xr determine the column index. This matrix is denoted by M(f)x1x2xl,xl+1xl+2xr. For convenience, we sometimes omit (f) and write simply Mx1xl,xl+1xr, or use the abbreviated form Mf when no ambiguity arises. For signatures with even arity, we typically choose l=r2.

Example 13 (Signature matrix).

If f is a binary signature and f=(f00,f01,f10,f11), then Mf=Mx1,x2=(f00f01f10f11).

If g is a quaternary signature, then

Mg=Mx1x2,x3x4=(g0000g0001g0010g0011g0100g0101g0110g0111g1000g1001g1010g1011g1100g1101g1110g1111).

We now establish the connection between matrix multiplication and gadget construction. Consider two -gates f and g with arities n and m respectively, where Var(f)={x1,x2,,xn} and Var(g)={y1,y2,,ym}. By connecting a subset of their dangling edges - specifically pairing {xnl+1,,xn} with {y1,y2,,yl} for some positive integer l, we construct a new -gate h.

The resulting signature h has variables Var(h)={x1,,xnl,yl+1,,ym}. Through direct comparison of gadget computation and matrix multiplication, we obtain:

Mh=Mx1xnl,yl+1ym=Mx1xnl,xnl+1xnMy1yl,yl+1ym=MfMg.

For #EO problems, the only modification is that edges now represent 2 instead of =2, yielding:

Mh=Mf2lMg.

This relationship will be frequently employed in subsequent discussions without further explanation.

We highlight two special forms of gadget construction: self-loop and pinning. In #EO problems, adding a self-loop to signature f involves selecting two variables x1 and x2 and connecting them with an internal edge, yielding new signature fx1x2. For Var(f)={x1,x2,,xn}, since the internal edge represents 2, we obtain:

fx1x2(x3,,xn)=f(0,1,x3,,xn)+f(1,0,x3,,xn).

This operation can be generalized using 2a,b. Instead of directly connecting x1 and x2, we introduce a new vertex assigned 2a,b and connect x1 and x2 to its dangling edges. The two possible connection orders yield either: f(x3,,xn)=af(0,1,x3,,xn)+bf(1,0,x3,,xn) or f(x3,,xn)=bf(0,1,x3,,xn)+af(1,0,x3,,xn).

Pinning represents the second key operation. While standard Holant and #CSP problems use Δ0=(1,0) or Δ1=(0,1) to fix variables, #EO problems employ 21,0 self-loops. For x,yVar(f), pinning simultaneously fixes x=1 and y=0, preserving the EO property. The resulting signature is denoted fx=1,y=0. Throughout this paper, “pinning signature” refers unambiguously to 21,0.

2.4 Two known dichotomies for #CSP and Six-vertex model

In this section, we introduce the dichotomies for #CSP and six-vertex model. We start from defining tractable classes 𝒜 and 𝒫. Let X be a (d+1)-dimensional column vector X=(x1,x2,,xd,1)T over 𝔽2. Suppose A is a matrix over 𝔽2. The function χAX takes value 1 when AX=𝟎, otherwise 0. In other words, χAX describe an affine relation on variables x1,x2,,xd.

Definition 14 ([25]).

We denote by 𝒜 the set of signatures which have the form λχAX𝔦L1(X)+L2(X)++Ln(X), where 𝔦=1, λ, n+, each Lj is a 0-1 indicator function of the form αj,X, where αj is a (d+1)-dimensional vector over 𝔽2, and the dot product , is computed over 𝔽2.

Definition 15 ([25]).

We denote by 𝒫 the set of all signatures which can be expressed a product of unary signatures, binary equality signatures (=2) and binary disequality signatures (2) (on not necessarily disjoint subsets of variables).

As in [9, chapter 3], 𝒜 and 𝒫 are closed under gadget construction. That is, if 𝒜 or 𝒫, then all -gates are respectively in 𝒜 or 𝒫. Now we state the dichotomy for #CSP from [25, Theorem 3.1].

Theorem 16 ([25]).

Suppose is a finite set of signatures mapping Boolean inputs to complex numbers. If 𝒜 or 𝒫, then #CSP() is computable in polynomial time. Otherwise, #CSP() is #P-hard.

For EO signatures belonging to 𝒜 or 𝒫, they satisfy the following properties.

Lemma 17 ([16, Lemma 5.7]).

If an EO signature f has affine support, then f is a pairwise opposite signature (EOM signature).

Lemma 18 ([16]).

f𝒜 (resp. 𝒫) if and only if τ(f)𝒜 (resp. 𝒫).

Now we introduce some definitions for the dichotomy for six-vertex model. is the set of all ternary signatures whose supports only contain strings of Hamming weight exactly 1. In other words, a quaternary EO signature fΔ1, if and only if supp(f){1}×{100,010,001}={1100,1010,1001}. ~ is defined similarly, except that the Hamming weight of each support string is exactly 2. The dichotomy for six-vertex model is as follows.

Theorem 19 ([19]).

Let f be a quaternary EO signature, then Holant(2f) is #P-hard except for the following cases:

a. f𝒫 (equivalently, fEOM and τ(f)𝒫);

b. f𝒜 (equivalently, fEOM and τ(f)𝒜);

c. fΔ1;

d. f~Δ0;

in which cases Holant(2f) is computable in polynomial time.

2.5 Insights from tractable cases

Starting from this section, this article presents a number of insights pertaining to the tractable cases within each dichotomy. The objective is to generalize these tractable cases at a high level of abstraction, although some statements may be informal. It is our hope that these generalized characteristics, derived from the tractable cases, will prove a valuable point of reference for future research.

In the dichotomy of #CSP, both 𝒜 and 𝒫 are self-dual signature sets. All signatures in 𝒜 and 𝒫 have affine supports, so having affine support is a necessary condition for tractability here, and we consider this condition as a support requirement. Informally speaking, there are two ways to reach tractability based on the support requirement, namely 𝒜 type and 𝒫 type requirements. The two steps explanation for the tractability part in Theorem 16, will be used as an important template in explaining the following results. We hope to exhibit an informal evolution process from the known tractable cases to the new tractable cases in this way.

In the dichotomy for six-vertex model, the support requirement is an union of two parts. The first part is that the support must be affine. Regardless of variable permutations, it is exactly an affine subspace of Q={0101,1001,0110,1010}. This corresponds to the tractable cases a and b in Theorem 19.

The second part is that the support must be an subset of Q1={1100,1010,1001} or its dual, Q0={0011,0101,0110}. This requirement itself is enough for tractability. Noticing that if each signature f in the instance satisfies that supp(f)=Q1, then one of its variables is fixed to 1, say x1. Transmitted by 2, as well as the general binary disequality signatures in the instance, another edge x2 of a signature g will be fixed to 0. Then the valid part of supp(g), the set of strings that can appear in an assignment with non-zero evaluation, is of size at most two and meets the affine support requirement. We denote this process as the receiving-sending mechanism. This mechanism directly corresponds to the chain reaction algorithm in [43]. This process may repeat many rounds, until each signature collapses to EOM. At each round, an opposite pair of variables is somehow fixed by this mechanism. And the process continues until the rest signatures in the whole instance are in EOM. Hence, this more general support requirement, can force a signature in an instance to work exactly like some EOM signature. The analysis of the dual case Q0 is similar.

3 New notations and our results

There are three parts of results in this paper, which are introduced in Subsection 3.1, 3.2, 3.3 respectively. In Subsection 3.4, we introduce two strange signatures, which serve as a motivation for some of our study. Finally in Subsection 3.5 we introduce the relations between these results.

3.1 A set of binary or quaternary signatures

The first part of our results generalizes six-vertex model to #EO problems defined by a set of EO signatures of arity no more than 4. We define

𝒜={fthe quotient of any two non-zero values of f belongs to {±1,±𝔦}}.

𝒜Δ1 can be seen as Δ1 with the 𝒜 type requirement. Similarly, we define

𝒜~={f~the quotient of any two non-zero values of f belongs to {±1,±𝔦}}.

The detailed version of Theorem 5 is as follows.

Theorem 20.

Suppose is a set of EO signatures with arity less than or equal to 4. Then Holant(2) is #P-hard unless one of the following conditions holds:

a. 𝒫(Δ1);

b. 𝒜(𝒜Δ1);

c. 𝒫(~Δ0);

d. 𝒜(𝒜~Δ0),

in which cases the problem can be computed in polynomial time.

We summarize current notations as the following tree. A specific example of the 𝒜 type requirement is also presented. When a set of signatures can meet all requirements on a path from the root to the four nodes at the bottom, the corresponding #EO problem is tractable; otherwise the problem is #P-hard.

3.1.1 Insights from tractable cases

This dichotomy exhibits two dual support requirements represented by {Q,Q1}444Each signature’s support must be a subset of either Q or Q1. and {Q,Q0}. Tractability requires satisfying either support requirement along with either an 𝒜-type or 𝒫-type requirement.

A key distinction between Theorems 19 and 20 lies in the emergence of 𝒜 in the latter. It can be verified that:

  • For Q signatures, 𝒜-type and 𝒫-type requirements produce the first two tractable classes in Theorem 19;

  • Q1 signatures under 𝒜-type requirements automatically satisfy 𝒫-type conditions, explaining the third tractable case;

  • The dual Q0 case similarly generates the fourth tractable case.

Theorem 20 demonstrates the crucial divergence between 𝒜-type and 𝒫-type requirements when handling mixed signature sets.

3.1.2 Proof outline of hardness result

We say two signature sets A,B mix (in ) if there exists f,g such that fAB and gBA. We first prove 3 no-mixing lemmas, mainly through signature classification on support size and gadget construction, showing the following cases are #P-hard:

  1. 1.

    Δ1 and ~Δ0 mix;

  2. 2.

    𝒜 and 𝒫 mix;

  3. 3.

    𝒜𝒫 and (Δ1)(𝒜Δ1) mix;

  4. 4.

    𝒜𝒫 and (~Δ0)(𝒜~Δ0) mix.

Suppose is a set of binary and quaternary EO signatures. Suppose the problem is not #P-hard. By Theorem 19, we can assume that 𝒜𝒫(Δ1)(~Δ0).

As Δ1 and ~Δ0 do not mix, either 𝒜𝒫(Δ1) or 𝒜𝒫(~Δ0). Due to the dual property, it is sufficient to focus on the former case.

As 𝒜 and 𝒫 do not mix, either 𝒫(Δ1) or 𝒜(Δ1). The former case is exactly tractable case a in Theorem 20. We focus on the latter case.

As 𝒜𝒫 and (Δ1)(𝒜Δ1) do not mix, either 𝒜(𝒜Δ1) or (𝒜𝒫)(Δ1). The former case is exactly tractable case b in Theorem 20, and the latter case is subsumed by tractable case a.

3.2 Pure signatures

In this section we focus on pure signatures, which can be seen as a generalization of the quaternary signatures in Δ1 and ~Δ0.

Definition 21.

An EO signature f is pure-up, if Span(f)HW. A signature set is pure-up, if each signature in it is pure-up. Similarly, An EO signature f is pure-down, if Span(f)HW. A signature set is pure-down, if each signature in it is pure-down.

These two categories are collectively termed pure signatures.

We summarize current notations as the following tree.

In the following, we present the dichotomy of pure signatures and the corresponding definitions. It is worth noticing that in this section, pure-up signatures and pure-down signatures never mix in .

Definition 22.

Suppose f is an arity 2d EO signature and SHW=. f|S is the restriction of f to S, which means when αS, f|S(α)=f(α), otherwise f|S(α)=0.

If for any pairing P of Var(f), f|EOP𝒜, then we say that f is EO𝒜.

Similarly, if for any pairing P of Var(f), f|EOP𝒫, then f is EO𝒫.

Theorem 23 (The dichotomy for pure-up EO signatures).

Suppose is a set of pure-up EO signatures. Then #EO() is #P-hard unless all signatures in are EO𝒜 or all of them are EO𝒫, in which cases the problem can be computed in polynomial time.

3.2.1 Insights from tractable cases

We primarily analyze pure-up signatures, noting that pure-down signatures admit dual analysis through symmetric arguments. Key properties of pure-up signatures reveal that each either belongs to EOM, or has at least one variable fixed to 1. These properties enable application of the active receiving-sending mechanism. Pure signatures thus induce a generalized support requirement with two dual cases (intersecting at the self-dual EOM requirement), where tractability emerges through additional EO𝒜 type or EO𝒫 type requirements.

3.2.2 Proof outline of hardness result

For a pure signature fof arity 2d, it can be proved that for an arbitrary pairing P of Var(f), f|EOP=fΔ0dkΔ1dk where f is an EOM signature of arity 2k. Such f can be realized by adding dk self-loops, and f𝒜 (or 𝒫) if and only if f|EOP𝒜 (or 𝒫).

Consequently, if is not a subset of EO𝒜 or EO𝒫, then there exist EOM signatures f𝒜 and g𝒫 can be realized. By Lemma 12, #EO({f,g}) is equivalent to a #CSP({f′′,g′′}) problem, where f′′𝒜 and g′′𝒫. By Theorem 16 #CSP({f′′,g′′}) is #P-hard, and consequently #EO() is #P-hard.

3.3 Rebalancing signatures

In this section, we define a property named rebalancing for EO signatures.

Definition 24 (Rebalancing).

An EO signature f of arity 2d, is called 0-rebalancing(1-rebalancing respectively), when the following recursive conditions are met.

  • d=0: No restriction.

  • d1: For any variable x in X=Var(f), there exists a variable y=ψ(x) different from x, such that for any α{0,1}X, if αx=αy=0(αx=αy=1 respectively) then f(α)=0. Besides, the arity 2d2 signature fx=0,y=1 is 0-rebalancing(fx=1,y=0 is 1-rebalancing respectively).

For completeness we view all nontrivial signatures of arity 0, which is a non-zero constant, as 0-rebalancing(1-rebalancing) signatures. For the d1 case, ψ is said to be the first level mapping of f.

Tractability can also be obtained based on 0-rebalancing/1-rebalancing property.

Theorem 25.

If is composed of 0-rebalancing(1-rebalancing) EO𝒜 signatures, or is composed of 0-rebalancing(1-rebalancing) EO𝒫 signatures, then #EO() is polynomial-time computable.

 Remark 26.

It can be verified that every EOM signature satisfies both 0-rebalancing and 1-rebalancing conditions. All pure-up signatures are 0-rebalancing due to the following arguments. When a pure-up signature f satisfies supp(f)HW>, it necessarily contains a Δ1(x) factor. This factor induces a first-level mapping ψ where all variables except x map to x, while ψ(x) can be any variable other than itself. This mapping process can be recursively applied until the signature f is transformed into an EOM signature, which remains 0-rebalancing. Through dual reasoning, all pure-down signatures satisfy 1-rebalancing.

3.3.1 Insights from the algorithm

This section extends the receiving-sending mechanism to rebalancing signatures. While the active receiving-sending mechanism for pure signatures requires initial Δ1 (Δ0) triggers, rebalancing signatures may lack such initial conditions. Nevertheless, by assuming fixed values for certain variables, the mechanism still functions through what we term the passive receiving-sending mechanism. Building on this modified mechanism, we develop a polynomial-time algorithm for #EO problems defined by 0-rebalancing or 1-rebalancing signatures meeting 𝒜-type or 𝒫-type requirements.

Definition 24 for d1 specifies two necessary conditions: the existence of mapping ψ (first-level condition) and the recursive condition. Crucially, the first-level condition remains unconditional - the relationship between x and ψ(x) persists even when other variables are fixed. This property enables identification of loops (rather than Δ0/Δ1-initiated paths) in the passive mechanism, while the recursive condition ensures the mechanism’s iterative applicability.

3.4 Two strange signatures

In this subsection we present the definition of f40 and f56, which are considered as two important examples in our study. Some of our results are motivated by these signatures. We first introduce some notations to describe signatures with large arity and a sparse support.

For matrices As×p and Bs×q, we use Cs×(p+q)=[AB] to denote the matrix C satisfying

C(i,j)={A(i,j),1jp;B(i,jp),p+1jp+q. (1)

Informally speaking, C is a concatenation of A,B. We use Ak to denote the matrix [AAA], which is a concatenation of k copies of matrix A. We also define the following matrices.

H0=(00000),H2=(11110000001000111000010010011000100101010001001011),H4=(0111110111110111110111110)

For a signature f of arity k, we use the support matrix Rs×k to describe its support. A string α{0,1}k is a support string of f if and only if α equals a row in Rs×k. f40 has the support matrix R5×40=[H23H42], f56 has the support matrix R5×56=[H0H24H43] and both of them are 0-1 weighted. Though the supports of them are sparse, they are not able to be captured by a number of existing algorithms and hardness results.

3.5 Relations between results

The first two parts collectively establish complete dichotomies for #EO problems, incorporating both tractability and hardness results: the first for binary and quaternary signature sets, the second for pure-up/pure-down signature sets. The hardness results from the first part form the foundational basis for the hardness classification in complex-weighted #EO, while those from the second part are equally pivotal for establishing the full #EO dichotomy.

The third part focuses on defining the rebalancing property and presenting a polynomial-time algorithm for 0-rebalancing/1-rebalancing signatures with type requirements. Notably, this algorithm subsumes both previous algorithms through its innovative use of support requirements to emulate the EOM property’s effects. The case of f40 (defined in Section 3.4) exemplifies this generalization - although not a pure signature, its satisfaction of 0-rebalancing demonstrates our algorithm’s strictly broader applicability compared to the pure signatures’ algorithm.

We observe that although the results in [43] are restricted to 0-1 weighted #EO problems, they nevertheless capture essential support requirements for signatures. Specifically, the pure property inherently implies the δ-affine property, and their chain reaction algorithm implements what we term the active receiving-sending mechanism.

The complex-weighted #EO dichotomy in [40] adopts the notation k for pure-up signatures and k for pure-down signatures, where our Theorem 23 directly resolves “Case 3a” and “Case 4a”. Notably, the signatures f40 and f56 introduced in our work, whose non-trivial nature is evident from our analysis, provide concrete examples for “Case 3c”.

4 Conclusion

In this article, we prove two dichotomies for #EO(): one with restricted to binary and quaternary signatures, and another with restricted to pure signatures. We also present an algorithm for rebalancing signature sets satisfying EO𝒜 or EO𝒫. A more detailed characterization of pure signatures and rebalancing signatures would be valuable, similar to what has been achieved for δ-affine kernels in [43]. Indeed, pure signatures clearly exhibit close connections to δ-affine signatures.

The pursuit of a complete dichotomy for #EO remains an important research direction. Notably, the signature f56 defined in Section 3.4 is neither pure nor rebalancing. The complexity of #EO({f56}) remains unresolved and presents significant interest. While some progress has been made, substantial challenges persist in addressing this problem.

Recent work [40] has established an FPNP versus #P dichotomy for complex-valued #EO, which includes an interesting polynomial-time algorithm with a specific NP oracle for solving #EO(f56). This development has also prompted renewed investigation of Boolean constraint satisfaction problems [32]. Nevertheless, the polynomial-time computability of #EO(f56) remains an open question, and the most general known polynomial-time algorithm for #EO is still our rebalancing signature algorithm presented in this work.

References

  • [1] Miriam Backens. A new Holant dichotomy inspired by quantum computation. arXiv preprint arXiv:1702.00767, 2017. arXiv:1702.00767.
  • [2] Miriam Backens. A full dichotomy for Holantc, inspired by quantum computation. SIAM Journal on Computing, 50(6):1739–1799, 2021.
  • [3] David M Bressoud. Proofs and confirmations: the story of the alternating-sign matrix conjecture. Cambridge University Press, 1999.
  • [4] Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, and David Richerby. The complexity of weighted and unweighted #CSP. Journal of Computer and System Sciences, 78(2):681–688, 2012. doi:10.1016/j.jcss.2011.12.002.
  • [5] Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, and David Richerby. The complexity of weighted Boolean #CSP with mixed signs. Theoretical Computer Science, 410(38-40):3949–3961, 2009. doi:10.1016/j.tcs.2009.06.003.
  • [6] Andrei Bulatov and Martin Grohe. The complexity of partition functions. Theoretical Computer Science, 348(2-3):148–186, 2005. doi:10.1016/j.tcs.2005.09.011.
  • [7] Andrei A Bulatov. The complexity of the counting constraint satisfaction problem. Journal of the ACM (JACM), 60(5):1–41, 2013. doi:10.1145/2528400.
  • [8] Andrei A Bulatov and Víctor Dalmau. Towards a dichotomy theorem for the counting constraint satisfaction problem. Information and Computation, 205(5):651–678, 2007. doi:10.1016/j.ic.2006.09.005.
  • [9] Jin-Yi Cai and Xi Chen. Complexity dichotomies for counting problems: Volume 1, Boolean domain. Cambridge University Press, 2017.
  • [10] Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. Journal of the ACM (JACM), 64(3):1–39, 2017. doi:10.1145/2822891.
  • [11] Jin-Yi Cai and Xi Chen. A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. computational complexity, 28:345–408, 2019. doi:10.1007/s00037-019-00184-5.
  • [12] Jin-Yi Cai, Xi Chen, and Pinyan Lu. Graph homomorphisms with complex values: A dichotomy theorem. SIAM Journal on Computing, 42(3):924–1029, 2013. doi:10.1137/110840194.
  • [13] Jin-Yi Cai, Xi Chen, and Pinyan Lu. Nonnegative weighted #CSP: an effective complexity dichotomy. SIAM Journal on Computing, 45(6):2177–2198, 2016. doi:10.1137/15M1032314.
  • [14] Jin-Yi Cai and Vinay Choudhary. Valiant’s Holant theorem and matchgate tensors. Theoretical Computer Science, 384(1):22–32, 2007. doi:10.1016/j.tcs.2007.05.015.
  • [15] Jin-Yi Cai and Zhiguo Fu. Complexity classification of the eight-vertex model. Information and Computation, 293:105064, 2023. doi:10.1016/j.ic.2023.105064.
  • [16] Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. Beyond #CSP: A dichotomy for counting weighted Eulerian orientations with ARS. Information and Computation, 275:104589, 2020. doi:10.1016/j.ic.2020.104589.
  • [17] Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. From Holant to quantum entanglement and back. arXiv preprint arXiv:2004.05706, 2020. arXiv:2004.05706.
  • [18] Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. New planar P-time computable six-vertex models and a complete complexity classification. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1535–1547. SIAM, 2021. doi:10.1137/1.9781611976465.93.
  • [19] Jin-Yi Cai, Zhiguo Fu, and Mingji Xia. Complexity classification of the six-vertex model. Information and Computation, 259:130–141, 2018. doi:10.1016/j.ic.2018.01.003.
  • [20] Jin-Yi Cai and Artem Govorov. Perfect matchings, rank of connection tensors and graph homomorphisms. Combinatorics, Probability and Computing, 31(2):268–303, 2022. doi:10.1017/S0963548321000286.
  • [21] Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 635–644, 2013.
  • [22] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Holant problems and counting CSP. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 715–724, 2009. doi:10.1145/1536414.1536511.
  • [23] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Computational complexity of Holant problems. SIAM Journal on Computing, 40(4):1101–1132, 2011. doi:10.1137/100814585.
  • [24] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for Holant* problems of Boolean domain. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1714–1728. SIAM, 2011. doi:10.1137/1.9781611973082.132.
  • [25] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted Boolean #CSP. Journal of Computer and System Sciences, 80(1):217–236, 2014. doi:10.1016/j.jcss.2013.07.003.
  • [26] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for real Holantc problems. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1802–1821. SIAM, 2018. doi:10.1137/1.9781611975031.118.
  • [27] Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. The complexity of weighted Boolean #CSP. SIAM Journal on Computing, 38(5):1970–1986, 2009. doi:10.1137/070690201.
  • [28] Martin Dyer, Leslie Ann Goldberg, and Mike Paterson. On counting homomorphisms to directed acyclic graphs. Journal of the ACM (JACM), 54(6):27–es, 2007.
  • [29] Martin Dyer and Catherine Greenhill. The complexity of counting graph homomorphisms. Random Structures & Algorithms, 17(3-4):260–289, 2000. doi:10.1002/1098-2418(200010/12)17:3/4\%3C260::AID-RSA5\%3E3.0.CO;2-W.
  • [30] Martin Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM Journal on Computing, 42(3):1245–1274, 2013. doi:10.1137/100811258.
  • [31] Martin E Dyer and David M Richerby. On the complexity of #CSP. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 725–734, 2010. doi:10.1145/1806689.1806789.
  • [32] Tomás Feder and Daniel Ford. Classification of bipartite Boolean constraint satisfaction through delta-matroid intersection. SIAM Journal on Discrete Mathematics, 20(2):372–394, 2006. doi:10.1137/S0895480104445009.
  • [33] Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A complexity dichotomy for partition functions with mixed signs. SIAM Journal on Computing, 39(7):3336–3402, 2010. doi:10.1137/090757496.
  • [34] Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia. The complexity of weighted Boolean #CSP modulo k. In STACS 2011, pages 249–260. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2011. doi:10.4230/LIPIcs.STACS.2011.249.
  • [35] Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. Journal of Combinatorial Theory, Series B, 48(1):92–110, 1990. doi:10.1016/0095-8956(90)90132-J.
  • [36] Michel Las Vergnas. On the evaluation at (3, 3) of the Tutte polynomial of a graph. Journal of Combinatorial Theory, Series B, 45(3):367–372, 1988. doi:10.1016/0095-8956(88)90079-2.
  • [37] Jiabao Lin and Hanpin Wang. The complexity of Boolean Holant problems with nonnegative weights. SIAM Journal on Computing, 47(3):798–828, 2018. doi:10.1137/17M113304X.
  • [38] László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):321–328, 1967.
  • [39] Boning Meng, Juqiu Wang, and Mingji Xia. P-time algorithms for typical #EO problems. arXiv preprint arXiv:2410.11557, 2024. doi:10.48550/arXiv.2410.11557.
  • [40] Boning Meng, Juqiu Wang, and Mingji Xia. The FPNP versus #P dichotomy for #EO, 2025. doi:10.48550/arXiv.2502.02012.
  • [41] Linus Pauling. The structure and entropy of ice and of other crystals with some randomness of atomic arrangement. Journal of the American Chemical Society, 57(12):2680–2684, 1935.
  • [42] Shuai Shao and Jin-Yi Cai. A dichotomy for real Boolean Holant problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1091–1102. IEEE, 2020. doi:10.1109/FOCS46700.2020.00105.
  • [43] Shuai Shao and Zhuxiao Tang. Eulerian orientations and Hadamard codes: A novel connection via counting. arXiv preprint arXiv:2411.02612, 2024. doi:10.48550/arXiv.2411.02612.
  • [44] Leslie G Valiant. Holographic algorithms. SIAM Journal on Computing, 37(5):1565–1594, 2008. doi:10.1137/070682575.