We present a Weitz-type FPTAS for the ferromagnetic Ising model across the entire Lee--Yang zero-free region, without relying on the strong spatial mixing (SSM) property. Our algorithm is Weitz-type for two reasons. First, it expresses the partition function as a telescoping product of ratios, with the key being to approximate each ratio. Second, it uses Weitz's self-avoiding walk tree, and truncates it at logarithmic depth to give a good and efficient approximation. The key difference from the standard Weitz algorithm is that we approximate a carefully designed edge-deletion ratio instead of the marginal probability of a vertex being assigned a particular spin, ensuring our algorithm does not require SSM. Furthermore, by establishing local dependence of coefficients (LDC), we prove a novel form of SSM for these edge-deletion ratios, which, in turn, implies the standard SSM for the random cluster model. This is the first SSM result for the random cluster model on general graphs, beyond lattices. Our proof of LDC is based on a new divisibility relation, and we show such relations hold quite universally. This leads to a broadly applicable framework for proving LDC across a variety of models, including the Potts model, the hypergraph independence polynomial, and Holant problems. Combined with existing zero-freeness results for these models, we derive new SSM results for them.

We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in ℂ for the eight-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) #P-hard for general graphs but computable in P-time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. In (2), we discover new P-time computable eight-vertex models on planar graphs beyond Kasteleyn’s algorithm for counting planar perfect matchings. They are obtained by a combinatorial transformation to the planar Even Coloring problem followed by a holographic transformation to the tractable cases in the planar six-vertex model. In the process, we also encounter non-local connections between the planar eight vertex model and the bipartite Ising model, conformal lattice interpolation and Möbius transformation from complex analysis. The proof also makes use of cyclotomic fields.

General factors are a generalization of matchings. Given a graph G with a set π(v) of feasible degrees, called a degree constraint, for each vertex v of G, the general factor problem is to find a (spanning) subgraph F of G such that deg_F(v) ∈ π(v) for every v of G. When all degree constraints are symmetric Δ-matroids, the problem is solvable in polynomial time. The weighted general factor problem is to find a general factor of the maximum total weight in an edge-weighted graph. Strongly polynomial-time algorithms are only known for weighted general factor problems that are reducible to the weighted matching problem by gadget constructions. In this paper, we present a strongly polynomial-time algorithm for a type of weighted general factor problems with real-valued edge weights that is provably not reducible to the weighted matching problem by gadget constructions. As an application, we obtain a strongly polynomial-time algorithm for the terminal backup problem by reducing it to the weighted general factor problem.

We discover new P-time computable six-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings.∗ We further prove that there are no more: Together, they exhaust all P-time computable six-vertex models on planar graphs, assuming #P is not P. This leads to the following exact complexity classification: For every parameter setting in ℂ for the six-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) #P-hard for general graphs but computable in P-time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. The new P-time cases in (2) provably cannot be subsumed by Kasteleyn's algorithm. They are obtained by a non-local connection to #CSP, defined in terms of a “loop space”. This is the first substantive advance toward a planar Holant classification with not necessarily symmetric constraints. We introduce Möbius transformation on ℂ as a powerful new tool in hardness proofs for counting problems.

We prove a complexity dichotomy for Holant problems on the boolean domain with arbitrary sets of real-valued constraint functions. These constraint functions need not be symmetric nor do we assume any auxiliary functions. It is proved that for every set F of real-valued constraint functions, Holant(F) is either P-time computable or #P-hard. The classification has an explicit criterion. This is a culmination of much research on this problem, and it uses many previous results and techniques. Dealing with some concrete functions plays an important role in this proof. In particular, two functions, called f6 and f8, and their associated families exhibit intriguing and extraordinary closure properties related to Bell states in quantum information theory.

Holant problems are intimately connected with quantum theory as tensor networks. We first use techniques from Holant theory to derive new and improved results for quantum entanglement theory. We discover two particular entangled states |Ψ₆⟩ of 6 qubits and |Ψ₈⟩ of 8 qubits respectively, that have extraordinary closure properties in terms of the Bell property. Then we use entanglement properties of constraint functions to derive a new complexity dichotomy for all real-valued Holant problems containing a signature of odd arity. The signatures need not be symmetric, and no auxiliary signatures are assumed.

For any bent function, it is very interesting to determine its dual function, because the dual function is also bent in certain cases. For k odd and gcd(n, k) = 1, it is known that the Coulter-Matthews bent function f(x) = T r (ax 3k+1/2) is weakly regular bent over F3n, where a ∈ F3n*, and T r (·) : F3n→ F3is the trace function. In this paper, we investigate the dual function of f (x), aiming to determine a universal formula. In particular, for two cases, we determine the formula explicitly: for the case of n = 3t + 1 and k = 2t + 1 with t ≥ 2, the dual function is given by Tr (- x32t+1+3t+1+2/a32t+1+3t+1+1) - x32t+1/a-32t+3t+1+ x2/a-32t+1+3t+1+1); and for the case of n = 3t + 2 and k = 2t + 1 with t≥2,the dual function is given by Tr (-x32t+2+1/a32t+2-3t+1+3- x2.32t+1+3t+1+1/a32t+2+3t+1+3+ x2/a-32t+2+3t+1+3) As a byproduct, we find two new classes of ternary bent functions with only three terms. Moreover, we also prove that in certain cases f (x) is regular bent.

In 1998, Lin presented a conjecture on a class of ternary sequences with ideal 2-level autocorrelation. Those sequences have a very simple structure, i.e., their trace representation has two trace monomial terms. In this paper, we present a proof for this conjecture. The mathematical tools employed are the second-order multiplexing decimation-Hadamard transform, Stickelberger's theorem, the Teichmüller character, and combinatorial techniques for enumerating the Hamming weights of ternary numbers. As a by-product, we also prove that the Lin conjectured ternary sequences are Hadamard equivalent to ternary m-sequences.

In 1998, Lin presented a conjecture on a class of ternary sequences with ideal two-level autocorrelation. Those sequences have a very simple structure, i.e., their trace representation has two trace monomial terms. In this paper, we present a proof for the conjecture. The mathematical tools employed are the second-order multiplexing decimation-Hadamard transform, Stickelberger's theorem, the Teichmüller character, and combinatorial techniques for enumerating the Hamming weights of ternary numbers. As a by-product, we also prove that the ternary sequences conjectured by Lin are Hadamard equivalent to ternary m-sequences.