Mingji Xia

I&C Journal 2026 Journal Article

Dichotomy for Holant* problems with one ternary function on domain size 3

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

Holant problems are a general framework to study the algorithmic complexity of counting problems. Both counting constraint satisfaction problems and graph homomorphisms are special cases. All previous results of Holant problems are over the Boolean domain. 3 In this paper, we give the first dichotomy theorem for Holant problems for domain size >2. We discover unexpected tractable families of counting problems, by giving new polynomial time algorithms. This paper also initiates holographic reductions in domains of size >2. This is our main algorithmic technique, and is used for both tractable families and hardness reductions. The dichotomy theorem is the following: For any complex-valued symmetric function F with arity 3 on domain size 3, we give an explicit criterion on F, such that if F satisfies the criterion then the problem Holant ⁎ ( F ) is computable in polynomial time; otherwise Holant ⁎ ( F ) is #P-hard.

I&C Journal 2026 Journal Article

Variable version Lovász local lemma: A tale of two boundaries

• Kun He
• Liang Li
• Xingwu Liu
• Yuyi Wang
• Mingji Xia

Shearer gave a tight criterion for the abstract version of the Lovász Local Lemma (abstract-LLL), but the corresponding picture for the variable version (variable-LLL), where events are generated from independent random variables, has remained largely open. We establish a necessary and sufficient criterion for variable-LLL expressed purely in terms of the event probabilities and the event-variable bigraph. This allows us to determine exactly the probability boundary for two fundamental families of event-variable graphs: cyclic and treelike bigraphs, giving the first nontrivial cases where the variable-LLL boundary is fully characterized. As a byproduct, we obtain a general constructive procedure that, for any given probability vector and event-variable graph, produces a set of events whose union has maximum possible probability; the method also applies when any two events are either independent or disjoint. We further show that computing the variable-LLL boundary is #P-hard in general, and focus on deciding whether there is a gap between the variable-LLL boundary and the corresponding abstract-LLL (Shearer) boundary. We prove that gap existence can be decided without evaluating Shearer's condition or our criterion. Using this theorem, we show that there is no gap when the base graph of the event-variable graph is a tree, whereas any induced cycle of length at least four forces a gap. Finally, we develop reduction rules that propagate gapful/gapless property and apply them to several combinatorial event-variable graphs.

STOC Conference 2025 Conference Paper

The FPᴺᴾ versus #P Dichotomy for #EO

• Boning Meng
• Juqiu Wang
• Mingji Xia

I&C Journal 2018 Journal Article

Complexity classification of the six-vertex model

• Jin-Yi Cai
• Zhiguo Fu
• Mingji Xia

We prove a complexity dichotomy theorem for the six-vertex model. For every setting of the parameters of the model, we prove that computing the partition function is either solvable in polynomial time or #P-hard. The dichotomy criterion is explicit.

SODA Conference 2018 Conference Paper

Dichotomy for Real Holant c Problems

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

FOCS Conference 2017 Conference Paper

Variable-Version Lovász Local Lemma: Beyond Shearer's Bound

• Kun He 0011
• Liang Li
• Xingwu Liu
• Yuyi Wang 0001
• Mingji Xia

A tight criterion under which the abstract version Lovász Local Lemma (abstract-LLL) holds was given by Shearer [41] decades ago. However, little is known about that of the variable version LLL (variable-LLL) where events are generated by independent random variables, though variable- LLL naturally models and is enough for almost all applications of LLL. We introduce a necessary and sufficient criterion for variable-LLL, in terms of the probabilities of the events and the event-variable graph specifying the dependency among the events. Based on this new criterion, we obtain boundaries for two families of event-variable graphs, namely, cyclic and treelike bigraphs. These are the first two non-trivial cases where the variable-LLL boundary is fully determined. As a byproduct, we also provide a universal constructive method to find a set of events whose union has the maximum probability, given the probability vector and the event-variable graph. Though it is #P-hard in general to determine variable- LLL boundaries, we can to some extent decide whether a gap exists between a variable-LLL boundary and the corresponding abstract-LLL boundary. In particular, we show that the gap existence can be decided without solving Shearer’s conditions or checking our variable-LLL criterion. Equipped with this powerful theorem, we show that there is no gap if the base graph of the event-variable graph is a tree, while gap appears if the base graph has an induced cycle of length at least 4. The problem is almost completely solved except when the base graph has only 3-cliques, in which case we also get partial solutions. A set of reduction rules are established that facilitate to infer gap existence of a event-variable graph from known ones. As an application, various event-variable graphs, in particular combinatorial ones, are shown to be gapful/gapless.

STOC Conference 2016 Conference Paper

Base collapse of holographic algorithms

• Mingji Xia

A holographic algorithm solves a problem in a domain of size n , by reducing it to counting perfect matchings in planar graphs. It may simulate a n -value variable by a bunch of t matchgate bits, which has 2 t values. The transformation in the simulation can be expressed as a n × 2 t matrix M , called the base of the holographic algorithm. We wonder whether more matchgate bits bring us more powerful holographic algorithms. In another word, whether we can solve the same original problem, with a collapsed base of size n × 2 r , where r < t .

FOCS Conference 2015 Conference Paper

Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k

• Radu Curticapean
• Mingji Xia

