Jin-Yi Cai | DeepAI

AI Chat

Featured Co-authors

Tianyu Liu
68 publications
Piotr Faliszewski
35 publications
Niclas Boehmer
32 publications
Pinyan Lu
30 publications
Shuai Shao
29 publications
Jing Yu
28 publications
Andrzej Kaczmarczyk
12 publications
Martin Dyer
11 publications
Austen Z. Fan
8 publications
Zhiguo Fu
6 publications
Tomasz Wąs
6 publications

∙ 07/29/2023

Restricted Holant Dichotomy on Domains 3 and 4

Holant^*(f) denotes a class of counting problems specified by a constrai...

0 Yin Liu, et al. ∙

∙ 06/15/2023

Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise

We consider Shor's quantum factoring algorithm in the setting of noisy q...

0 Jin-Yi Cai, et al. ∙

∙ 03/29/2023

Planar 3-way Edge Perfect Matching Leads to A Holant Dichotomy

We prove a complexity dichotomy theorem for a class of Holant problems o...

0 Jin-Yi Cai, et al. ∙

∙ 03/05/2023

Properties of Position Matrices and Their Elections

We study the properties of elections that have a given position matrix (...

0 Niclas Boehmer, et al. ∙

∙ 02/16/2023

The complexity of counting planar graph homomorphisms of domain size 3

We prove a complexity dichotomy theorem for counting planar graph homomo...

0 Jin-Yi Cai, et al. ∙

∙ 12/06/2022

Planar #CSP Equality Corresponds to Quantum Isomorphism – A Holant Viewpoint

Recently, Mančinska and Roberson proved that two graphs G and G' are qua...

0 Jin-Yi Cai, et al. ∙

∙ 08/21/2022

Counting Cycles on Planar Graphs in Subexponential Time

We study the problem of counting all cycles or self-avoiding walks (SAWs...

0 Jin-Yi Cai, et al. ∙

∙ 10/04/2021

Bipartite 3-Regular Counting Problems with Mixed Signs

We prove a complexity dichotomy for a class of counting problems express...

0 Jin-Yi Cai, et al. ∙

∙ 11/18/2020

Dichotomy Result on 3-Regular Bipartite Non-negative Functions

We prove a complexity dichotomy theorem for a class of Holant problems o...

0 Austen Z. Fan, et al. ∙

∙ 10/12/2020

FPRAS via MCMC where it mixes torpidly (and very little effort)

Is Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for a p...

0 Jin-Yi Cai, et al. ∙

∙ 10/10/2020

The Complexity of Counting Edge Colorings for Simple Graphs

We prove #P-completeness results for counting edge colorings on simple g...

0 Jin-Yi Cai, et al. ∙

∙ 05/16/2020

A Dichotomy for Real Boolean Holant Problems

We prove a complexity dichotomy for Holant problems on the boolean domai...

0 Shuai Shao, et al. ∙

∙ 04/14/2020

Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs

The complexity of graph homomorphisms has been a subject of intense stud...

0 Jin-Yi Cai, et al. ∙

∙ 04/12/2020

From Holant to Quantum Entanglement and Back

Holant problems are intimately connected with quantum theory as tensor n...

0 Jin-Yi Cai, et al. ∙

∙ 02/05/2020

A dichotomy for bounded degree graph homomorphisms with nonnegative weights

We consider the complexity of counting weighted graph homomorphisms defi...

0 Artem Govorov, et al. ∙

∙ 09/09/2019

On a Theorem of Lovász that (·, H) Determines the Isomorhphism Type of H

Graph homomorphism has been an important research topic since its introd...

0 Jin-Yi Cai, et al. ∙

∙ 09/07/2019

Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms

We develop a theory of graph algebras over general fields. This is model...

0 Jin-Yi Cai, et al. ∙

∙ 04/23/2019

Counting perfect matchings and the eight-vertex model

We study the approximation complexity of the partition function of the e...

0 Jin-Yi Cai, et al. ∙

∙ 04/04/2019

Complexity of Counting Weighted Eulerian Orientations with ARS

Unique prime factorization of integers is taught in every high school. W...

0 Jin-Yi Cai, et al. ∙

∙ 11/07/2018

Approximability of the Eight-vertex Model

We initiate a study of the classification of approximation complexity of...

0 Jin-Yi Cai, et al. ∙

∙ 12/16/2017

Approximability of the Six-vertex Model

In this paper we take the first step toward a classification of the appr...

0 Jin-Yi Cai, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world