We take the first step toward a classification of the approximation complexity of the six-vertex
model. This is a subject of extensive research in statistical physics. Our result concerns the …

We study the approximability of the four-vertex model, a special case of the six-vertex model.
We prove that, despite being NP-hard to approximate in the worst case, the four-vertex …

We discover a novel connection between two classical mathematical notions, Eulerian
orientations and Hadamard codes by studying the counting problem of Eulerian orientations …

We study the approximability of the four-vertex model, a special case of the six-vertex model.
We prove that, despite being NP-hard to approximate in the worst case, the four-vertex …

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 …

An essential problem in the design of holographic algorithms is to decide whether the
required signatures can be realized by matchgates under a suitable basis transformation …

The six-vertex model is an important model in statistical physics and has deep connections
with counting problems. There have been some fully polynomial randomized approximation …

Suppose φ and ψ are two angles satisfying tan (φ)= 2 tan (ψ)> 0. We prove that under this
condition φ and ψ cannot be both rational multiples of π. We use this number theoretic result …

An Eulerian orientation of an undirected graph is an orientation of edges such that, for each
vertex, both the indegree and the outdegree are the same. Eulerian orientations are …

This dissertation furthers a systematic study of the complexity classification of counting
problems. A central goal of this study is to prove complexity classification theorems which …