We identify and study relevant structural parameters for the problem PerfMatch of counting perfect matchings in a given input graph C. These generalize the well-known tractable planar case, and they include the genus of C, its apex number (the minimum number of vertices whose removal renders C planar), and its Hadwiger number (the size of a largest clique minor). To study these parameters, we first introduce the notion of combined matchgates, a general technique that bridges parameterized counting problems and the theory of so-called Holants and matchgates: Using combined matchgates, we can simulate certain nonexisting gadgets F as linear combinations of L = O(1) existing gadgets. If a graph C features k occurrences of F, we can then reduce C to t k graphs that feature only existing gadgets, thus enabling parameterized reductions. As applications of this technique, we simplify known 4 g n O(1) time algorithms for PerfMatch on graphs of genus g. Orthogonally to this, we show #W[1]-hardness of the permanent on k-apex graphs, implying its ⊕W[1]-hardness under the Hadwiger number. Additionally, we rule out n o(k/ log k) time algorithms under the counting exponential-time hypothesis #ETH. Finally, we use combined matchgates to prove $W[1]-hardness of evaluating the permanent modulo 2k, complementing an O(n 4k-3 ) time algorithm by Valiant and answering an open question of Bjϋrklund. We also obtain a lower bound of n Ω(k/ log k) under the parity version $ETH of the exponential-time hypothesis.

SODA Conference 2013 Conference Paper

Dichotomy for Holant* Problems with Domain Size 3

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

TCS Journal 2011 Journal Article

A computational proof of complexity of some restricted counting problems

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

We explore a computational approach to proving the intractability of certain counting problems. These problems can be described in various ways, and they include concrete problems such as counting the number of vertex covers or independent sets for 3-regular graphs. The high level principle of our approach is algebraic, which provides sufficient conditions for interpolation to succeed. Another algebraic component is holographic reductions. We then analyze in detail polynomial maps on R 2 induced by some combinatorial constructions. These maps define sufficiently complicated dynamics of R 2 that we can only analyze them computationally. In this paper we use both numerical computation (as intuitive guidance) and symbolic computation (as proof theoretic verification) to derive that a certain collection of combinatorial constructions, in myriad combinations, fulfills the algebraic requirements of proving #P-hardness. The final result is a dichotomy theorem for a class of counting problems. This includes a class of generic holant problems with an arbitrary real valued edge signature over ( 2, 3 ) -regular undirected graphs. In particular, it includes all partition functions with 0–1 vertex assignments and an arbitrary real valued edge function over all 3-regular undirected graphs.

SODA Conference 2011 Conference Paper

Dichotomy for Holant* Problems of Boolean Domain

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

Holant problems are a general framework to study counting problems. Both counting Constraint Satisfaction Problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant*( F ), where F is a set of constraint functions on Boolean variables and output complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique and indeed the formulation of the theorem use holographic algorithms and reductions. By considering these counting problems over the complex domain, we discover surprising new tractable classes, which are associated with isotropic vectors, i. e. , a (non-zero) vector whose inner product with itself is zero.

FOCS Conference 2010 Conference Paper

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

Valiant introduced match gate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, match gate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i. e. , polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but ractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

TCS Journal 2009 Journal Article

An approximation algorithm to the k-Steiner Forest problem

• Peng Zhang
• Mingji Xia

Given a graph G, an integer k, and a demand set D = { ( s 1, t 1 ), …, ( s l, t l ) }, the k -Steiner Forest problem finds a forest in graph G to connect at least k demands in D such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O ( n 2 / 3 log l ). We give a simpler and faster approximation algorithm to this problem with performance ratio O ( n 2 / 3 log k ) via greedy approach, improving the previously best known ratio in the literature.

STOC Conference 2009 Conference Paper

Holant problems and counting CSP

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant Problems. Compared to counting Constrained Satisfaction Problems (CSP), it is a refinement with a more explicit role for the function constraints. Both graph homomorphism and CSP can be viewed as special cases of Holant Problems. We prove complexity dichotomy theorems in this framework. Because the framework is more stringent, previous dichotomy theorems for CSP problems no longer apply. Indeed, we discover surprising tractable subclasses of counting problems, which could not have been easily specified in the CSP framework. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations. The study of Holant Problems led us to discover and prove a complexity dichotomy theorem for the most general form of Boolean CSP where every constraint function takes values in the complex number field {C}.

FOCS Conference 2008 Conference Paper

Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

We propose a new method to prove complexity dichotomy theorems. First we introduce Fibonacci gates which provide a new class of polynomial time holographic algorithms. Then we develop holographic reductions. We show that holographic reductions followed by interpolations provide a uniform strategy to prove #P-hardness.

TCS Journal 2007 Journal Article

Computational complexity of counting problems on 3-regular planar graphs

• Mingji Xia
• Peng Zhang
• Wenbo Zhao

A variety of counting problems on 3-regular planar graphs are considered in this paper. We give a sufficient condition which guarantees that the coefficients of a homogeneous polynomial can be uniquely determined by its values on a recurrence sequence. This result enables us to use the polynomial interpolation technique in high dimension to prove the #P-completeness of problems on graphs with special requirements. Using this method, we show that #3-Regular Bipartite Planar Vertex Covers is #P-complete. Furthermore, we use Valiant’s Holant Theorem to construct a holographic reduction from it to #2, 3-Regular Bipartite Planar Matchings, establishing the #P-completeness of the latter. Finally, we completely classify the problems #Planar Read-twice 3SAT with different ternary symmetric relations according to their computational complexity, by giving several more applications of holographic reduction in proving the #P-completeness of the corresponding counting problems.