
Dichotomy Result on 3Regular Bipartite Nonnegative Functions
We prove a complexity dichotomy theorem for a class of Holant problems o...
read it

FPRAS via MCMC where it mixes torpidly (and very little effort)
Is Fully Polynomialtime Randomized Approximation Scheme (FPRAS) for a p...
read it

The Complexity of Counting Edge Colorings for Simple Graphs
We prove #Pcompleteness results for counting edge colorings on simple g...
read it

A Dichotomy for Real Boolean Holant Problems
We prove a complexity dichotomy for Holant problems on the boolean domai...
read it

Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs
The complexity of graph homomorphisms has been a subject of intense stud...
read it

From Holant to Quantum Entanglement and Back
Holant problems are intimately connected with quantum theory as tensor n...
read it

A dichotomy for bounded degree graph homomorphisms with nonnegative weights
We consider the complexity of counting weighted graph homomorphisms defi...
read it

On a Theorem of Lovász that (·, H) Determines the Isomorhphism Type of H
Graph homomorphism has been an important research topic since its introd...
read it

Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms
We develop a theory of graph algebras over general fields. This is model...
read it

Counting perfect matchings and the eightvertex model
We study the approximation complexity of the partition function of the e...
read it

Complexity of Counting Weighted Eulerian Orientations with ARS
Unique prime factorization of integers is taught in every high school. W...
read it

Approximability of the Eightvertex Model
We initiate a study of the classification of approximation complexity of...
read it

Approximability of the Sixvertex Model
In this paper we take the first step toward a classification of the appr...
read it
JinYi Cai
is this you? claim profile