Edit Profile (opens in new tab) Cai, Jin-Yi Co-Author Distance Author ID: cai.jin-yi Published as: Cai, Jin-Yi; Cai, Jin-yi; Cai, J.-Y.; Cai, Jinyi; Cai, J. more...less Further Spellings: 蔡进一 Homepage: http://pages.cs.wisc.edu/~jyc/ External Links: MGP · Wikidata · Google Scholar · dblp · GND · IdRef Documents Indexed: 184 Publications since 1986, including 1 Book and 3 Additional arXiv Preprints 6 Contributions as Editor Biographic References: 1 Publication Co-Authors: 82 Co-Authors with 163 Joint Publications 1,992 Co-Co-Authors all top 5 Co-Authors 22 single-authored 36 Lu, Pinyan 13 Xia, Mingji 12 Fu, Zhiguo 12 Hemaspaandra, Lane A. 11 Chen, Xi 10 Guo, Heng 10 Kowalczyk, Michael 10 Williams, Tyson 7 Govorov, Artem 7 Lipton, Richard Jay 6 Chakaravarthy, Venkatesan T. 6 Watanabe, Osamu 4 Bach, Eric 4 Choudhary, Vinay 4 Fan, Austen Z. 4 Nerurkar, Ajay 4 Ogihara, Mitsunori 4 Wechsung, Gerd 3 Cai, Pu 3 Condon, Anne E. 3 Hartmanis, Juris 3 Liu, Tianyu 3 Pavan, Aduri 2 Alfeld, Chris 2 Barford, Paul 2 Charles, Denis Xavier 2 Cooper, Stuart Barry 2 Cusick, Thomas W. 2 Galanis, Andreas 2 Girstmair, Kurt 2 Goldberg, Leslie Ann 2 Gundermann, Thomas 2 Huang, Sangxia 2 Jerrum, Mark R. 2 Li, Dong 2 Maran, Ashwin 2 Meyer, Gabriele E. 2 Naik, Ashish V. 2 Regan, Kenneth W. 2 Selman, Alan Louis 2 Sengupta, Samik 2 Sewelson, Vivian 2 Shao, Shuai 2 Štefankovič, Daniel 2 Tang, Linqing 2 van Melkebeek, Dieter 2 Vigoda, Eric 2 Vyskoč, Jozef 2 Wagner, Klaus W. 2 Wong, Chak-Kuen 2 Yegneswaran, Vinod 2 Zhang, Peng 2 Zhao, Wenbo 1 Ar, Sigal 1 Babai, László 1 Beals, Robert M. 1 Bhatt, Sandeep N. 1 Chari, Suresh 1 Chen, Lily 1 Coleman, Thomas F. 1 Dyer, Martin E. 1 Fürer, Martin 1 Furst, Merrick L. 1 Gorenstein, Aaron 1 Green, Frederic 1 Hirsch, Michael D. 1 Immerman, Neil 1 Ivanyos, Gábor 1 Kabanets, Valentine 1 Kruse, Jacob 1 Li, Angsheng 1 Liu, Zicheng 1 Longpré, Luc 1 Luks, Eugene M. 1 Poon, Chung Keung 1 Szabo, Daniel P. 1 Thierauf, Thomas 1 Threlfall, Robert A. 1 Young, Ben 1 Zalcstein, Yechezkel 1 Zhang, Jialin 1 Zhu, Hong 1 Zhu, Yixin all top 5 Serials 13 SIAM Journal on Computing 13 Theoretical Computer Science 12 Journal of Computer and System Sciences 10 Theory of Computing Systems 9 Information and Computation 6 Information Processing Letters 6 Algorithmica 5 Computational Complexity 4 Journal of Combinatorial Optimization 3 Mathematical Systems Theory 3 International Journal of Foundations of Computer Science 3 Lecture Notes in Computer Science 2 ACM Transactions on Computation Theory 1 Discrete Applied Mathematics 1 Journal of the Association for Computing Machinery 1 SIAM Journal on Algebraic and Discrete Methods 1 Combinatorica 1 Bulletin of the Iranian Mathematical Society 1 Journal of Complexity 1 Random Structures & Algorithms 1 Linear Algebra and its Applications 1 Combinatorics, Probability and Computing 1 Journal of the ACM 1 International Mathematical Journal 1 Communications in Information and Systems 1 DIMACS. Series in Discrete Mathematics and Theoretical Computer Science 1 Theory of Computing 1 Research in the Mathematical Sciences all top 5 Fields 166 Computer science (68-XX) 35 Combinatorics (05-XX) 15 Mathematical logic and foundations (03-XX) 9 Information and communication theory, circuits (94-XX) 7 Operations research, mathematical programming (90-XX) 6 General and overarching topics; collections (00-XX) 6 Number theory (11-XX) 5 Statistical mechanics, structure of matter (82-XX) 5 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 4 Linear and multilinear algebra; matrix theory (15-XX) 3 Group theory and generalizations (20-XX) 3 Numerical analysis (65-XX) 2 Order, lattices, ordered algebraic structures (06-XX) 2 Field theory and polynomials (12-XX) 1 Associative rings and algebras (16-XX) 1 Functional analysis (46-XX) 1 Manifolds and cell complexes (57-XX) 1 Probability theory and stochastic processes (60-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 141 Publications have been cited 1,367 times in 729 Documents Cited by ▼ Year ▼ An optimal lower bound on the number of variables for graph identification. Zbl 0785.68043 Cai, Jin-Yi; Fürer, Martin; Immerman, Neil 104 1992 The Boolean hierarchy. I: Structural properties. Zbl 0676.68011 Cai, Jin-yi; Gundermann, Thomas; Hartmanis, Juris; Hemachandra, Lane A.; Sewelson, Vivian; Wagner, Klaus; Wechsung, Gerd 61 1988 Circuit minimization problem. Zbl 1296.94182 Kabanets, Valentine; Cai, Jin-Yi 44 2000 Holant problems and counting CSP. Zbl 1304.68067 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 37 2009 The cyclic coloring problem and estimation of sparse Hessian matrices. Zbl 0613.65066 Coleman, Thomas F.; Cai, Jin-Yi 34 1986 The Boolean hierarchy. II: Applications. Zbl 0676.68012 Cai, Jin-Yi; Gundermann, Thomas; Hartmanis, Juris; Hemachandra, Lane A.; Sewelson, Vivian; Wagner, Klaus; Wechsung, Gerd 33 1989 On the power of parity polynomial time. Zbl 0718.68038 Cai, Jin-yi; Hemachandra, Lane A. 33 1990 Holographic algorithms: from art to science. Zbl 1214.68170 Cai, Jin-Yi; Lu, Pinyan 32 2011 The complexity of complex weighted Boolean #CSP. Zbl 1311.68074 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 29 2014 Computational complexity of Holant problems. Zbl 1234.68130 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 27 2011 Graph homomorphisms with complex values: a dichotomy theorem. Zbl 1275.68073 Cai, Jin-Yi; Chen, Xi; Lu, Pinyan 26 2013 On the correlation of symmetric functions. Zbl 0858.94033 Cai, Jin-Yi; Green, F.; Thierauf, T. 24 1996 Holographic algorithms with matchgates capture precisely tractable planar #CSP. Zbl 1370.68117 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 24 2017 A complete dichotomy rises from the capture of vanishing signatures. Zbl 1350.68133 Cai, Jin-Yi; Guo, Heng; Williams, Tyson 23 2016 With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy. Zbl 0668.68052 Cai, Jin-Yi 21 1989 Enumerative counting is hard. Zbl 0679.68072 Cai, Jin-Yi; Hemachandra, Lane A. 21 1989 Multiplicative equations over commuting matrices. Zbl 0865.15012 Babai, László; Beals, Robert; Cai, Jin-yi; Ivanyos, Gábor; Luks, Eugene M. 21 1996 On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line. Zbl 0824.68054 Cai, Jin-Yi; Hartmanis, Juris 21 1994 Complexity of counting CSP with complex weights. Zbl 1426.68114 Cai, Jin-Yi; Chen, Xi 20 2017 Holographic algorithms: from art to science. Zbl 1232.68055 Cai, Jin-Yi; Lu, Pinyan 20 2007 Complexity dichotomies for counting problems. Volume 1. Boolean domain. Zbl 06821418 Cai, Jin-Yi; Chen, Xi 20 2017 From Holant to #CSP and back: dichotomy for Holant\(^{c}\) problems. Zbl 1255.68079 Cai, Jin-Yi; Huang, Sangxia; Lu, Pinyan 19 2012 Complexity of counting CSP with complex weights. Zbl 1286.68182 Cai, Jin-Yi; Chen, Xi 19 2012 Some results on matchgates and holographic algorithms. Zbl 1223.68120 Cai, Jin-Yi; Choudhary, Vinay 18 2006 A complete dichotomy rises from the capture of vanishing signatures (extended abstract). Zbl 1293.68162 Cai, Jin-Yi; Guo, Heng; Williams, Tyson 18 2013 Dichotomy for Holant* problems of Boolean domain. Zbl 1373.68256 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 16 2011 Holographic algorithms by Fibonacci gates. Zbl 1257.05004 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 16 2013 Holant problems for regular graphs with complex edge functions. Zbl 1250.68129 Kowalczyk, Michael; Cai, Jin-Yi 15 2010 Competing provers yield improved Karp-Lipton collapse results. Zbl 1066.68050 Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori 15 2005 \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Zbl 1338.68086 Cai, Jin-Yi; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Jerrum, Mark; Štefankovič, Daniel; Vigoda, Eric 15 2016 Nonnegative weighted #CSP: an effective complexity dichotomy. Zbl 1356.68094 Cai, Jin-Yi; Chen, Xi; Lu, Pinyan 14 2016 Approximation and hardness results for label cut and related problems. Zbl 1211.90201 Zhang, Peng; Cai, Jin-Yi; Tang, Lin-Qing; Zhao, Wen-Bo 13 2011 \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\). Zbl 1133.68020 Cai, Jin-Yi 13 2007 PSPACE survives constant-width bottlenecks. Zbl 0742.68022 Cai, Jin-Yi; Furst, Merrick 13 1991 Matchgates revisited. Zbl 1342.68156 Cai, Jin-Yi; Gorenstein, Aaron 13 2014 Graph homomorphisms with complex values: a dichotomy theorem (extended abstract). Zbl 1288.05178 Cai, Jin-Yi; Chen, Xi; Lu, Pinyan 13 2010 Valiant’s holant theorem and matchgate tensors. Zbl 1124.68113 Cai, Jin-Yi; Choudhary, Vinay 12 2007 Dichotomy for real Holant\(^{\mathrm c}\) problems. Zbl 1403.68076 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 12 2018 Pseudorandom generators, measure theory, and natural proofs. Zbl 0938.68822 Regan, Kenneth W.; Sivakumar, D.; Cai, Jin-yi 12 1995 A note on enumerative counting. Zbl 0733.68030 Cai, Jinyi; Hemachandra, Lane A. 11 1991 Spin systems on \(k\)-regular graphs with complex edge functions. Zbl 1252.68149 Cai, Jin-Yi; Kowalczyk, Michael 11 2012 On symmetric signatures in holographic algorithms. Zbl 1186.68540 Cai, Jin-Yi; Lu, Pinyan 10 2007 On the theory of matchgate computations. Zbl 1178.68254 Cai, Jin-Yi; Choudhary, Vinay; Lu, Pinyan 10 2009 Holographic algorithms: The power of dimensionality resolved. Zbl 1171.68841 Cai, Jin-Yi; Lu, Pinyan 9 2007 Dichotomy for Holant* problems with a function on domain size 3. Zbl 1421.68065 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 9 2013 Holant problems for 3-regular graphs with complex edge functions. Zbl 1350.68151 Kowalczyk, Michael; Cai, Jin-Yi 9 2016 Quadratic lower bound for permanent vs. determinant in any characteristic. Zbl 1204.68100 Cai, Jin-Yi; Chen, Xi; Li, Dong 8 2010 A computational proof of complexity of some restricted counting problems. Zbl 1216.68122 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 8 2011 On a scheduling problem of time deteriorating jobs. Zbl 0910.68019 Cai, Jin-Yi; Cai, Pu; Zhu, Yixin 8 1998 A relation of primal–dual lattices and the complexity of shortest lattice vector problem. Zbl 0926.11047 Cai, Jin-Yi 8 1998 On the hardness of permanent. Zbl 0931.65048 Cai, Jin-Yi; Pavan, A.; Sivakumar, D. 8 1999 Basis collapse in holographic algorithms. Zbl 1149.68036 Cai, Jin-Yi; Lu, Pinyan 8 2008 Graph minimal uncolorability is \(D^ P\)-complete. Zbl 0626.05017 Cai, Jin-Yi; Meyer, Gabriele E. 7 1987 Valiant’s holant theorem and matchgate tensors. Zbl 1178.68660 Cai, Jin-Yi; Choudhary, Vinay 7 2006 Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions. Zbl 0947.68065 Cai, Jin-Yi; Nerurkar, Ajay 7 1999 Computing Jordan normal forms exactly for commuting matrices in polynomial time. Zbl 0830.68061 Cai, Jin-Yi 7 1994 A note on the determinant and permanent problem. Zbl 0687.68021 Cai, Jin-yi 7 1990 Signature theory in holographic algorithms. Zbl 1183.68718 Cai, Jin-Yi; Lu, Pinyan 7 2008 PSPACE is provable by two provers in one round. Zbl 0802.68055 Cai, Jin-yi; Condon, Anne; Lipton, Richard J. 7 1994 Holographic algorithm with matchgates is universal for planar #CSP over Boolean domain. Zbl 1369.68233 Cai, Jin-Yi; Fu, Zhiguo 7 2017 Gadgets and anti-gadgets leading to a complexity dichotomy. Zbl 1347.68178 Cai, Jin-Yi; Kowalczyk, Michael; Williams, Tyson 7 2012 On the power of parity polynomial time. Zbl 1492.68054 Cai, Jin-yi; Hemachandra, Lane A. 7 1989 Holographic reduction, interpolation and hardness. Zbl 1282.68120 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 7 2012 On symmetric signatures in holographic algorithms. Zbl 1204.68256 Cai, Jin-Yi; Lu, Pinyan 6 2010 Approximating the SVP to within a factor \((1+\frac{1}{\text{dim}^\varepsilon})\) is NP-hard under randomized reductions. Zbl 0935.68035 Cai, Jin-Yi; Nerurkar, Ajay 6 1998 On zero error algorithms having oracle access to one query. Zbl 1130.90068 Cai, Jin-Yi; Chakaravarthy, Venkatesan T. 6 2006 A quadratic lower bound for the permanent and determinant problem over any characteristic \(\neq 2\). Zbl 1231.68288 Cai, Jin-Yi; Chen, Xi; Li, Dong 6 2008 Holographic algorithms: the power of dimensionality resolved. Zbl 1172.68058 Cai, Jin-Yi; Lu, Pinyan 6 2009 On games of incomplete information. Zbl 0757.90090 Cai, Jin-yi; Condon, Anne; Lipton, Richard J. 6 1992 On the existence of hard sparse sets under weak reductions. Zbl 1379.68138 Cai, Jin-Yi; Naik, Ashish V.; Sivakumar, D. 6 1996 Holographic algorithms with unsymmetric signatures. Zbl 1192.68474 Cai, Jin-Yi; Lu, Pinyan 6 2008 From Holant to #CSP and back: dichotomy for Holant\(^{c }\) problems. Zbl 1310.68101 Cai, Jin-Yi; Huang, Sangxia; Lu, Pinyan 6 2010 FKT is not universal – a planar holant dichotomy for symmetric constraints. Zbl 07473209 Cai, Jin-Yi; Fu, Zhiguo; Guo, Heng; Williams, Tyson 6 2022 Probability one separation of the Boolean hierarchy. Zbl 0634.68028 Cai, Jin-yi 5 1987 Signature theory in holographic algorithms. Zbl 1238.68184 Cai, Jin-Yi; Lu, Pinyan 5 2011 A computational proof of complexity of some restricted counting problems. Zbl 1241.68068 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 5 2009 The resolution of a Hartmanis conjecture. Zbl 0938.68666 Cai, Jin-yi; Sivakumar, D. 5 1995 A new transference theorem in the geometry of numbers and new bounds for Ajtai’s connection factor. Zbl 1116.11050 Cai, Jin-Yi 5 2003 Sparse sets versus complexity classes. Zbl 0880.68038 Cai, Jin-Yi; Ogihara, Mitsunori 5 1997 Perfect matchings, rank of connection tensors and graph homomorphisms. Zbl 1434.05068 Cai, Jin-Yi; Govorov, Artem 5 2019 Approximability of the six-vertex model. Zbl 1432.68191 Cai, Jin-Yi; Liu, Tianyu; Lu, Pinyan 5 2019 The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems. Zbl 1344.05060 Cai, Jin-Yi; Guo, Heng; Williams, Tyson 5 2016 A dichotomy for \(k\)-regular graphs with \(\{0, 1\}\)-vertex assignments and real edge functions. Zbl 1284.68276 Cai, Jin-Yi; Kowalczyk, Michael 4 2010 The complexity of the \(A\) \(B\) \(C\) problem. Zbl 0967.20029 Cai, Jin-yi; Lipton, Richard J.; Zalcstein, Yechezkel 4 2000 Time-space tradeoff in derandomizing probabilistic logspace. Zbl 1101.68109 Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; van Melkebeek, Dieter 4 2006 Lower bounds for constant-depth circuits in the presence of help bits. Zbl 0704.68040 Cai, Jin-yi 4 1990 Taking random walks to grow trees in hypercubes. Zbl 0785.68005 Bhatt, Sandeep; Cai, Jin-Yi 4 1993 Promises and fault-tolerant database access. Zbl 0794.68059 Cai, Jin-yi; Hemachandra, Lane A.; Vyskoč, Jozef 4 1993 Fine separation of average time complexity classes. Zbl 1379.68139 Cai, Jin-yi; Selman, Alan L. 4 1996 Competing provers yield improved Karp-Lipton collapse results. Zbl 1035.68053 Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori 4 2003 On tractable exponential sums. Zbl 1288.68104 Cai, Jin-Yi; Chen, Xi; Lipton, Richard; Lu, Pinyan 4 2010 Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions. Zbl 1300.05246 Cai, Jin-Yi; Kowalczyk, Michael 4 2013 Spin systems on graphs with complex edge functions and specified degree regularities. Zbl 1353.68110 Cai, Jin-Yi; Kowalczyk, Michael 3 2011 Robust reductions. Zbl 0946.68053 Cai, J.-Y.; Hemaspaandra, L. A.; Wechsung, G. 3 1999 Approximation and hardness results for label cut and related problems. Zbl 1241.90129 Zhang, Peng; Cai, Jin-Yi; Tang, Linqing; Zhao, Wenbo 3 2009 Complexity classification of the six-vertex model. Zbl 1388.68107 Cai, Jin-Yi; Fu, Zhiguo; Xia, Mingji 3 2018 Sparse hard sets for P: Resolution of a conjecture of Hartmanis. Zbl 0936.68046 Cai, Jin-Yi; Sivakumar, D. 3 1999 Playing games of incomplete information. Zbl 0786.90094 Cai, Jin-yi; Condon, Anne; Lipton, Richard J. 3 1990 The bounded membership problem of the monoid \(\mathrm{SL}_2(N)\). Zbl 0860.68045 Cai, J.; Liu, Zicheng 3 1996 Holographic algorithms beyond matchgates. Zbl 1408.68143 Cai, Jin-Yi; Guo, Heng; Williams, Tyson 3 2014 Counting cycles on planar graphs in subexponential time. Zbl 07724751 Cai, Jin-Yi; Maran, Ashwin 1 2023 FKT is not universal – a planar holant dichotomy for symmetric constraints. Zbl 07473209 Cai, Jin-Yi; Fu, Zhiguo; Guo, Heng; Williams, Tyson 6 2022 Holographic algorithm with matchgates is universal for planar #CSP over Boolean domain. Zbl 07516618 Cai, Jin-Yi; Fu, Zhiguo 3 2022 Dichotomy result on 3-regular bipartite non-negative functions. Zbl 07493526 Fan, Austen Z.; Cai, Jin-Yi 3 2021 On a theorem of Lovász that \((\cdot, H)\) determines the isomorphism type of \(H\). Zbl 1506.05142 Cai, Jin-yi; Govorov, Artem 1 2021 Dichotomy for Holant\(^\ast\) problems on the Boolean domain. Zbl 1503.68199 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 2 2020 Beyond #CSP: a dichotomy for counting weighted Eulerian orientations with ARS. Zbl 1496.68157 Cai, Jin-Yi; Fu, Zhiguo; Shao, Shuai 1 2020 Approximability of the eight-vertex model. Zbl 07561732 Cai, Jin-Yi; Liu, Tianyu; Lu, Pinyan; Yu, Jing 1 2020 Perfect matchings, rank of connection tensors and graph homomorphisms. Zbl 1434.05068 Cai, Jin-Yi; Govorov, Artem 5 2019 Approximability of the six-vertex model. Zbl 1432.68191 Cai, Jin-Yi; Liu, Tianyu; Lu, Pinyan 5 2019 Gadgets and anti-gadgets leading to a complexity dichotomy. Zbl 1485.68104 Cai, Jin-Yi; Kowalczyk, Michael; Williams, Tyson 3 2019 A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. Zbl 1429.68079 Cai, Jin-Yi; Chen, Xi 1 2019 Dichotomy for real Holant\(^{\mathrm c}\) problems. Zbl 1403.68076 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 12 2018 Complexity classification of the six-vertex model. Zbl 1388.68107 Cai, Jin-Yi; Fu, Zhiguo; Xia, Mingji 3 2018 Holographic algorithms beyond matchgates. Zbl 1390.68338 Cai, Jin-Yi; Guo, Heng; Williams, Tyson 2 2018 Clifford gates in the Holant framework. Zbl 1400.68072 Cai, Jin-Yi; Guo, Heng; Williams, Tyson 2 2018 Commuting mappings on the Hochschild extension of an algebra. Zbl 1410.16040 Chen, L.; Cai, J. 1 2018 A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory. Zbl 1462.68078 Cai, Jin-Yi; Fu, Zhiguo; Girstmair, Kurt; Kowalczyk, Michael 1 2018 Holographic algorithms with matchgates capture precisely tractable planar #CSP. Zbl 1370.68117 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 24 2017 Complexity of counting CSP with complex weights. Zbl 1426.68114 Cai, Jin-Yi; Chen, Xi 20 2017 Complexity dichotomies for counting problems. Volume 1. Boolean domain. Zbl 06821418 Cai, Jin-Yi; Chen, Xi 20 2017 Holographic algorithm with matchgates is universal for planar #CSP over Boolean domain. Zbl 1369.68233 Cai, Jin-Yi; Fu, Zhiguo 7 2017 A complete dichotomy rises from the capture of vanishing signatures. Zbl 1350.68133 Cai, Jin-Yi; Guo, Heng; Williams, Tyson 23 2016 \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Zbl 1338.68086 Cai, Jin-Yi; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Jerrum, Mark; Štefankovič, Daniel; Vigoda, Eric 15 2016 Nonnegative weighted #CSP: an effective complexity dichotomy. Zbl 1356.68094 Cai, Jin-Yi; Chen, Xi; Lu, Pinyan 14 2016 Holant problems for 3-regular graphs with complex edge functions. Zbl 1350.68151 Kowalczyk, Michael; Cai, Jin-Yi 9 2016 The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems. Zbl 1344.05060 Cai, Jin-Yi; Guo, Heng; Williams, Tyson 5 2016 The complexity of complex weighted Boolean #CSP. Zbl 1311.68074 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 29 2014 Matchgates revisited. Zbl 1342.68156 Cai, Jin-Yi; Gorenstein, Aaron 13 2014 Holographic algorithms beyond matchgates. Zbl 1408.68143 Cai, Jin-Yi; Guo, Heng; Williams, Tyson 3 2014 A collapse theorem for holographic algorithms with matchgates on domain size at most 4. Zbl 1309.68085 Cai, Jin-Yi; Fu, Zhiguo 3 2014 Graph homomorphisms with complex values: a dichotomy theorem. Zbl 1275.68073 Cai, Jin-Yi; Chen, Xi; Lu, Pinyan 26 2013 A complete dichotomy rises from the capture of vanishing signatures (extended abstract). Zbl 1293.68162 Cai, Jin-Yi; Guo, Heng; Williams, Tyson 18 2013 Holographic algorithms by Fibonacci gates. Zbl 1257.05004 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 16 2013 Dichotomy for Holant* problems with a function on domain size 3. Zbl 1421.68065 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 9 2013 Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions. Zbl 1300.05246 Cai, Jin-Yi; Kowalczyk, Michael 4 2013 Complexity dichotomy for counting problems. Zbl 1377.68093 Cai, Jin-Yi 1 2013 From Holant to #CSP and back: dichotomy for Holant\(^{c}\) problems. Zbl 1255.68079 Cai, Jin-Yi; Huang, Sangxia; Lu, Pinyan 19 2012 Complexity of counting CSP with complex weights. Zbl 1286.68182 Cai, Jin-Yi; Chen, Xi 19 2012 Spin systems on \(k\)-regular graphs with complex edge functions. Zbl 1252.68149 Cai, Jin-Yi; Kowalczyk, Michael 11 2012 Gadgets and anti-gadgets leading to a complexity dichotomy. Zbl 1347.68178 Cai, Jin-Yi; Kowalczyk, Michael; Williams, Tyson 7 2012 Holographic reduction, interpolation and hardness. Zbl 1282.68120 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 7 2012 Inapproximability after uniqueness phase transition in two-spin systems. Zbl 1358.82018 Cai, Jin-Yi; Chen, Xi; Guo, Heng; Lu, Pinyan 3 2012 Holographic algorithms on domain size \(k > 2\). Zbl 1354.68288 Fu, Zhiguo; Cai, Jin-Yi 1 2012 Holographic algorithms: from art to science. Zbl 1214.68170 Cai, Jin-Yi; Lu, Pinyan 32 2011 Computational complexity of Holant problems. Zbl 1234.68130 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 27 2011 Dichotomy for Holant* problems of Boolean domain. Zbl 1373.68256 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 16 2011 Approximation and hardness results for label cut and related problems. Zbl 1211.90201 Zhang, Peng; Cai, Jin-Yi; Tang, Lin-Qing; Zhao, Wen-Bo 13 2011 A computational proof of complexity of some restricted counting problems. Zbl 1216.68122 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 8 2011 Signature theory in holographic algorithms. Zbl 1238.68184 Cai, Jin-Yi; Lu, Pinyan 5 2011 Spin systems on graphs with complex edge functions and specified degree regularities. Zbl 1353.68110 Cai, Jin-Yi; Kowalczyk, Michael 3 2011 Honeynet games: A game theoretic approach to defending network monitors. Zbl 1229.91090 Cai, Jin-Yi; Yegneswaran, Vinod; Alfeld, Chris; Barford, Paul 1 2011 Holant problems for regular graphs with complex edge functions. Zbl 1250.68129 Kowalczyk, Michael; Cai, Jin-Yi 15 2010 Graph homomorphisms with complex values: a dichotomy theorem (extended abstract). Zbl 1288.05178 Cai, Jin-Yi; Chen, Xi; Lu, Pinyan 13 2010 Quadratic lower bound for permanent vs. determinant in any characteristic. Zbl 1204.68100 Cai, Jin-Yi; Chen, Xi; Li, Dong 8 2010 On symmetric signatures in holographic algorithms. Zbl 1204.68256 Cai, Jin-Yi; Lu, Pinyan 6 2010 From Holant to #CSP and back: dichotomy for Holant\(^{c }\) problems. Zbl 1310.68101 Cai, Jin-Yi; Huang, Sangxia; Lu, Pinyan 6 2010 A dichotomy for \(k\)-regular graphs with \(\{0, 1\}\)-vertex assignments and real edge functions. Zbl 1284.68276 Cai, Jin-Yi; Kowalczyk, Michael 4 2010 On tractable exponential sums. Zbl 1288.68104 Cai, Jin-Yi; Chen, Xi; Lipton, Richard; Lu, Pinyan 4 2010 On blockwise symmetric signatures for matchgates. Zbl 1183.68297 Cai, Jin-Yi; Lu, Pinyan 1 2010 Holant problems and counting CSP. Zbl 1304.68067 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 37 2009 On the theory of matchgate computations. Zbl 1178.68254 Cai, Jin-Yi; Choudhary, Vinay; Lu, Pinyan 10 2009 Holographic algorithms: the power of dimensionality resolved. Zbl 1172.68058 Cai, Jin-Yi; Lu, Pinyan 6 2009 A computational proof of complexity of some restricted counting problems. Zbl 1241.68068 Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji 5 2009 Approximation and hardness results for label cut and related problems. Zbl 1241.90129 Zhang, Peng; Cai, Jin-Yi; Tang, Linqing; Zhao, Wenbo 3 2009 An attacker-defender game for honeynets. Zbl 1248.68072 Cai, Jin-Yi; Yegneswaran, Vinod; Alfeld, Chris; Barford, Paul 2 2009 Basis collapse in holographic algorithms. Zbl 1149.68036 Cai, Jin-Yi; Lu, Pinyan 8 2008 Signature theory in holographic algorithms. Zbl 1183.68718 Cai, Jin-Yi; Lu, Pinyan 7 2008 A quadratic lower bound for the permanent and determinant problem over any characteristic \(\neq 2\). Zbl 1231.68288 Cai, Jin-Yi; Chen, Xi; Li, Dong 6 2008 Holographic algorithms with unsymmetric signatures. Zbl 1192.68474 Cai, Jin-Yi; Lu, Pinyan 6 2008 Holographic algorithms: from art to science. Zbl 1232.68055 Cai, Jin-Yi; Lu, Pinyan 20 2007 \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\). Zbl 1133.68020 Cai, Jin-Yi 13 2007 Valiant’s holant theorem and matchgate tensors. Zbl 1124.68113 Cai, Jin-Yi; Choudhary, Vinay 12 2007 On symmetric signatures in holographic algorithms. Zbl 1186.68540 Cai, Jin-Yi; Lu, Pinyan 10 2007 Holographic algorithms: The power of dimensionality resolved. Zbl 1171.68841 Cai, Jin-Yi; Lu, Pinyan 9 2007 On block-wise symmetric signatures for matchgates. Zbl 1135.68436 Cai, Jin-Yi; Lu, Pinyan 1 2007 Holographic algorithms. Zbl 1167.68058 Cai, Jin-Yi 1 2007 Some results on matchgates and holographic algorithms. Zbl 1223.68120 Cai, Jin-Yi; Choudhary, Vinay 18 2006 Valiant’s holant theorem and matchgate tensors. Zbl 1178.68660 Cai, Jin-Yi; Choudhary, Vinay 7 2006 On zero error algorithms having oracle access to one query. Zbl 1130.90068 Cai, Jin-Yi; Chakaravarthy, Venkatesan T. 6 2006 Time-space tradeoff in derandomizing probabilistic logspace. Zbl 1101.68109 Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; van Melkebeek, Dieter 4 2006 Competing provers yield improved Karp-Lipton collapse results. Zbl 1066.68050 Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori 15 2005 A note on zero error algorithms having oracle access to one NP query. Zbl 1128.68358 Cai, Jin-Yi; Chakaravarthy, Venkatesan T. 1 2005 On proving circuit lower bounds against the polynomial-time hierarchy. Zbl 1105.68041 Cai, Jin-Yi; Watanabe, Osamu 1 2004 A new transference theorem in the geometry of numbers and new bounds for Ajtai’s connection factor. Zbl 1116.11050 Cai, Jin-Yi 5 2003 Competing provers yield improved Karp-Lipton collapse results. Zbl 1035.68053 Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori 4 2003 On testing for zero polynomials by a set of points with bounded precision. Zbl 1045.68166 Cai, Jin-Yi; Bach, Eric 1 2003 On testing for zero polynomials by a set of points with bounded precision. Zbl 0991.68156 Cai, Jin-Yi; Bach, Eric 3 2001 Circuit minimization problem. Zbl 1296.94182 Kabanets, Valentine; Cai, Jin-Yi 44 2000 The complexity of the \(A\) \(B\) \(C\) problem. Zbl 0967.20029 Cai, Jin-yi; Lipton, Richard J.; Zalcstein, Yechezkel 4 2000 Resolution of Hartmanis’ conjecture for NL-hard sparse sets. Zbl 0945.68102 Cai, J.-Y.; Sivakumar, D. 2 2000 A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. Zbl 1063.11504 Cai, Jin-Yi; Nerurkar, Ajay 1 2000 On the hardness of permanent. Zbl 0931.65048 Cai, Jin-Yi; Pavan, A.; Sivakumar, D. 8 1999 Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions. Zbl 0947.68065 Cai, Jin-Yi; Nerurkar, Ajay 7 1999 Robust reductions. Zbl 0946.68053 Cai, J.-Y.; Hemaspaandra, L. A.; Wechsung, G. 3 1999 Sparse hard sets for P: Resolution of a conjecture of Hartmanis. Zbl 0936.68046 Cai, Jin-Yi; Sivakumar, D. 3 1999 Fine separation of average-time complexity classes. Zbl 0939.68041 Cai, Jin-Yi; Selman, Alan L. 2 1999 Hardness and hierarchy theorems for probabilistic quasi-polynomial time. Zbl 1346.68095 Cai, Jin-Yi; Nerurkar, Ajay; Sivakumar, D. 2 1999 A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes. Zbl 1338.68081 Cai, Jin-Yi 1 1999 On a scheduling problem of time deteriorating jobs. Zbl 0910.68019 Cai, Jin-Yi; Cai, Pu; Zhu, Yixin 8 1998 ...and 41 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 912 Authors 64 Cai, Jin-Yi 39 Hemaspaandra, Lane A. 22 Lu, Pinyan 18 Goldberg, Leslie Ann 17 Allender, Eric W. 15 Köbler, Johannes 15 Verbitsky, Oleg 13 Beigel, Richard 13 Grohe, Martin 12 Fu, Zhiguo 12 Guo, Heng 12 Medina, Luis A. 12 Rothe, Jörg-Matthias 11 Hemaspaandra, Edith 10 Dawar, Anuj 9 Lutz, Jack H. 9 Ogihara, Mitsunori 9 Wagner, Klaus W. 8 Galanis, Andreas 8 Jerrum, Mark R. 8 Mayordomo, Elvira 8 Ponomarenko, Ilya Nikolaevich 8 Regts, Guus 8 Richerby, David M. 8 Xia, Mingji 7 Castro, Francis Noel 7 Gasarch, William Ian 7 Grädel, Erich 7 Hempel, Harald 7 Hirahara, Shuichi 7 van Melkebeek, Dieter 7 Watanabe, Osamu 6 Arvind, Vikraman 6 Bulatov, Andrei A. 6 Chang, Richard 6 Curticapean, Radu 6 Dyer, Martin E. 6 Fortnow, Lance J. 6 Fuhlbrück, Frank 6 Green, Frederic 6 Kabanets, Valentine 6 Kowalczyk, Michael 6 Neuen, Daniel 6 Pavan, Aduri 6 Semukhin, Pavel 6 Torán, Jacobo 6 Williams, Tyson 5 Bell, Paul C. 5 Book, Ronald Vernon 5 Buhrman, Harry 5 Hitchcock, John M. 5 Kiefer, Sandra 5 Ogiwara, Mitsunori 5 Potapov, Igor 5 Roth, Marc 5 Selman, Alan Louis 5 Staiger, Ludwig 5 Štefankovič, Daniel 5 Wechsung, Gerd 5 Yamakami, Tomoyuki 5 Zhang, Peng 4 Braga, Mónica 4 Cygan, Marek 4 Dell, Holger 4 Fan, Austen Z. 4 Glaßer, Christian 4 Göbel, Andreas-Nikolas 4 Hartmanis, Juris 4 Hou, Jianfeng 4 Ilango, Rahul 4 Impagliazzo, Russell 4 Kumar, Mrinal 4 Li, Keqin 4 Lohrey, Markus 4 Marenco, Javier L. 4 Otto, Martin 4 Pakusa, Wied 4 Pikhurko, Oleg 4 Pilipczuk, Marcin L. 4 Pilipczuk, Michał 4 Santhanam, Rahul 4 Sepúlveda, L. Brehsner 4 Stephan, Frank 4 Turner, Jacob M. 4 Vigoda, Eric 4 Vinodchandran, N. Variyam 4 Zetzsche, Georg 3 Backens, Miriam 3 Barvinok, Alexander I. 3 Baumeister, Dorothea 3 Berkholz, Christoph 3 Beyersdorff, Olaf 3 Chakaravarthy, Venkatesan T. 3 Chen, Xi 3 Evdokimov, Sergeĭ Alekseevich 3 Frei, Fabian 3 Fu, Bin 3 Goldreich, Oded 3 Govorov, Artem 3 Grochow, Joshua A. ...and 812 more Authors all top 5 Cited in 122 Serials 89 Theoretical Computer Science 64 Journal of Computer and System Sciences 44 Information and Computation 32 Information Processing Letters 31 Computational Complexity 30 Theory of Computing Systems 24 SIAM Journal on Computing 18 Discrete Applied Mathematics 13 The Journal of Symbolic Logic 13 Algorithmica 11 Mathematical Systems Theory 9 Annals of Pure and Applied Logic 9 Journal of Combinatorial Optimization 6 SIAM Journal on Discrete Mathematics 6 Linear Algebra and its Applications 6 The Bulletin of Symbolic Logic 5 Discrete Mathematics 5 Graphs and Combinatorics 5 Journal of Symbolic Computation 4 Communications in Mathematical Physics 4 Journal of Combinatorial Theory. Series A 4 Journal of Combinatorial Theory. Series B 4 European Journal of Combinatorics 4 International Journal of Foundations of Computer Science 4 Journal of Scheduling 4 Logical Methods in Computer Science 4 Theory of Computing 3 Advances in Mathematics 3 Journal of Number Theory 3 Journal of Pure and Applied Algebra 3 Combinatorica 3 International Journal of Algebra and Computation 3 RAIRO. Informatique Théorique et Applications 3 Mathematical Programming. Series A. Series B 3 Journal of Algebraic Combinatorics 3 Combinatorics, Probability and Computing 3 The Electronic Journal of Combinatorics 3 Optimization Methods & Software 3 Foundations of Computational Mathematics 3 ACM Transactions on Computational Logic 3 Science China. Mathematics 2 Artificial Intelligence 2 Journal of Statistical Physics 2 Applied Mathematics and Computation 2 Journal of Graph Theory 2 The Annals of Applied Probability 2 Applicable Algebra in Engineering, Communication and Computing 2 Mathematical Logic Quarterly (MLQ) 2 Annals of Mathematics and Artificial Intelligence 2 Journal of Graph Algorithms and Applications 2 Journal of Machine Learning Research (JMLR) 2 Journal of Discrete Algorithms 2 Forum of Mathematics, Sigma 2 ACM Transactions on Computation Theory 2 Annales de l’Institut Henri Poincaré D. Combinatorics, Physics and their Interactions 2 Research in the Mathematical Sciences 1 International Journal of Systems Science 1 Linear and Multilinear Algebra 1 Rocky Mountain Journal of Mathematics 1 BIT 1 Glasgow Mathematical Journal 1 Journal of Algebra 1 Journal of Functional Analysis 1 Journal of Optimization Theory and Applications 1 Journal of Philosophical Logic 1 Monatshefte für Mathematik 1 Proceedings of the American Mathematical Society 1 Proceedings of the Japan Academy. Series A 1 Rendiconti dell’Istituto di Matematica dell’Università di Trieste 1 Studia Logica 1 Transactions of the American Mathematical Society 1 Advances in Applied Mathematics 1 Mathematical Social Sciences 1 Operations Research Letters 1 Probability Theory and Related Fields 1 Journal of Complexity 1 Discrete & Computational Geometry 1 Journal of the American Mathematical Society 1 Journal of Parallel and Distributed Computing 1 Annals of Operations Research 1 Random Structures & Algorithms 1 Neural Computation 1 International Journal of Computational Geometry & Applications 1 Differential Geometry and its Applications 1 The Journal of Geometric Analysis 1 European Journal of Operational Research 1 International Journal of Computer Mathematics 1 Distributed Computing 1 Archive for Mathematical Logic 1 The Australasian Journal of Combinatorics 1 New Zealand Journal of Mathematics 1 Journal of Mathematical Sciences (New York) 1 St. Petersburg Mathematical Journal 1 Finite Fields and their Applications 1 Complexity 1 Journal of Heuristics 1 Annals of Combinatorics 1 Discrete Mathematics and Theoretical Computer Science. DMTCS 1 Interdisciplinary Information Sciences (IIS) 1 LMS Journal of Computation and Mathematics ...and 22 more Serials all top 5 Cited in 33 Fields 573 Computer science (68-XX) 180 Combinatorics (05-XX) 113 Mathematical logic and foundations (03-XX) 44 Information and communication theory, circuits (94-XX) 40 Operations research, mathematical programming (90-XX) 34 Number theory (11-XX) 25 Group theory and generalizations (20-XX) 22 Linear and multilinear algebra; matrix theory (15-XX) 21 Statistical mechanics, structure of matter (82-XX) 18 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 14 Probability theory and stochastic processes (60-XX) 11 Numerical analysis (65-XX) 10 Measure and integration (28-XX) 9 Order, lattices, ordered algebraic structures (06-XX) 9 Quantum theory (81-XX) 8 Commutative algebra (13-XX) 6 Dynamical systems and ergodic theory (37-XX) 6 Convex and discrete geometry (52-XX) 5 General algebraic systems (08-XX) 5 Field theory and polynomials (12-XX) 5 Algebraic geometry (14-XX) 5 Statistics (62-XX) 3 Associative rings and algebras (16-XX) 3 Category theory; homological algebra (18-XX) 2 Harmonic analysis on Euclidean spaces (42-XX) 2 Functional analysis (46-XX) 1 General and overarching topics; collections (00-XX) 1 Nonassociative rings and algebras (17-XX) 1 Abstract harmonic analysis (43-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Manifolds and cell complexes (57-XX) 1 Biology and other natural sciences (92-XX) 1 Systems theory; control (93-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.