Jin-Yi Cai

Publication Activity (10 Years)

Years Active: 1987-2024
Publications (10 Years): 75

Top Venues

CoRR

SODA

Inf. Comput.

J. Comput. Syst. Sci.

Publications

Jin-Yi Cai, Ashwin Maran
Counting Cycles on Planar Graphs in Subexponential Time. Algorithmica 86 (2) (2024)
Jin-Yi Cai, Jacob Kruse, Kenneth Mayer, Daniel P. Szabo
A Uniformly Random Solution to Algorithmic Redistricting. CoRR (2024)
Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, Michael Kowalczyk
A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory. Comput. Complex. 32 (1) (2023)
Jin-Yi Cai, Austen Z. Fan, Yin Liu
Bipartite 3-regular counting problems with mixed signs. J. Comput. Syst. Sci. 135 (2023)
Jin-Yi Cai, Ben Young
Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint. ICALP (2023)
Yin Liu, Austen Z. Fan, Jin-Yi Cai
Restricted Holant Dichotomy on Domains 3 and 4. CoRR (2023)
Niclas Boehmer, Jin-Yi Cai, Piotr Faliszewski, Austen Z. Fan, Lukasz Janeczko, Andrzej Kaczmarczyk, Tomasz Was
Properties of Position Matrices and Their Elections. AAAI (2023)
Yin Liu, Austen Z. Fan, Jin-Yi Cai
Restricted Holant Dichotomy on Domains 3 and 4. COCOA (2) (2023)
Jin-Yi Cai, Austen Z. Fan
Planar 3-way Edge Perfect Matching Leads to A Holant Dichotomy. CoRR (2023)
Jin-Yi Cai
Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise. CoRR (2023)
Jin-Yi Cai, Zhiguo Fu
Complexity classification of the eight-vertex model. Inf. Comput. 293 (2023)
Niclas Boehmer, Jin-Yi Cai, Piotr Faliszewski, Austen Z. Fan, Lukasz Janeczko, Andrzej Kaczmarczyk, Tomasz Was
Properties of Position Matrices and Their Elections. CoRR (2023)
Zhiguo Fu, Jin-Yi Cai
Holographic Algorithms on Domains of General Size. Theory Comput. Syst. 67 (3) (2023)
Austen Z. Fan, Jin-Yi Cai
Dichotomy result on 3-regular bipartite non-negative functions. Theor. Comput. Sci. 949 (2023)
Artem Govorov, Jin-Yi Cai, Martin E. Dyer
A dichotomy for bounded degree graph homomorphisms with nonnegative weights. J. Comput. Syst. Sci. 132 (2023)
Jin-Yi Cai, Ashwin Maran
The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3. STOC (2023)
Jin-Yi Cai, Ashwin Maran
The complexity of counting planar graph homomorphisms of domain size 3. CoRR (2023)
Jin-Yi Cai, Ashwin Maran
Counting Cycles on Planar Graphs in Subexponential Time. CoRR (2022)
Jin-Yi Cai, Ashwin Maran
Counting Cycles on Planar Graphs in Subexponential Time. COCOON (2022)
Jin-Yi Cai, Ben Young
Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint. CoRR (2022)
Jin-Yi Cai, Artem Govorov
Perfect matchings, rank of connection tensors and graph homomorphisms. Comb. Probab. Comput. 31 (2) (2022)
Jin-Yi Cai, Daniel P. Szabo
Bounded Degree Nonnegative Counting CSP. MFCS (2022)
Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams
FKT is Not Universal - A Planar Holant Dichotomy for Symmetric Constraints. Theory Comput. Syst. 66 (1) (2022)
Jin-Yi Cai, Zhiguo Fu
Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain. SIAM J. Comput. 51 (2) (2022)
Jin-Yi Cai, Austen Z. Fan, Yin Liu
Bipartite 3-Regular Counting Problems with Mixed Signs. FCT (2021)
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification. SODA (2021)
Jin-Yi Cai, Artem Govorov
The complexity of counting edge colorings for simple graphs. Theor. Comput. Sci. 889 (2021)
Jin-Yi Cai, Tianyu Liu
An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures. SODA (2021)
Jin-Yi Cai, Austen Z. Fan, Yin Liu
Bipartite 3-Regular Counting Problems with Mixed Signs. CoRR (2021)
Austen Z. Fan, Jin-Yi Cai
Dichotomy Result on 3-Regular Bipartite Non-negative Functions. CSR (2021)
Jin-Yi Cai, Artem Govorov
The Complexity of Counting Edge Colorings for Simple Graphs. CoRR (2020)
Austen Z. Fan, Jin-Yi Cai
Dichotomy Result on 3-Regular Bipartite Non-negative Functions. CoRR (2020)
Artem Govorov, Jin-Yi Cai, Martin E. Dyer
A dichotomy for bounded degree graph homomorphisms with nonnegative weights. CoRR (2020)
Jin-Yi Cai, Tianyu Liu
FPRAS via MCMC where it mixes torpidly (and very little effort). CoRR (2020)
Jin-Yi Cai, Tianyu Liu
Counting Perfect Matchings and the Eight-Vertex Model. ICALP (2020)
Jin-Yi Cai, Artem Govorov
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs. FOCS (2020)
Shuai Shao, Jin-Yi Cai
A Dichotomy for Real Boolean Holant Problems. FOCS (2020)
Artem Govorov, Jin-Yi Cai, Martin E. Dyer
A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights. ICALP (2020)
Jin-Yi Cai, Tianyu Liu, Pinyan Lu, Jing Yu
Approximability of the Eight-Vertex Model. Computational Complexity Conference (2020)
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
From Holant to Quantum Entanglement and Back. ICALP (2020)
Jin-Yi Cai, Artem Govorov
On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H. ITCS (2020)
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
From Holant to Quantum Entanglement and Back. CoRR (2020)
Jin-Yi Cai, Pinyan Lu, Mingji Xia
Problems on the Boolean Domain. Theory Comput. Syst. 64 (8) (2020)
Shuai Shao, Jin-Yi Cai
A Dichotomy for Real Boolean Holant Problems. CoRR (2020)
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
Beyond #CSP: A dichotomy for counting weighted Eulerian orientations with ARS. Inf. Comput. 275 (2020)
Jin-Yi Cai, Artem Govorov
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs. CoRR (2020)
Jin-Yi Cai, Artem Govorov
Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms. CoRR (2019)
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
Complexity of Counting Weighted Eulerian Orientations with ARS. CoRR (2019)
Jin-Yi Cai, Michael Kowalczyk, Tyson Williams
Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy. ACM Trans. Comput. Theory 11 (2) (2019)
Jin-Yi Cai, Tianyu Liu, Pinyan Lu
Approximability of the Six-vertex Model. SODA (2019)
Jin-Yi Cai, Tianyu Liu
Counting perfect matchings and the eight-vertex model. CoRR (2019)
Jin-Yi Cai, Artem Govorov
Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms. SODA (2019)
Jin-Yi Cai, Artem Govorov
On a Theorem of Lovász that hom(·, H) Determines the Isomorhphism Type of H. CoRR (2019)
Jin-Yi Cai, Xi Chen
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. Comput. Complex. 28 (3) (2019)
Jin-Yi Cai, Tianyu Liu, Pinyan Lu, Jing Yu
Approximability of the Eight-vertex Model. CoRR (2018)
Jin-Yi Cai, Heng Guo, Tyson Williams
Clifford gates in the Holant framework. Theor. Comput. Sci. 745 (2018)
Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, Michael Kowalczyk
A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory. ITCS (2018)
Jin-Yi Cai, Pinyan Lu, Mingji Xia
Problems. SODA (2018)
Jin-Yi Cai, Heng Guo, Tyson Williams
Holographic algorithms beyond matchgates. Inf. Comput. 259 (1) (2018)
Jin-Yi Cai, Zhiguo Fu, Mingji Xia
Complexity classification of the six-vertex model. Inf. Comput. 259 (Part) (2018)
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
A Complexity Trichotomy for the Six-Vertex Model. CoRR (2017)
Jin-Yi Cai, Zhiguo Fu
Complexity Classification of the Eight-Vertex Model. CoRR (2017)
Jin-Yi Cai, Zhiguo Fu, Mingji Xia
Complexity Classification Of The Six-Vertex Model. CoRR (2017)
Jin-Yi Cai, Heng Guo, Tyson Williams
Clifford Gates in the Holant Framework. CoRR (2017)
Jin-Yi Cai, Pinyan Lu, Mingji Xia
Problems. CoRR (2017)
Jin-Yi Cai, Xi Chen
Complexity of Counting CSP with Complex Weights. J. ACM 64 (3) (2017)
Jin-Yi Cai, Zhiguo Fu
Holographic algorithm with matchgates is universal for planar #CSP over boolean domain. STOC (2017)
Jin-Yi Cai, Pinyan Lu, Mingji Xia
Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. SIAM J. Comput. 46 (3) (2017)
Jin-Yi Cai, Tianyu Liu, Pinyan Lu
Approximability of the Six-vertex Model. CoRR (2017)
Jin-Yi Cai, Zhiguo Fu
Holographic Algorithm with Matchgates Is Universal for Planar $\#$CSP Over Boolean Domain. CoRR (2016)
Jin-Yi Cai, Heng Guo, Tyson Williams
A Complete Dichotomy Rises from the Capture of Vanishing Signatures. SIAM J. Comput. 45 (5) (2016)
Jin-Yi Cai, Xi Chen, Pinyan Lu
Nonnegative Weighted #CSP: An Effective Complexity Dichotomy. SIAM J. Comput. 45 (6) (2016)
Michael Kowalczyk, Jin-Yi Cai
Holant Problems for 3-Regular Graphs with Complex Edge Functions. Theory Comput. Syst. 59 (1) (2016)
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, Eric Vigoda
#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. J. Comput. Syst. Sci. 82 (5) (2016)
Jin-Yi Cai, Pinyan Lu
Erratum to: Signature Theory in Holographic Algorithms. Algorithmica 74 (4) (2016)
Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams
A Holant Dichotomy: Is the FKT Algorithm Universal? CoRR (2015)
Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams
A Holant Dichotomy: Is the FKT Algorithm Universal? FOCS (2015)
Jin-Yi Cai, Pinyan Lu, Mingji Xia
The complexity of complex weighted Boolean #CSP. J. Comput. Syst. Sci. 80 (1) (2014)
Jin-Yi Cai, Aaron Gorenstein
Matchgates Revisited. Theory Comput. 10 (2014)
Jin-Yi Cai, Heng Guo, Tyson Williams
The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. FOCS (2014)
Jin-Yi Cai, Heng Guo, Tyson Williams
The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. CoRR (2014)
Jin-Yi Cai, Zhiguo Fu
A collapse theorem for holographic algorithms with matchgates on domain size at most 4. Inf. Comput. 239 (2014)
Jin-Yi Cai, Heng Guo, Tyson Williams
Holographic Algorithms Beyond Matchgates. ICALP (1) (2014)
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, Eric Vigoda
#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. APPROX-RANDOM (2014)
Byron J. Gao, Martin Ester, Hui Xiong, Jin-Yi Cai, Oliver Schulte
The Minimum Consistent Subset Cover Problem: A Minimization View of Data Mining. IEEE Trans. Knowl. Data Eng. 25 (3) (2013)
Jin-Yi Cai, Heng Guo, Tyson Williams
Holographic Algorithms Beyond Matchgates. CoRR (2013)
Jin-Yi Cai, Xi Chen, Pinyan Lu
Graph Homomorphisms with Complex Values: A Dichotomy Theorem. SIAM J. Comput. 42 (3) (2013)
Jin-Yi Cai, Pinyan Lu, Mingji Xia
Dichotomy for Holant* Problems with Domain Size 3. SODA (2013)
Chen Zeng, Jin-Yi Cai, Pinyan Lu, Jeffrey F. Naughton
On optimal differentially private mechanisms for count-range queries. ICDT (2013)
Jin-Yi Cai, Leslie Ann Goldberg, Heng Guo, Mark Jerrum
Approximating the Partition Function of Two-Spin Systems on Bipartite Graphs. CoRR (2013)
Jin-Yi Cai, Zhiguo Fu
A Collapse Theorem for Holographic Algorithms with Matchgates on Domain Size at Most 4 CoRR (2013)
Jin-Yi Cai, Heng Guo, Tyson Williams
A complete dichotomy rises from the capture of vanishing signatures: extended abstract. STOC (2013)
Jin-Yi Cai
Complexity Dichotomy for Counting Problems. LATA (2013)
Jin-Yi Cai, Aaron Gorenstein
Matchgates Revisited CoRR (2013)
Jin-Yi Cai, Michael Kowalczyk
k-regular graphs with {0, 1}{0, 1}-vertex assignments and real edge functions. Theor. Comput. Sci. 494 (2013)
Jin-Yi Cai, Aaron Gorenstein
Matchgates Revisited. Electron. Colloquium Comput. Complex. 20 (2013)
Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu
Inapproximability after Uniqueness Phase Transition in Two-Spin Systems. COCOA (2012)
Zhiguo Fu, Jin-Yi Cai
Holographic Algorithms on Domain Size k > 2. TAMC (2012)
Jin-Yi Cai, Michael Kowalczyk
Spin systems on k-regular graphs with complex edge functions. Theor. Comput. Sci. 461 (2012)
Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu
Inapproximability After Uniqueness Phase Transition in Two-Spin Systems CoRR (2012)

Jin-Yi Cai.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Jin-Yi Cai