BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jin-Yi Cai

Jin-Yi Cai appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational Complexitymath.COData Structures and AlgorithmsDiscrete Mathematicsquant-ph

Catalog footprint

What is connected

24works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

24 published item(s)

preprint2022arXiv

Counting Cycles on Planar Graphs in Subexponential Time

We study the problem of counting all cycles or self-avoiding walks (SAWs) on triangulated planar graphs. We present a subexponential $2^{O(\sqrt{n})}$ time algorithm for this counting problem. Among the technical ingredients used in this algorithm are the planar separator theorem and a delicate analysis using pairs of Motzkin paths and Motzkin numbers. We can then adapt this algorithm to uniformly sample SAWs, in subexponential time. Our work is motivated by the problem of gerrymandered districting maps.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On a Theorem of Lovász that $\hom(\cdot, H)$ Determines the Isomorphism Type of $H$

Graph homomorphism has been an important research topic since its introduction [17]. Stated in the language of binary relational structures in that paper [17], Lovász proved a fundamental theorem that, for a graph $H$ given by its $0$-$1$ valued adjacency matrix, the graph homomorphism function $G \mapsto \hom(G, H)$ determines the isomorphism type of $H$. In the past 50 years various extensions have been proved by many researchers [18, 12, 1, 23, 21]. These extend the basic $0$-$1$ case to admit vertex and edge weights; but these extensions all have some restrictions such as all vertex weights must be positive. In this paper we prove a general form of this theorem where H can have arbitrary vertex and edge weights. A noteworthy aspect is that we prove this by a surprisingly simple and unified argument. This bypasses various technical obstacles and unifies and extends all previous known versions of this theorem on graphs. The constructive proof of our theorem can be used to make various complexity dichotomy theorems for graph homomorphism effective in the following sense: it provides an algorithm that for any $H$ either outputs a P-time algorithm solving $\hom(\cdot, H)$ or a P-time reduction from a canonical #P-hard problem to $\hom(\cdot, H)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A dichotomy for bounded degree graph homomorphisms with nonnegative weights

We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix $A$. Each symmetric matrix $A$ defines a graph homomorphism function $Z_A(\cdot)$, also known as the partition function. Dyer and Greenhill [10] established a complexity dichotomy of $Z_A(\cdot)$ for symmetric $\{0, 1\}$-matrices $A$, and they further proved that its #P-hardness part also holds for bounded degree graphs. Bulatov and Grohe [4] extended the Dyer-Greenhill dichotomy to nonnegative symmetric matrices $A$. However, their hardness proof requires graphs of arbitrarily large degree, and whether the bounded degree part of the Dyer-Greenhill dichotomy can be extended has been an open problem for 15 years. We resolve this open problem and prove that for nonnegative symmetric $A$, either $Z_A(G)$ is in polynomial time for all graphs $G$, or it is #P-hard for bounded degree (and simple) graphs $G$. We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [12] for $Z_A(\cdot)$ also holds for simple graphs, where $A$ is any real symmetric matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Dichotomy for Real Boolean Holant 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 as in previous results. It is proved that for every set $\mathcal{F}$ of real-valued constraint functions, Holant$(\mathcal{F})$ is either P-time computable or #P-hard. The classification has an explicit criterion. This is the culmination of much research on this problem, and it uses previous results and techniques from many researchers. Some particularly intriguing concrete functions $f_6$, $f_8$ and their associated families with extraordinary closure properties related to Bell states in quantum information theory play an important role in this proof.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs

The complexity of graph homomorphisms has been a subject of intense study [11, 12, 4, 42, 21, 17, 6, 20]. The partition function $Z_{\mathbf A}(\cdot)$ of graph homomorphism is defined by a symmetric matrix $\mathbf A$ over $\mathbb C$. We prove that the complexity dichotomy of [6] extends to bounded degree graphs. More precisely, we prove that either $G \mapsto Z_{\mathbf 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) \le Δ$. The tractability criterion on $\mathbf A$ for this dichotomy is explicit, and can be decided in polynomial-time in the size of $\mathbf A$. We also show that the dichotomy is effective in that either a P-time algorithm for, or a reduction from #SAT to, $Z_{\mathbf A}(\cdot)$ can be constructed from $\mathbf A$, in the respective cases.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

