×
Author ID: cai.jin-yi Recent zbMATH articles by "Cai, Jin-Yi"
Published as: Cai, Jin-Yi; Cai, Jin-yi; Cai, J.-Y.; Cai, Jinyi; Cai, J.
Further Spellings: 蔡进一
Homepage: http://pages.cs.wisc.edu/~jyc/
External Links: MGP · Wikidata · Google Scholar · dblp · GND · IdRef
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

Publications by Year

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 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

Citations by Year

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.