Jin-Yi Cai

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.

TCS Journal 2025 Journal Article

Restricted holant dichotomy on domain sizes 3 and 4

• Yin Liu
• Austen Z. Fan
• Jin-Yi Cai

Holant ⁎ ( f ) denotes a class of counting problems specified by a constraint function f. We prove complexity dichotomy theorems for Holant ⁎ ( f ) in two settings: (1) f is any symmetric arity-3 real-valued function on input of domain size 3. (2) f is any symmetric arity-3 { 0, 1 } -valued function on input of domain size 4.

I&C Journal 2023 Journal Article

Complexity classification of the eight-vertex model

• Jin-Yi Cai
• Zhiguo Fu

We prove a complexity dichotomy theorem for the eight-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. For tractability, we find some new classes of problems computable in polynomial time. For #P-hardness, we employ Möbius transformations to prove the success of interpolations.

TCS Journal 2023 Journal Article

Dichotomy result on 3-regular bipartite non-negative functions

• Austen Z. Fan
• Jin-Yi Cai

We prove a complexity dichotomy theorem for a class of Holant problems on 3-regular bipartite graphs. Given an arbitrary nonnegative weighted symmetric constraint function f = [ x 0, x 1, x 2, x 3 ], we prove that the bipartite Holant problem Holant ( f | ( = 3 ) ) is either computable in polynomial time or #P-hard. The dichotomy criterion on f is explicit.

AAAI Conference 2023 Conference Paper

Properties of Position Matrices and Their Elections

• Niclas Boehmer
• Jin-Yi Cai
• Piotr Faliszewski
• Austen Z. Fan
• Łukasz Janeczko
• Andrzej Kaczmarczyk
• Tomasz Wąs

We study the properties of elections that have a given position matrix (in such elections each candidate is ranked on each position by a number of voters specified in the matrix). We show that counting elections that generate a given position matrix is #P-complete. Consequently, sampling such elections uniformly at random seems challenging and we propose a simpler algorithm, without hard guarantees. Next, we consider the problem of testing if a given matrix can be implemented by an election with a certain structure (such as single-peakedness or group-separability). Finally, we consider the problem of checking if a given position matrix can be implemented by an election with a Condorcet winner. We complement our theoretical findings with experiments.

STOC Conference 2023 Conference Paper

The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3

• Jin-Yi Cai
• Ashwin Maran

MFCS Conference 2022 Conference Paper

Bounded Degree Nonnegative Counting CSP

• Jin-Yi Cai
• Daniel P. Szabo