From Holant to Quantum Entanglement and Back

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 $|{Ψ_6}\rangle$ of 6 qubits and $|{Ψ_8}\rangle$ of 8 qubits respectively, that have extraordinary and unique 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 an odd-arity signature. The signatures need not be symmetric, and no auxiliary signatures are assumed.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms

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 with both complex vertex and edge weights (or even from 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Holographic Algorithm with Matchgates Is Universal for Planar $\#$CSP Over Boolean Domain

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

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region

Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #SAT to approximate. We study #BIS in the general framework of two-state spin systems on bipartite graphs. We define two notions, nearly-independent phase-correlated spins and unary symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any 2-spin system on bipartite graphs supporting these two notions. As a consequence, we classify the complexity of approximating the partition function of antiferromagnetic 2-spin systems on bounded-degree bipartite graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Holant Dichotomy: Is the FKT Algorithm Universal?

We prove a complexity dichotomy for complex-weighted Holant problems with an arbitrary set of symmetric constraint functions on Boolean variables. This dichotomy is specifically to answer the question: Is the FKT algorithm under a holographic transformation a \emph{universal} strategy to obtain polynomial-time algorithms for problems over planar graphs that are intractable in general? This dichotomy is a culmination of previous ones, including those for Spin Systems, Holant, and #CSP. A recurring theme has been that a holographic reduction to FKT is a universal strategy. Surprisingly, for planar Holant, we discover new planar tractable problems that are not expressible by a holographic reduction to FKT. In previous work, an important tool was a dichotomy for #CSP^d, which denotes #CSP where every variable appears a multiple of d times. However its proof violates planarity. We prove a dichotomy for planar #CSP^2. We apply this planar #CSP^2 dichotomy in the proof of the planar Holant dichotomy. As a special case of our new planar tractable problems, counting perfect matchings (#PM) over k-uniform hypergraphs is polynomial-time computable when the incidence graph is planar and k >= 5. The same problem is #P-hard when k=3 or k=4, which is also a consequence of our dichotomy. When k=2, it becomes #PM over planar graphs and is tractable again. More generally, over hypergraphs with specified hyperedge sizes and the same planarity assumption, #PM is polynomial-time computable if the greatest common divisor of all hyperedge sizes is at least 5.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

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

We show that an effective version of Siegel's Theorem on finiteness of integer solutions 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 k >= 3 domain elements. We prove that Holant(f) exhibits a complexity dichotomy. This dichotomy holds even when restricted to planar graphs. A special case of this result is that counting edge k-colorings is #P-hard over planar 3-regular graphs for k >= 3. In fact, we prove that counting edge k-colorings is #P-hard over planar r-regular graphs for all k >= 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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Collapse Theorem for Holographic Algorithms with Matchgates on Domain Size at Most 4

Holographic algorithms with matchgates are a novel approach to design polynomial time computation. It uses 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 $\ell$. 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^{\ell}$. We prove a sharp basis collapse theorem, that shows that for domain size 3 and 4, all non-trivial holographic reductions have basis size $\ell$ collapse to 1 and 2 respectively. The main proof techniques are Matchgates Identities, and a Group Property of matchgates signatures.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Matchgates Revisited

We study a collection of concepts and theorems that laid the foundation of matchgate computation. This includes the signature theory of planar matchgates, and the parallel theory of characters of not necessarily planar matchgates. Our aim is to present a unified and, whenever possible, simplified account of this challenging theory. Our results include: (1) A direct proof that Matchgate Identities (MGI) are necessary and sufficient conditions for matchgate signatures. This proof is self-contained and does not go through the character theory. More importantly it rectifies a gap in the existing proof. (2) A proof that Matchgate Identities already imply the Parity Condition. (3) A simplified construction of a crossover gadget. This is used in the proof of sufficiency of MGI for matchgate signatures. This is also used to give a proof of equivalence between the signature theory and the character theory which permits omittable nodes. (4) A direct construction of matchgates realizing all matchgate-realizable symmetric signatures.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Dichotomy for Holant* Problems with a Function on Domain Size 3

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. 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 ${\bf F}$ with arity 3 on domain size 3, we give an explicit criterion on ${\bf F}$, such that if ${\bf F}$ satisfies the criterion then the problem ${\rm Holant}^*({\bf F})$ is computable in polynomial time, otherwise ${\rm Holant}^*({\bf F})$ is #P-hard.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Inapproximability After Uniqueness Phase Transition in Two-Spin Systems

A two-state spin system is specified by a 2 x 2 matrix A = {A_{0,0} A_{0,1}, A_{1,0} A_{1,1}} = {β1, 1 γ} where β, γ\ge 0. Given an input graph G=(V,E), the partition function Z_A(G) of a system is defined as Z_A(G) = \sum_{σ: V -> {0,1}} \prod_{(u,v) \in E} A_{σ(u), σ(v)} We prove inapproximability results for the partition function in the region specified by the non-uniqueness condition from phase transition for the Gibbs measure. More specifically, assuming NP \ne RP, for any fixed β, γin the unit square, there is no randomized polynomial-time algorithm that approximates Z_A(G) for d-regular graphs G with relative error ε= 10^{-4}, if d = Ω(Δ(β,γ)), where Δ(β,γ) > 1/(1-βγ) is the uniqueness threshold. Up to a constant factor, this hardness result confirms the conjecture that the uniqueness phase transition coincides with the transition from computational tractability to intractability for Z_A(G). We also show a matching inapproximability result for a region of parameters β, γoutside the unit square, and all our results generalize to partition functions with an external field.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Complexity of Counting CSP with Complex Weights

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

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy

We introduce an idea called anti-gadgets in complexity reductions. These combinatorial gadgets have the effect of erasing the presence of some other graph fragment, as if we had managed to include a negative copy of a graph gadget. We use this idea to prove a complexity dichotomy theorem for the partition function $Z(G)$ on 3-regular directed graphs $G$, where each edge is given a complex-valued binary function $f: \{0,1\}^2 \rightarrow \mathbb{C}$. We show that \[Z(G) = \sum_{σ: V(G) \to \{0,1\}} \prod_{(u,v) \in E(G)} f(σ(u), σ(v)),\] is either computable in polynomial time or #P-hard, depending explicitly on $f$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Graph Homomorphisms with Complex Values: A Dichotomy Theorem

Graph homomorphism has been studied intensively. Given an m x m symmetric matrix A, the graph homomorphism function is defined as \[Z_A (G) = \sum_{f:V->[m]} \prod_{(u,v)\in E} A_{f(u),f(v)}, \] where G = (V,E) is any undirected graph. The function Z_A can encode many interesting graph properties, including counting vertex covers and k-colorings. We study the computational complexity of Z_A for arbitrary symmetric matrices A with algebraic complex values. Building on work by Dyer and Greenhill, Bulatov and Grohe, and especially the recent beautiful work by Goldberg, Grohe, Jerrum and Thurley, we prove a complete dichotomy theorem for this problem. We show that Z_A is either computable in polynomial-time or #P-hard, depending explicitly on the matrix A. We further prove that the tractability criterion on A is polynomial-time decidable.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Holant Problems for Regular Graphs with Complex Edge Functions

We prove a complexity dichotomy theorem for Holant Problems on 3-regular graphs with an arbitrary complex-valued edge function. Three new techniques are introduced: (1) higher dimensional iterations in interpolation; (2) Eigenvalue Shifted Pairs, which allow us to prove that a pair of combinatorial gadgets in combination succeed in proving #P-hardness; and (3) algebraic symmetrization, which significantly lowers the symbolic complexity of the proof for computational complexity. With holographic reductions the classification theorem also applies to problems beyond the basic model.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

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

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

From Holant To #CSP And Back: Dichotomy For Holant$^c$ Problems

We explore the intricate interdependent relationship among counting problems, considered from three frameworks for such problems: Holant Problems, counting CSP and weighted H-colorings. We consider these problems for general complex valued functions that take boolean inputs. We show that results from one framework can be used to derive results in another, and this happens in both directions. Holographic reductions discover an underlying unity, which is only revealed when these counting problems are investigated in the complex domain $\mathbb{C}$. We prove three complexity dichotomy theorems, leading to a general theorem for Holant$^c$ problems. This is the natural class of Holant problems where one can assign constants 0 or 1. More specifically, given any signature grid on $G=(V,E)$ over a set ${\mathscr F}$ of symmetric functions, we completely classify the complexity to be in P or #P-hard, according to ${\mathscr F}$, of \[\sum_{σ: E \rightarrow \{0,1\}} \prod_{v\in V} f_v(σ\mid_{E(v)}),\] where $f_v \in {\mathscr F} \cup \{{\bf 0}, {\bf 1}\}$ ({\bf 0}, {\bf 1} are the unary constant 0, 1 functions). Not only is holographic reduction the main tool, but also the final dichotomy can be only naturally stated in the language of holographic transformations. The proof goes through another dichotomy theorem on boolean complex weighted #CSP.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP

Valiant introduced matchgate 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, matchgate 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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Non-negative Weighted #CSPs: An Effective Complexity Dichotomy

We prove a complexity dichotomy theorem for all non-negative weighted counting Constraint Satisfaction Problems (CSP). This caps a long series of important results on counting problems including unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSP. Our dichotomy theorem gives a succinct criterion for tractability. If a set F of constraint functions satisfies the criterion, then the counting CSP problem defined by F is solvable in polynomial time; if it does not satisfy the criterion, then the problem is #P-hard. We furthermore show that the question of whether F satisfies the criterion is decidable in NP. Surprisingly, our tractability criterion is simpler than the previous criteria for the more restricted classes of problems, although when specialized to those cases, they are logically equivalent. Our proof mainly uses Linear Algebra, and represents a departure from Universal Algebra, the dominant methodology in recent years.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On Tractable Exponential Sums

We consider the problem of evaluating certain exponential sums. These sums take the form $\sum_{x_1,...,x_n \in Z_N} e^{f(x_1,...,x_n) {2 πi / N}} $, where each x_i is summed over a ring Z_N, and f(x_1,...,x_n) is a multivariate polynomial with integer coefficients. We show that the sum can be evaluated in polynomial time in n and log N when f is a quadratic polynomial. This is true even when the factorization of N is unknown. Previously, this was known for a prime modulus N. On the other hand, for very specific families of polynomials of degree \ge 3, we show the problem is #P-hard, even for any fixed prime or prime power modulus. This leads to a complexity dichotomy theorem - a complete classification of each problem to be either computable in polynomial time or #P-hard - for a class of exponential sums. These sums arise in the classifications of graph homomorphisms and some other counting CSP type problems, and these results lead to complexity dichotomy theorems. For the polynomial-time algorithm, Gauss sums form the basic building blocks. For the hardness results, we prove group-theoretic necessary conditions for tractability. These tests imply that the problem is #P-hard for even very restricted families of simple cubic polynomials over fixed modulus N.

0 citations0 reviewsNo code linkedOpen access