Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDJin-Yi Cai
Jin-yi Cai
Person information
- affiliation: University of Wisconsin-Madison, Madison, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[j100]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): 4 (2023)- [j99]Jin-Yi Cai, Zhiguo Fu
:
Complexity classification of the eight-vertex model. Inf. Comput. 293: 105064 (2023) - [j98]Artem Govorov, Jin-Yi Cai, Martin E. Dyer:
A dichotomy for bounded degree graph homomorphisms with nonnegative weights. J. Comput. Syst. Sci. 132: 1-15 (2023) - [j97]Jin-Yi Cai, Austen Z. Fan, Yin Liu:
Bipartite 3-regular counting problems with mixed signs. J. Comput. Syst. Sci. 135: 15-31 (2023) - [j96]Zhiguo Fu, Jin-Yi Cai:
Holographic Algorithms on Domains of General Size. Theory Comput. Syst. 67(3): 417-436 (2023) - [j95]Austen Z. Fan, Jin-Yi Cai:
Dichotomy result on 3-regular bipartite non-negative functions. Theor. Comput. Sci. 949: 113745 (2023) - [c125]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: 5507-5514 - [c124]Jin-Yi Cai, Ben Young:
Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint. ICALP 2023: 33:1-33:17 - [c123]Jin-Yi Cai, Ashwin Maran:
The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3. STOC 2023: 1285-1297 - [i65]Jin-Yi Cai, Ashwin Maran:
The complexity of counting planar graph homomorphisms of domain size 3. CoRR abs/2302.08570 (2023) - [i64]Niclas Boehmer, Jin-Yi Cai, Piotr Faliszewski, Austen Z. Fan, Lukasz Janeczko, Andrzej Kaczmarczyk, Tomasz Was:
Properties of Position Matrices and Their Elections. CoRR abs/2303.02538 (2023) - [i63]Jin-Yi Cai, Austen Z. Fan:
Planar 3-way Edge Perfect Matching Leads to A Holant Dichotomy. CoRR abs/2303.16705 (2023) - [i62]Jin-Yi Cai:
Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise. CoRR abs/2306.10072 (2023) - [i61]Yin Liu, Austen Z. Fan, Jin-Yi Cai:
Restricted Holant Dichotomy on Domains 3 and 4. CoRR abs/2307.16078 (2023) - 2022
- [j94]Jin-Yi Cai, Artem Govorov:
Perfect matchings, rank of connection tensors and graph homomorphisms. Comb. Probab. Comput. 31(2): 268-303 (2022) - [j93]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): 143-308 (2022) - [j92]Jin-Yi Cai, Zhiguo Fu:
Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain. SIAM J. Comput. 51(2): 17-50 (2022) - [c122]Jin-Yi Cai, Ashwin Maran:
Counting Cycles on Planar Graphs in Subexponential Time. COCOON 2022: 268-279 - [c121]Jin-Yi Cai, Daniel P. Szabo:
Bounded Degree Nonnegative Counting CSP. MFCS 2022: 27:1-27:16 - [i60]Jin-Yi Cai, Ashwin Maran:
Counting Cycles on Planar Graphs in Subexponential Time. CoRR abs/2208.09948 (2022) - [i59]Jin-Yi Cai, Ben Young:
Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint. CoRR abs/2212.03335 (2022) - 2021
- [j91]Jin-Yi Cai, Artem Govorov:
The complexity of counting edge colorings for simple graphs. Theor. Comput. Sci. 889: 14-24 (2021) - [j90]Jin-yi Cai, Artem Govorov:
On a Theorem of Lovász that (&sdot, H) Determines the Isomorphism Type of H. ACM Trans. Comput. Theory 13(2): 11:1-11:25 (2021) - [c120]Austen Z. Fan, Jin-Yi Cai:
Dichotomy Result on 3-Regular Bipartite Non-negative Functions. CSR 2021: 102-115 - [c119]Jin-Yi Cai, Austen Z. Fan, Yin Liu:
Bipartite 3-Regular Counting Problems with Mixed Signs. FCT 2021: 135-148 - [c118]Jin-Yi Cai, Tianyu Liu:
An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures. SODA 2021: 1520-1534 - [c117]Jin-Yi Cai, Zhiguo Fu, Shuai Shao:
New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification. SODA 2021: 1535-1547 - [i58]Jin-Yi Cai, Austen Z. Fan, Yin Liu:
Bipartite 3-Regular Counting Problems with Mixed Signs. CoRR abs/2110.01173 (2021) - 2020
- [j89]Jin-Yi Cai, Zhiguo Fu, Shuai Shao:
Beyond #CSP: A dichotomy for counting weighted Eulerian orientations with ARS. Inf. Comput. 275: 104589 (2020) - [j88]Jin-Yi Cai, Pinyan Lu, Mingji Xia:
Dichotomy for Holant∗ Problems on the Boolean Domain. Theory Comput. Syst. 64(8): 1362-1391 (2020) - [c116]Jin-Yi Cai, Tianyu Liu, Pinyan Lu, Jing Yu:
Approximability of the Eight-Vertex Model. CCC 2020: 4:1-4:18 - [c115]Shuai Shao, Jin-Yi Cai:
A Dichotomy for Real Boolean Holant Problems. FOCS 2020: 1091-1102 - [c114]Jin-Yi Cai, Artem Govorov:
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs. FOCS 2020: 1103-1111 - [c113]Jin-Yi Cai, Zhiguo Fu, Shuai Shao:
From Holant to Quantum Entanglement and Back. ICALP 2020: 22:1-22:16 - [c112]Jin-Yi Cai, Tianyu Liu:
Counting Perfect Matchings and the Eight-Vertex Model. ICALP 2020: 23:1-23:18 - [c111]Artem Govorov, Jin-Yi Cai, Martin E. Dyer:
A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights. ICALP 2020: 66:1-66:18 - [c110]Jin-Yi Cai, Artem Govorov:
On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H. ITCS 2020: 17:1-17:15 - [i57]Artem Govorov, Jin-Yi Cai, Martin E. Dyer:
A dichotomy for bounded degree graph homomorphisms with nonnegative weights. CoRR abs/2002.02021 (2020) - [i56]Jin-Yi Cai, Zhiguo Fu, Shuai Shao:
From Holant to Quantum Entanglement and Back. CoRR abs/2004.05706 (2020) - [i55]Jin-Yi Cai, Artem Govorov:
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs. CoRR abs/2004.06620 (2020) - [i54]Shuai Shao, Jin-Yi Cai:
A Dichotomy for Real Boolean Holant Problems. CoRR abs/2005.07906 (2020) - [i53]Jin-Yi Cai, Artem Govorov:
The Complexity of Counting Edge Colorings for Simple Graphs. CoRR abs/2010.04910 (2020) - [i52]Jin-Yi Cai, Tianyu Liu:
FPRAS via MCMC where it mixes torpidly (and very little effort). CoRR abs/2010.05425 (2020) - [i51]Austen Z. Fan, Jin-Yi Cai:
Dichotomy Result on 3-Regular Bipartite Non-negative Functions. CoRR abs/2011.09110 (2020)
2010 – 2019
- 2019
- [j87]Jin-Yi Cai, Xi Chen:
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. Comput. Complex. 28(3): 345-408 (2019) - [j86]Jin-Yi Cai, Michael Kowalczyk, Tyson Williams:
Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy. ACM Trans. Comput. Theory 11(2): 7:1-7:26 (2019) - [c109]Jin-Yi Cai, Artem Govorov:
Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms. SODA 2019: 476-495 - [c108]Jin-Yi Cai, Tianyu Liu, Pinyan Lu:
Approximability of the Six-vertex Model. SODA 2019: 2248-2261 - [i50]Jin-Yi Cai, Zhiguo Fu, Shuai Shao:
Complexity of Counting Weighted Eulerian Orientations with ARS. CoRR abs/1904.02362 (2019) - [i49]Jin-Yi Cai, Tianyu Liu:
Counting perfect matchings and the eight-vertex model. CoRR abs/1904.10493 (2019) - [i48]Jin-Yi Cai, Artem Govorov:
Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms. CoRR abs/1909.03179 (2019) - [i47]Jin-Yi Cai, Artem Govorov:
On a Theorem of Lovász that hom(·, H) Determines the Isomorhphism Type of H. CoRR abs/1909.03693 (2019) - 2018
- [j85]Jin-Yi Cai, Heng Guo, Tyson Williams:
Holographic algorithms beyond matchgates. Inf. Comput. 259(1): 102-129 (2018) - [j84]Jin-Yi Cai, Zhiguo Fu, Mingji Xia:
Complexity classification of the six-vertex model. Inf. Comput. 259(Part): 130-141 (2018) - [j83]Jin-Yi Cai, Heng Guo, Tyson Williams:
Clifford gates in the Holant framework. Theor. Comput. Sci. 745: 163-171 (2018) - [c107]Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, Michael Kowalczyk:
A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory. ITCS 2018: 2:1-2:22 - [c106]Jin-Yi Cai, Pinyan Lu, Mingji Xia:
Dichotomy for Real Holantc Problems. SODA 2018: 1802-1821 - [i46]Jin-Yi Cai, Tianyu Liu, Pinyan Lu, Jing Yu:
Approximability of the Eight-vertex Model. CoRR abs/1811.03126 (2018) - 2017
- [j82]Jin-Yi Cai, Xi Chen:
Complexity of Counting CSP with Complex Weights. J. ACM 64(3): 19:1-19:39 (2017) - [j81]Jin-Yi Cai, Pinyan Lu, Mingji Xia:
Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. SIAM J. Comput. 46(3): 853-889 (2017) - [c105]Jin-Yi Cai, Zhiguo Fu:
Holographic algorithm with matchgates is universal for planar #CSP over boolean domain. STOC 2017: 842-855 - [i45]Jin-Yi Cai, Pinyan Lu, Mingji Xia:
Dichotomy for Real Holantc Problems. CoRR abs/1702.02693 (2017) - [i44]Jin-Yi Cai, Zhiguo Fu, Mingji Xia:
Complexity Classification Of The Six-Vertex Model. CoRR abs/1702.02863 (2017) - [i43]Jin-Yi Cai, Zhiguo Fu:
Complexity Classification of the Eight-Vertex Model. CoRR abs/1702.07938 (2017) - [i42]Jin-Yi Cai, Zhiguo Fu, Shuai Shao:
A Complexity Trichotomy for the Six-Vertex Model. CoRR abs/1704.01657 (2017) - [i41]Jin-Yi Cai, Heng Guo, Tyson Williams:
Clifford Gates in the Holant Framework. CoRR abs/1705.00942 (2017) - [i40]Jin-Yi Cai, Tianyu Liu, Pinyan Lu:
Approximability of the Six-vertex Model. CoRR abs/1712.05880 (2017) - 2016
- [j80]Jin-Yi Cai, Pinyan Lu:
Erratum to: Signature Theory in Holographic Algorithms. Algorithmica 74(4): 1473-1476 (2016) - [j79]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): 690-711 (2016) - [j78]Michael Kowalczyk, Jin-Yi Cai:
Holant Problems for 3-Regular Graphs with Complex Edge Functions. Theory Comput. Syst. 59(1): 133-158 (2016) - [j77]Jin-Yi Cai, Heng Guo, Tyson Williams:
A Complete Dichotomy Rises from the Capture of Vanishing Signatures. SIAM J. Comput. 45(5): 1671-1728 (2016) - [j76]Jin-Yi Cai, Xi Chen, Pinyan Lu:
Nonnegative Weighted #CSP: An Effective Complexity Dichotomy. SIAM J. Comput. 45(6): 2177-2198 (2016) - [r3]Jin-Yi Cai, Xi Chen, Pinyan Lu:
Complexity Dichotomies for Counting Graph Homomorphisms. Encyclopedia of Algorithms 2016: 366-369 - [r2]Jin-Yi Cai, Heng Guo, Tyson Williams:
Holant Problems. Encyclopedia of Algorithms 2016: 918-921 - [r1]Jin-Yi Cai, Pinyan Lu, Mingji Xia:
Holographic Algorithms. Encyclopedia of Algorithms 2016: 921-926 - [i39]Jin-Yi Cai, Zhiguo Fu:
Holographic Algorithm with Matchgates Is Universal for Planar $\#$CSP Over Boolean Domain. CoRR abs/1603.07046 (2016) - 2015
- [c104]Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams:
A Holant Dichotomy: Is the FKT Algorithm Universal? FOCS 2015: 1259-1276 - [i38]Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams:
A Holant Dichotomy: Is the FKT Algorithm Universal? CoRR abs/1505.02993 (2015) - 2014
- [j75]Jin-Yi Cai, Zhiguo Fu:
A collapse theorem for holographic algorithms with matchgates on domain size at most 4. Inf. Comput. 239: 149-169 (2014) - [j74]Jin-Yi Cai, Pinyan Lu, Mingji Xia:
The complexity of complex weighted Boolean #CSP. J. Comput. Syst. Sci. 80(1): 217-236 (2014) - [j73]Jin-Yi Cai, Aaron Gorenstein:
Matchgates Revisited. Theory Comput. 10: 167-197 (2014) - [c103]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: 582-595 - [c102]Jin-Yi Cai, Heng Guo, Tyson Williams:
The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. FOCS 2014: 601-610 - [c101]Jin-Yi Cai, Heng Guo, Tyson Williams:
Holographic Algorithms Beyond Matchgates. ICALP (1) 2014: 271-282 - [i37]Jin-Yi Cai, Heng Guo, Tyson Williams:
The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. CoRR abs/1404.4020 (2014) - 2013
- [j72]Jin-Yi Cai, Xi Chen, Pinyan Lu:
Graph Homomorphisms with Complex Values: A Dichotomy Theorem. SIAM J. Comput. 42(3): 924-1029 (2013) - [j71]Jin-Yi Cai, Michael Kowalczyk:
Partition functions on kk-regular graphs with {0, 1}{0, 1}-vertex assignments and real edge functions. Theor. Comput. Sci. 494: 63-74 (2013) - [j70]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): 690-703 (2013) - [c100]Chen Zeng, Jin-Yi Cai, Pinyan Lu, Jeffrey F. Naughton:
On optimal differentially private mechanisms for count-range queries. ICDT 2013: 261-271 - [c99]Jin-Yi Cai:
Complexity Dichotomy for Counting Problems. LATA 2013: 1-11 - [c98]Jin-Yi Cai, Pinyan Lu, Mingji Xia:
Dichotomy for Holant* Problems with Domain Size 3. SODA 2013: 1278-1295 - [c97]Jin-Yi Cai, Heng Guo, Tyson Williams:
A complete dichotomy rises from the capture of vanishing signatures: extended abstract. STOC 2013: 635-644 - [i36]Jin-Yi Cai, Aaron Gorenstein:
Matchgates Revisited. CoRR abs/1303.6729 (2013) - [i35]Jin-Yi Cai, Zhiguo Fu:
A Collapse Theorem for Holographic Algorithms with Matchgates on Domain Size at Most 4. CoRR abs/1305.1409 (2013) - [i34]Jin-Yi Cai, Heng Guo, Tyson Williams:
Holographic Algorithms Beyond Matchgates. CoRR abs/1307.7430 (2013) - [i33]Jin-Yi Cai, Leslie Ann Goldberg, Heng Guo, Mark Jerrum:
Approximating the Partition Function of Two-Spin Systems on Bipartite Graphs. CoRR abs/1311.4451 (2013) - [i32]Jin-Yi Cai, Aaron Gorenstein:
Matchgates Revisited. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j69]Jin-Yi Cai, Sangxia Huang, Pinyan Lu:
From Holant to #CSP and Back: Dichotomy for Holant c Problems. Algorithmica 64(3): 511-533 (2012) - [j68]Jin-Yi Cai, Pinyan Lu, Mingji Xia:
Holographic reduction, interpolation and hardness. Comput. Complex. 21(4): 573-604 (2012) - [j67]Chen Zeng, Jeffrey F. Naughton, Jin-Yi Cai:
On differentially private frequent itemset mining. Proc. VLDB Endow. 6(1): 25-36 (2012) - [j66]Jin-Yi Cai, Michael Kowalczyk:
Spin systems on k-regular graphs with complex edge functions. Theor. Comput. Sci. 461: 2-16 (2012) - [c96]Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu:
Inapproximability after Uniqueness Phase Transition in Two-Spin Systems. COCOA 2012: 336-347 - [c95]Jin-yi Cai, Michael Kowalczyk, Tyson Williams:
Gadgets and anti-gadgets leading to a complexity dichotomy. ITCS 2012: 452-467 - [c94]Jin-Yi Cai, Xi Chen:
Complexity of counting CSP with complex weights. STOC 2012: 909-920 - [c93]Zhiguo Fu, Jin-Yi Cai:
Holographic Algorithms on Domain Size k > 2. TAMC 2012: 346-359 - [i31]Jin-Yi Cai, Heng Guo, Tyson Williams:
A Complete Dichotomy Rises from the Capture of Vanishing Signatures. CoRR abs/1204.6445 (2012) - [i30]Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu:
Inapproximability After Uniqueness Phase Transition in Two-Spin Systems. CoRR abs/1205.2934 (2012) - [i29]Jin-Yi Cai, Pinyan Lu, Mingji Xia:
Dichotomy for Holant* Problems with a Function on Domain Size 3. CoRR abs/1207.2354 (2012) - 2011
- [j65]Jin-yi Cai, Pinyan Lu:
Signature Theory in Holographic Algorithms. Algorithmica 61(4): 779-816 (2011) - [j64]Peng Zhang, Jin-yi Cai, Linqing Tang, Wenbo Zhao:
Approximation and hardness results for label cut and related problems. J. Comb. Optim. 21(2): 192-208 (2011) - [j63]Jin-yi Cai, Vinod Yegneswaran, Chris Alfeld, Paul Barford:
Honeynet games: a game theoretic approach to defending network monitors. J. Comb. Optim. 22(3): 305-324 (2011) - [j62]Jin-yi Cai, Alan L. Selman:
Foreword. J. Comput. Syst. Sci. 77(1): 1-2 (2011) - [j61]Jin-yi Cai, Pinyan Lu:
Holographic algorithms: From art to science. J. Comput. Syst. Sci. 77(1): 41-61 (2011) - [j60]Jin-yi Cai, Pinyan Lu, Mingji Xia:
Computational Complexity of Holant Problems. SIAM J. Comput. 40(4): 1101-1132 (2011) - [j59]Jin-yi Cai, Pinyan Lu, Mingji Xia:
A computational proof of complexity of some restricted counting problems. Theor. Comput. Sci. 412(23): 2468-2485 (2011) - [c92]Jin-yi Cai:
Progress in Complexity of Counting Problems. FAW-AAIM 2011: 1-3 - [c91]Jin-yi Cai, Xi Chen, Pinyan Lu:
Non-negatively Weighted #CSP: An Effective Complexity Dichotomy. CCC 2011: 45-54 - [c90]Jin-yi Cai, Michael Kowalczyk:
Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities. COCOON 2011: 146-157 - [c89]Jin-yi Cai, Pinyan Lu, Mingji Xia:
Dichotomy for Holant* Problems of Boolean Domain. SODA 2011: 1714-1728 - [i28]Jin-yi Cai, Michael Kowalczyk, Tyson Williams:
Gadgets and Anti-gadgets Leading to a Complexity Dichotomy. CoRR abs/1108.3383 (2011) - [i27]Jin-yi Cai, Xi Chen:
Complexity of Counting CSP with Complex Weights. CoRR abs/1111.2384 (2011) - 2010
- [j58]Jin-yi Cai, Xi Chen