Constraint satisfaction problems (CSP) encompass an enormous variety of computational problems. In particular, all partition functions from statistical physics, such as spin systems, are special cases of counting CSP (#CSP). We prove a complete complexity classification for every counting problem in #CSP with nonnegative valued constraint functions that is valid when every variable occurs a bounded number of times in all constraints. We show that, depending on the set of constraint functions ℱ, every problem in the complexity class #CSP(ℱ) defined by ℱ is either polynomial time computable for all instances without the bounded occurrence restriction, or is #P-hard even when restricted to bounded degree input instances. The constant bound in the degree depends on ℱ. The dichotomy criterion on ℱ is decidable. As a second contribution, we prove a slightly modified but more streamlined decision procedure (from [Jin-Yi Cai et al. , 2011]) for tractability. This enables us to fully classify a family of directed weighted graph homomorphism problems. This family contains both P-time tractable problems and #P-hard problems. To our best knowledge, this is the first family of such problems explicitly classified that are not acyclic, thereby the Lovász-goodness criterion of Dyer-Goldberg-Paterson [Martin E. Dyer et al. , 2006] cannot be applied.

SODA Conference 2021 Conference Paper

An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures

• Jin-Yi Cai
• Tianyu Liu 0002

We give the first efficient approximate counting and sampling algorithms for the six-vertex model and the eight-vertex model on regions of the square lattice ℤ 2 in the low temperature regime. All previous algorithms for these problems are for high temperature settings, and rely on the rapid mixing of Markov chains. We prove that these natural Markov chains are torpidly mixing (exponentially slowly) in the low temperature settings. Rather than depending on rapid mixing MCMC, our algorithms are obtained by defining a special edge-2-coloring model, and showing an equivalence to (a linear combination of) abstract polymer models. We then prove the convergence of the cluster expansion of these polymer models. This allows us to employ the approach recently developed by Helmuth, Perkins, and Regts [25]. This combined with Barvinok's method [3, 42] via Taylor expansion (zero-free region of log partition function) gives the approximate counting and sampling algorithms. Significantly, these results provide the first counting problems that admit a fully polynomial time approximation scheme (FPTAS) on square lattice graphs but NP-hard to approximate even on bipartite graphs (rather than the weaker #BIS-hardness.)

SODA Conference 2021 Conference Paper

New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification

• Jin-Yi Cai
• Zhiguo Fu
• Shuai Shao 0001

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.

TCS Journal 2021 Journal Article

The complexity of counting edge colorings for simple graphs

• Jin-Yi Cai
• Artem Govorov

We prove #P-completeness results for counting edge colorings on simple graphs. These strengthen the corresponding results on multigraphs from [4]. We prove that for any κ ≥ r ≥ 3 counting κ-edge colorings on r-regular simple graphs is #P-complete. Furthermore, we show that for planar r-regular simple graphs, where r ∈ { 3, 4, 5 }, counting edge colorings with κ colors for any κ ≥ r is also #P-complete. As there are no planar r-regular simple graphs for any r > 5, these statements cover all interesting cases in terms of the parameters ( κ, r ).

FOCS Conference 2020 Conference Paper

A Dichotomy for Real Boolean Holant Problems

• Shuai Shao 0001
• Jin-Yi Cai

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.

I&C Journal 2020 Journal Article

Beyond #CSP: A dichotomy for counting weighted Eulerian orientations with ARS

• Jin-Yi Cai
• Zhiguo Fu
• Shuai Shao

We define and explore a notion of unique prime factorization for constraint functions, and use this as a new tool to prove a complexity classification for counting weighted Eulerian orientation problems with arrow reversal symmetry (ars). We prove that all such problems are either polynomial-time computable or #P-hard. We show that the class of weighted Eulerian orientation problems subsumes all weighted counting constraint satisfaction problems (#CSP) on Boolean variables. More significantly, we establish a novel connection between #CSP and counting weighted Eulerian orientation problems that is global in nature. This connection is based on a structural determination of all half-weighted affine linear subspaces over Z 2, which is proved using Möbius inversion.

FOCS Conference 2020 Conference Paper

Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs

• Jin-Yi Cai
• Artem Govorov

The complexity of graph homomorphisms has been a subject of intense study [1], [2], [3], [4], [5], [6], [7], [8]. The partition function Z A (·) of graph homomorphism is defined by a symmetric matrix A over C. We prove that the complexity dichotomy of [7] extends to bounded degree graphs. More precisely, we prove that either G → Z A (G) is computable in polynomial-time for every G, or for some Δ > 0 it is #P-hard over (simple) graphs G with maximum degree Δ(G) ≤ Δ. The tractability criterion on A for this dichotomy is explicit, and can be decided in polynomial-time in the size of A. We also show that the dichotomy is effective in that either a P-time algorithm for, or a reduction from #SAT to, Z A (·) can be constructed from A, in the respective cases. cases.

SODA Conference 2019 Conference Paper

Approximability of the Six-vertex Model

• Jin-Yi Cai
• Tianyu Liu 0002
• Pinyan Lu

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 approximability of the partition function on 4-regular graphs, classified according to the parameters of the model. Our complexity results conform to the phase transition phenomenon from physics. We show that the approximation complexity of the six-vertex model behaves dramatically differently on the two sides separated by the phase transition threshold. Furthermore, we present structural properties of the six-vertex model on planar graphs for parameter settings that have known relations to the Tutte polynomial T ( G; x, y ).

SODA Conference 2019 Conference Paper

Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms

• Jin-Yi Cai
• Artem Govorov

We develop a theory of graph algebras over general fields. This is modeled after the theory developed by Freedman, Lovász and Schrijver in [22] for connection matrices, in the study of graph homomorphism functions over real edge weight and positive vertex weight. We introduce connection tensors for graph properties. This notion naturally generalizes the concept of connection matrices. It is shown that counting perfect matchings, and a host of other graph properties naturally defined as Holant problems (edge models), cannot be expressed by graph homomorphism functions over the complex numbers (or even more general fields). Our necessary and sufficient condition in terms of connection tensors is a simple exponential rank bound. It shows that positive semidefiniteness is not needed in the more general setting.

TCS Journal 2018 Journal Article

Clifford gates in the Holant framework

• Jin-Yi Cai
• Heng Guo
• Tyson Williams

We show that the Clifford gates and stabilizer circuits in the quantum computing literature, which admit efficient classical simulation, are equivalent to affine signatures under a unitary condition. The latter is a known class of tractable functions under the Holant framework.

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

I&C Journal 2018 Journal Article

Holographic algorithms beyond matchgates

• Jin-Yi Cai
• Heng Guo
• Tyson Williams

Holographic algorithms introduced by Valiant have two ingredients: matchgates, which are gadgets realizing local constraint functions by weighted planar perfect matchings, and holographic reductions, which show equivalences among problems with different descriptions via basis transformations. In this paper, we replace matchgates in the paradigm above by the affine type and the product type constraint functions, which are known to be tractable in general (not necessarily planar) graphs. We present polynomial-time algorithms to decide if a given counting problem has a holographic reduction to another problem defined by the affine or product-type functions. We also give polynomial-time algorithms to the same problems for symmetric functions, where the complexity is measured in terms of the (exponentially more) succinct representations. The latter result implies that the symmetric Boolean Holant dichotomy (Cai, Guo, and Williams, SICOMP 2016) is efficiently decidable. Our proof techniques are mainly algebraic.

STOC Conference 2017 Conference Paper

Holographic algorithm with matchgates is universal for planar #CSP over boolean domain

• Jin-Yi Cai
• Zhiguo Fu

We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (#CSP) over Boolean variables into exactly three classes: (1) Polynomial-time solvable; (2) #P-hard for general instances, but solvable in polynomial-time over planar structures; and (3) #P-hard over planar structures. The classification applies to all finite sets of complex-valued, not necessarily symmetric, constraint functions on Boolean variables. It is shown that Valiant's holographic algorithm with matchgates is universal strategy for all problems in class (2).

FOCS Conference 2015 Conference Paper

A Holant Dichotomy: Is the FKT Algorithm Universal?

• Jin-Yi Cai
• Zhiguo Fu
• Heng Guo 0001
• Tyson Williams

We prove a complexity dichotomy for complex-weighted Holant problems with an arbitrary set of symmetric constraint functions on Boolean variables. In the study of counting complexity, such as #CSP, there are problems which are #P-hard over general graphs but P-time solvable over planar graphs. A recurring theme has been that a holographic reduction [36] to FKT precisely captures these problems. This dichotomy answers the question: Is this a universal strategy? Surprisingly, we discover new planar tractable problems in the Holant framework (which generalizes #CSP) that are not expressible by a holographic reduction to FKT. In particular, the putative form of a dichotomy for planar Holant problems is false. Nevertheless, we prove a dichotomy for #CSP 2, a variant of #CSP where every variable appears even times, that the presumed universality holds for #CSP 2. This becomes an important tool in the proof of the full dichotomy, which refutes this universality in general. The full dichotomy says that the new P-time algorithms and the strategy of holographic reductions to FKT together are universal for these locally defined counting problems. As a special case of our new planar tractable problems, counting perfect matchings (#PM) over k-uniform hypergraphs is P-time computable when the incidence graph is planar and k ≥ 5. The same problem is #P-hard when k = 3 or k = 4, also a consequence of the dichotomy. More generally, over hypergraphs with specified hyperedge sizes and the same planarity assumption, #PM is P-time computable if the greatest common divisor (gcd) of all hyperedge sizes is at least 5.

I&C Journal 2014 Journal Article

A collapse theorem for holographic algorithms with matchgates on domain size at most 4

• Jin-Yi Cai
• Zhiguo Fu

Holographic algorithms with matchgates are a novel approach to design polynomial time computation. They use Kasteleyn's algorithm for perfect matchings, and more importantly a holographic reduction. The two fundamental parameters of a holographic reduction are the domain size k of the underlying problem and the basis size ℓ. A holographic reduction transforms the computation to matchgates by a linear transformation that maps to (a tensor product space of) a linear space of dimension 2 ℓ. We prove a sharp basis collapse theorem, which shows that for domain size 3 and 4, all non-trivial holographic reductions can be expressed with a basis of size 1 or 2, respectively. The main proof techniques are Matchgate Identities and a Group Property of matchgate signatures.

FOCS Conference 2014 Conference Paper

The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems

• Jin-Yi Cai
• Heng Guo 0001
• Tyson Williams

We show that an effective version of Siegel's Theorem on finiteness of integer solutions for a specific algebraic curve and an application of elementary Galois theory are key ingredients in a complexity classification of some Holant problems. These Holant problems, denoted by Holant(f), are defined by a symmetric ternary function f that is invariant under any permutation of the κ ≥ 3 domain elements. We prove that Holant(f) exhibits a complexity dichotomy. The hardness, and thus the dichotomy, holds even when restricted to planar graphs. A special case of this result is that counting edge κ-colorings is #P-hard over planar 3-regular multigraphs for all κ ≥ 3. In fact, we prove that counting edge κ-colorings is #P-hard over planar r-regular multigraphs for all κ ≥ r ≥ 3. The problem is polynomial-time computable in all other parameter settings. The proof of the dichotomy theorem for Holant(f) depends on the fact that a specific polynomial p(x, y) has an explicitly listed finite set of integer solutions, and the determination of the Galois groups of some specific polynomials. In the process, we also encounter the Tutte polynomial, medial graphs, Eulerian partitions, Puiseux series, and a certain lattice condition on the (logarithm of) the roots of polynomials.

STOC Conference 2013 Conference Paper

A complete dichotomy rises from the capture of vanishing signatures: extended abstract

• Jin-Yi Cai
• Heng Guo 0001
• Tyson Williams

We prove a complexity dichotomy theorem for Holant problems over an arbitrary set of complex-valued symmetric constraint functions {F} on Boolean variables. This extends and unifies all previous dichotomies for Holant problems on symmetric constraint functions (taking values without a finite modulus). We define and characterize all symmetric vanishing signatures. They turned out to be essential to the complete classification of Holant problems. The dichotomy theorem has an explicit tractability criterion. A Holant problem defined by a set of constraint functions {F} is solvable in polynomial time if it satisfies this tractability criterion, and is #P-hard otherwise. The tractability criterion can be intuitively stated as follows: A set {F} is tractable if (1) every function in {F} has arity at most two, or (2) {F} is transformable to an affine type, or (3) {F} is transformable to a product type, or (4) {F} is vanishing, combined with the right type of binary functions, or (5) {F} belongs to a special category of vanishing type Fibonacci gates. The proof of this theorem utilizes many previous dichotomy theorems on Holant problems and Boolean #CSP. Holographic transformations play an indispensable role, not only as a proof technique, but also in the statement of the dichotomy criterion.

SODA Conference 2013 Conference Paper

Dichotomy for Holant* Problems with Domain Size 3

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

TCS Journal 2013 Journal Article

Partition functions on k -regular graphs with { 0, 1 } -vertex assignments and real edge functions

• Jin-Yi Cai
• Michael Kowalczyk

We prove a complexity dichotomy theorem for a class of partition functions over k -regular graphs, for any fixed k. These problems can be viewed as graph homomorphisms from an arbitrary k -regular input graph G to the weighted two vertex graph on { 0, 1 } defined by a real-valued symmetric function h. We completely classify the computational complexity of this problem. We show that there are exactly the following alternatives, for any given h. Depending on h, over k -regular graphs, either 1. the problem is # P-hard even for planar graphs, 2. the problem is # P-hard for general (non-planar) graphs, but solvable in polynomial time for planar graphs, or 3. the problem is solvable in polynomial time for general graphs. The dependence on h is an explicit criterion. Furthermore, we show that in case (2) the problem is solvable in polynomial time over k -regular planar graphs, by exactly the theory of holographic algorithms using matchgates.

STOC Conference 2012 Conference Paper

Complexity of counting CSP with complex weights

• Jin-Yi Cai
• Xi Chen 0001

We give a complexity dichotomy theorem for the counting constraint satisfaction problem (#CSP in short) with algebraic complex weights. To this end, we give three conditions for its tractability. Let F be any finite set of complex-valued functions. We show that #CSP(F) is solvable in polynomial time if all three conditions are satisfied; and is #P-hard otherwise. Our dichotomy theorem generalizes a long series of important results on counting problems: (a) the problem of counting graph homomorphisms is the special case when F has a single symmetric binary function; (b) the problem of counting directed graph homomorphisms is the special case when F has a single but not-necessarily-symmetric binary function; and (c) the unweighted form of #CSP is when all functions in F take values in {0,1}.

TCS Journal 2012 Journal Article

Spin systems on k -regular graphs with complex edge functions

• Jin-Yi Cai
• Michael Kowalczyk

Let k ≥ 1 be an integer and let h = [ h ( 0, 0 ) h ( 0, 1 ) h ( 1, 0 ) h ( 1, 1 ) ] be a complex-valued symmetric function on domain { 0, 1 } (i. e. , where h ( 0, 1 ) = h ( 1, 0 ) ). We introduce a new technique, called a syzygy, and prove a dichotomy theorem for the following class of problems, specified by k and h: given an arbitrary k -regular graph G = ( V, E ), where the function h is attached to each edge, compute Z ( G ) = ∑ σ: V → { 0, 1 } ∏ { u, v } ∈ E h ( σ ( u ), σ ( v ) ). Z ( ⋅ ) is known as the partition function of the spin system, also known as counting graph homomorphisms on domain size two, and is a special case of Holant problems. The dichotomy theorem gives a complete classification of the computational complexity of this problem, depending on k and h. The dependence on k and h is explicit.

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

A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights

• Jin-Yi Cai
• Xi Chen 0001

The complexity of graph homomorphism problems has been the subject of intense study. It is a long standing open problem to give a (decidable) complexity dichotomy theorem for the partition function of directed graph homomorphisms. In this paper, we prove a decidable complexity dichotomy theorem for this problem and our theorem applies to all non-negative weighted form of the problem: given any fixed matrix A with non-negative algebraic entries, the partition function Z A (G) of directed graph homomorphisms from any directed graph G is either tractable in polynomial time or #P-hard, depending on the matrix A. The proof of the dichotomy theorem is combinatorial, but involves the definition of an infinite family of graph homomorphism problems. The proof of its decidability is algebraic using properties of polynomials.

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 2010 Journal Article

On blockwise symmetric signatures for matchgates

• Jin-Yi Cai
• Pinyan Lu

We give a classification of blockwise symmetric signatures in the theory of matchgate computations. The main proof technique uses matchgate identities, also known as useful Grassmann–Plücker identities.

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}.

TCS Journal 2009 Journal Article

Holographic algorithms: The power of dimensionality resolved

• Jin-Yi Cai
• Pinyan Lu

Valiant’s theory of holographic algorithms is a novel methodology to achieve exponential speed-ups in computation. A fundamental parameter in holographic algorithms is the dimension of the linear basis vectors. We completely resolve the problem of the power of higher dimensional bases. We prove that 2-dimensional bases are universal for holographic algorithms.

STOC Conference 2008 Conference Paper

A quadratic lower bound for the permanent and determinant problem over any characteristic! = 2

• Jin-Yi Cai
• Xi Chen 0001
• Dong Li

In Valiant's theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field F of characteristic ≠2, and an integer n, what is the minimum m such that the permanent of an n x n matrix X=(x ij ) can be expressed as a determinant of an m x m matrix, where the entries of the determinant matrix are affine linear functions of x ij 's, and the equality is in F [X]. Mignon and Ressayre (2004) [11] proved a quadratic lower bound m=Ω(n 2 ) for fields of characteristic 0. We extend the Mignon-Ressayre quadratic lower bound to all fields of characteristic ≠2.

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.

SODA Conference 2008 Conference Paper

Holographic algorithms with unsymmetric signatures

• Jin-Yi Cai
• Pinyan Lu

STOC Conference 2007 Conference Paper

Holographic algorithms: from art to science

• Jin-Yi Cai
• Pinyan Lu

We develop the theory of holographic algorithms. We definea basis manifold and give characterizations of algebraic varieties of realizable symmetric generators and recognizers on this manifold. We present a polynomial time decision algorithm for the simultaneous realizability problem. Using the general machinery we are able to giveunexpected holographic algorithms for some counting problems, modulo certain Mersenne type integers. These counting problems are P-complete without the moduli. Going beyond symmetric signatures, we define d -admissibility and d -realizability for general signatures, and give a characterizationof 2-admissibility.

TCS Journal 2007 Journal Article

Valiant’s Holant Theorem and matchgate tensors

• Jin-Yi Cai
• Vinay Choudhary

We propose matchgate tensors as a natural and proper language to develop Valiant’s new theory of Holographic Algorithms. We give a treatment of the central theorem in this theory–the Holant Theorem–in terms of matchgate tensors. Some generalizations are presented.

I&C Journal 2005 Journal Article

Competing provers yield improved Karp–Lipton collapse results

• Jin-Yi Cai
• Venkatesan T. Chakaravarthy
• Lane A. Hemaspaandra
• Mitsunori Ogihara

Via competing provers, we show that if a language A is self-reducible and has polynomial-size circuits then S 2 A = S 2. Building on this, we strengthen the Kämper–AFK theorem, namely, we prove that if NP⊆(NP∩coNP)/poly then the polynomial hierarchy collapses to S 2 NP ∩ coNP. We also strengthen Yap’s theorem, namely, we prove that if NP⊆coNP/poly then the polynomial hierarchy collapses to S 2 NP. Under the same assumptions, the best previously known collapses were to ZPPNP and ZPP NP NP, respectively ([SIAM Journal on Computing 28 (1) (1998) 311; Journal of Computer and System Sciences 52 (3) (1996) 421], building on [Proceedings of the 12th ACM Symposium on Theory of Computing, ACM Press, New York, 1980, pp. 302–309; Journal of Computer and System Sciences 39 (1989) 21; Theoretical Computer Science 85 (2) (1991) 305; Theoretical Computer Science 26 (3) (1983) 287]). It is known that S2 ⊆ZPPNP [Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 2001, pp. 620–629]. That result and its relativized version show that our new collapses indeed improve the previously known results. The Kämper–AFK theorem and Yap’s theorem are used in the literature as bridges in a variety of results—ranging from the study of unique solutions to issues of approximation—and so our results implicitly strengthen those results.

TCS Journal 2003 Journal Article

On testing for zero polynomials by a set of points with bounded precision

• Jin-Yi Cai
• Eric Bach

We consider a general methodology proposed by Chen and Kao for testing polynomial identities. We prove that the test cannot be completely derandomized by any specified set of rational approximations to algebraic numbers up to a polynomial number of bits. The proof is a direct application of Dirichlet's box principle. We also give some number theoretic estimates for the likelihood of a multiplicatively independent sequence of integers which can be used in their algorithm.

FOCS Conference 2001 Conference Paper

On the Average-Case Hardness of CVP

• Jin-Yi Cai

We prove a connection of the worst-case complexity to the average-case complexity based on the Closest Vector Problem (CVP) for lattices. We assume that there is an efficient algorithm which can approximately solve a random instance of CVP, with a non-trivial success probability. For lattices under a certain natural distribution, we show that one can approximately solve several lattice problems (including a version of CVP) efficiently for every lattice with high probability.

FOCS Conference 2001 Conference Paper

S p 2 subseteq ZPP NP

• Jin-Yi Cai

We show that the class S 2 is a subclass of ZPP NP. The proof uses universal hashing, approximate counting and witness sampling. As a consequence, a collapse first noticed by Samik Sengupta that the assumption NP has small circuits collapses PH to S 2 becomes the strongest version to date of the Karp-Lipton Theorem. We also discuss the problem of finding irrefutable proofs for S 2 in ZPP NP.

STOC Conference 2000 Conference Paper

Circuit minimization problem

• Valentine Kabanets
• Jin-Yi Cai

TCS Journal 2000 Journal Article

Resolution of Hartmanis’ conjecture for NL-hard sparse sets

• Jin-Yi Cai
• D. Sivakumar

We resolve a conjecture of Hartmanis from 1978 about sparse hard sets for nondeterministic logspace (NL). We show that there exists a sparse hard set S for NL under logspace many-one reductions if and only if NL=L (deterministic logspace).

I&C Journal 1999 Journal Article

A Lattice-Based Public-Key Cryptosystem

• Jin-Yi Cai
• Thomas W. Cusick

Ajtai recently found a random class of lattices of integer points for which he could prove the following worst-case/average-case equivalence result: If there is a probabilistic polynomial time algorithm which finds a short vector in a random lattice from the class, then there is also a probabilistic polynomial time algorithm which solves several problems related to the shortest lattice vector problem (SVP) in any n-dimensional lattice. Ajtai and Dwork then designed a public-key cryptosystem which is provably secure unless the worst case of a version of the SVP can be solved in probabilistic polynomial time. However, their cryptosystem suffers from massive data expansion because it encrypts data bit-by-bit. Here we present a public-key cryptosystem based on similar ideas, but with much less data expansion.

STOC Conference 1999 Conference Paper

Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time

• Jin-Yi Cai
• Ajay Nerurkar
• D. Sivakumar

TCS Journal 1998 Journal Article

A relation of primal-dual lattices and the complexity of shortest lattice vector problem

• Jin-Yi Cai

We give a simplified proof of a theorem of Lagarias, Lenstra and Schnorr [17] that the problem of approximating the length of the shortest lattice vector within a factor of Cn, for an appropriate constant C, cannot be NP-hard, unless NP = coNP. We also prove that the problem of finding a n 1 4 -unique shortest lattice vector is not NP-hard under polynomial time many-one reductions, unless the polynomial time hierarchy collapses. © 1998—Elsevier Science B. V. All rights reserved

FOCS Conference 1997 Conference Paper

An Improved Worst-Case to Average-Case Connection for Lattice Problems

• Jin-Yi Cai
• Ajay Nerurkar

We improve a connection of the worst-case complexity and the average-case complexity of some well-known lattice problems. This fascinating connection was first discovered by Ajtai (1995). We improve the exponent of this connection from 8 to 3. 5+/spl epsiv/.

FOCS Conference 1997 Conference Paper

Constant Depth Circuits and the Lutz Hypothesis

• Jin-Yi Cai
• D. Sivakumar
• Martin J. Strauss

Resource-bounded measure theory is a study of complexity classes via an adaptation of the probabilistic method. The central hypothesis in this theory is the assertion that NP does not have measure zero in Exponential Time. This is a quantitative strengthening of NP/spl ne/P. We show that the analog in P of this hypothesis fails dramatically. In fact, we show that NTIME[n/sup 1/11/] has measure zero in P. These follow as consequences of our main theorem that the collection of languages accepted by constant-depth nearly exponential-size circuits has measure zero at polynomial time. In contrast, we show that the class AC/sup 0//sub 4/[/spl oplus/] of languages accepted by depth-4 polynomial-size circuits with AND, OR, NOT, and PARITY gates does not have measure zero at polynomial time. Our proof is based on techniques from circuit complexity theory and pseudorandom generators.

SODA Conference 1996 Conference Paper

Multiplicative Equations over Commuting Matrices

• László Babai
• Robert Beals
• Jin-Yi Cai
• Gábor Ivanyos
• Eugene M. Luks

FOCS Conference 1995 Conference Paper

Pseudorandom Generators, Measure Theory, and Natural Proofs

• Kenneth W. Regan
• D. Sivakumar
• Jin-Yi Cai

We prove that if strong pseudorandom number generators exist, then the class of languages that have polynomial-sized circuits (P/poly) is not measurable within exponential time, in terms of the resource-bounded measure theory of Lutz. We prove our result by showing that if P/poly has measure zero in exponential time, then there is a natural proof against P/poly, in the terminology of Razborov and Rudich (1994). We also provide a partial converse of this result.

FOCS Conference 1995 Conference Paper

The Resolution of a Hartmanis Conjecture

• Jin-Yi Cai
• D. Sivakumar

Building on the recent breakthrough by M. Ogihara (1995), we resolve a conjecture made by J. Hartmanis (1978) regarding the (non) existence of sparse sets complete for P under logspace many-one reductions. We show that if there exists a sparse hard set for P under logspace many-one reductions, then P=LOGSPACE. We further prove that if P has a sparse hard set under many-one reductions computable in NC/sup 1/, then P collapses to NC/sup 1/.

FOCS Conference 1994 Conference Paper

Efficient Average-Case Algorithms for the Modular Group

• Jin-Yi Cai
• Wolfgang H. J. Fuchs
• Dexter Kozen
• Zicheng Liu 0001

The modular group occupies a central position in many branches of mathematical sciences. In this paper we give average polynomial-time algorithms for the unbounded and bounded membership problems for finitely generated subgroups of the modular group. The latter result affirms a conjecture of Y. Gurevich (1990). >

SODA Conference 1994 Conference Paper

Reliable Benchmarks Using Numerical Instability

• Sigal Ar
• Jin-Yi Cai

FOCS Conference 1994 Conference Paper

The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices

• Jin-Yi Cai
• Richard J. Lipton
• Yechezkel Zalcstein

We present a deterministic polynomial-time algorithm for the ABC problem, which is the membership problem for 2-generated commutative linear semigroups over an algebraic number field. We also obtain a polynomial time algorithm, for the (easier) membership problem, for 2-generated abelian linear groups. Furthermore, we provide a polynomial-sized encoding for the set of all solutions. >

TCS Journal 1992 Journal Article

On games of incomplete information

• Jin-Yi Cai
• Anne Condon
• Richard J. Lipton

STOC Conference 1992 Conference Paper

Parallel Computation Over Hyperbolic Groups

• Jin-Yi Cai

MFCS Conference 1992 Conference Paper

Promise Problems and Access to Unambiguous Computation

• Jin-Yi Cai
• Lane A. Hemachandra
• Jozef Vyskoc

Abstract This paper studies the power of three types of access to unambiguous computation: nonadaptive access, fault-tolerant access, and guarded access. (1) Though for NP it is known that nonadaptive access has exponentially terse adaptive simulations, we show that UP has no such relativizable simulations: there are worlds in which ( k +1)-truth-table access to UP is not subsumed by k -Turing access to UP. (2) Though fault-tolerant access (i. e. , “1-helping” access) to NP is known to be no more powerful than NP itself, we give both structural and relativized evidence that fault tolerant access to UP suffices to recognize even sets beyond UP. Furthermore, we completely characterize, in terms of locally positive reductions, the sets that fault-tolerantly reduce to UP. (3) In guarded access, Grollmann and Selman's natural notion of access to unambiguous computation, a deterministic polynomial-time Turing machine asks questions to a nondeterministic polynomial-time Turing machine in such a way that the nondeterministic machine never accepts ambiguously. In contrast to guarded access, the standard notion of access to unambiguous computation is that of access to a set that is uniformly unambiguous—even for queries that it never will be asked by its questioner, it must be unambiguous. We show that these notions, though the same for nonadaptive reductions, differ for Turing and strong nondeterministic reductions.

I&C Journal 1990 Journal Article

A note on the determinant and permanent problem

• Jin-Yi Cai

In Valiant's theory of arithmetic complexity, the following question occupies a central position: Given an integer n, what is the minimal m such that the permanent of an n × n matrix is the projection of the determinant of an m × m matrix? More generally, for affine linear transformations, we ask the similar question: what is the minimal m such that the permanent of an n × n matrix is the determinant of an m × m matrix via affine linear transformation? This paper gives the lower bound m ⩾ ⌊ 2 · n ⌋, for affine linear transformations. The result is an improvement of earlier results by von zur Gathen, Babai, and Seress. It also generalizes a classical theorem of Marcus and Minc.

FOCS Conference 1989 Conference Paper

An Optimal Lower Bound on the Number of Variables for Graph Identification

• Jin-Yi Cai
• Martin Fürer
• Neil Immerman

It is shown that Omega (n) variables are needed for first-order logic with counting to identify graphs on n vertices. This settles a long-standing open problem. The lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that three variables suffice to identify all graphs of color class size 3, and two variables suffice to identify almost all graphs. The lower bound is optimal up to multiplication by a constant because n variables obviously suffice to identify graphs on n vertices. >

I&C Journal 1989 Journal Article

Enumerative counting is hard

• Jin-Yi Cai
• Lane A. Hemachandra

An n-variable Boolean formula may have anywhere from 0 to 2 n satisfying assignments. Can a polynomial-time machine, given such a formula, reduce this exponential number of possibilities to a small number of possibilities? We call such a machine an enumerator and prove that if there is a good polynomial-time enumerator for #P (i. e. , one where for every Boolean formula f, the small set has at most O(|f|1−ε ) numbers), then P = NP = P# P and probabilistic polynomial time equals polynomial time. Furthermore, we show that #P polynomial-time Turing reduces to enumerating #P.

FOCS Conference 1989 Conference Paper

Lower Bounds for Constant Depth Circuits in the Presence of Help Bits

• Jin-Yi Cai

The problem of how many extra bits of 'help' a constant depth circuit needs in order to compute m functions is considered. Each help bit can be an arbitrary Boolean function. An exponential lower bound on the size of the circuit computing m parity functions in the presence of m-1 help bits is proved. The proof is carried out using the algebraic machinery of A. Razborov (1987) and R. Smolensky (1987). A by-product of the proof is that the same bound holds for circuits with mod/sub p/ gates for a fixed prime p>2. The lower bound implies a random oracle separation for PH and PSPACE, which is optimal in a technical sense. >

FOCS Conference 1989 Conference Paper

Subquadratic Simulations of Circuits by Branching Programs

• Jin-Yi Cai
• Richard J. Lipton

Boolean circuits and their simulations by bounded-width branching programs are considered. It is shown that every NC/sup 1/ circuit of size s can be simulated by a constant-width branching program of length s/sup 1. 811. .. /. Some related group-theoretic results are presented. >

FOCS Conference 1988 Conference Paper

Take a Walk, Grow a Tree (Preliminary Version)

• Sandeep N. Bhatt
• Jin-Yi Cai

A simple randomized algorithm is presented for maintaining dynamically evolving binary trees on hypercube networks. The algorithm guarantees that: (1) nodes adjacent in the tree are within distance O(log log N) in an N-processor hypercube, and (2) with overwhelming probability, no hypercube processor is assigned more than O(1+M/N) tree nodes, where M is the number of nodes in the tree. The algorithm is distributed and does not require any global information. This is the first load-balancing algorithm with provably good performance. The algorithm can be used to parallelize efficiently any tree-based computation. It can also be used to maintain efficiently dynamic data structures such as quadtrees. A technique called tree surgery is introduced to deal with dependencies inherent in trees. Together with tree surgery, the study of random walks is used to analyze the algorithm. >

STOC Conference 1986 Conference Paper

With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy

• Jin-Yi Cai