37 citations · 213 across the 42 of their papers we have counts for
46 papers
Restricted Holant Dichotomy on Domains 3 and 4
Yin Liu, Austen Z. Fan, Jin-Yi Cai
denotes a class of counting problems specified by a constraint function . We prove complexity dichotomy theorems for in…
Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise
Jin-Yi Cai
We consider Shor's quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algor…
Planar 3-way Edge Perfect Matching Leads to A Holant Dichotomy
Jin-Yi Cai, Austen Z. Fan
We prove a complexity dichotomy theorem for a class of Holant problems on planar 3-regular bipartite graphs. The complexity dichotomy states that for every weighted constraint func…
Properties of Position Matrices and Their Elections
Niclas Boehmer, Jin-Yi Cai, Piotr Faliszewski +4
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).…
The complexity of counting planar graph homomorphisms of domain size 3
Jin-Yi Cai, Ashwin Maran
We prove a complexity dichotomy theorem for counting planar graph homomorphisms of domain size 3. Given any 3 by 3 real valued symmetric matrix defining a graph homomorphism fr…
Planar #CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint
Jin-Yi Cai, Ben Young
Recently, Mančinska and Roberson proved that two graphs and are quantum isomorphic if and only if they admit the same number of homomorphisms from all planar graphs. We ex…