×

zbMATH — the first resource for mathematics

Cai, Jin-Yi

Compute Distance To:
Author ID: cai.jin-yi Recent zbMATH articles by "Cai, Jin-Yi"
Published as: Cai, J.; Cai, J.-Y.; Cai, Jin-Yi; Cai, Jin-yi; Cai, Jinyi
Homepage: http://pages.cs.wisc.edu/~jyc/
External Links: MGP · Wikidata · dblp · GND
Documents Indexed: 164 Publications since 1986, including 7 Books
Biographic References: 1 Publication

Publications by Year

Citations contained in zbMATH

124 Publications have been cited 940 times in 532 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
71
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
52
1988
On the power of parity polynomial time. Zbl 0718.68038
Cai, Jin-yi; Hemachandra, Lane A.
34
1990
The cyclic coloring problem and estimation of sparse Hessian matrices. Zbl 0613.65066
Coleman, Thomas F.; Cai, Jin-Yi
30
1986
Holant problems and counting CSP. Zbl 1304.68067
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
28
2009
The Boolean hierarchy. II: Applications. Zbl 0676.68012
Cai, Jin-Yi; Gundermann, Thomas; Hartmanis, Juris; Hemachandra, Lane A.; Sewelson, Vivian; Wagner, Klaus; Wechsung, Gerd
24
1989
Circuit minimization problem. Zbl 1296.94182
Kabanets, Valentine; Cai, Jin-Yi
21
2000
Holographic algorithms: from art to science. Zbl 1214.68170
Cai, Jin-Yi; Lu, Pinyan
20
2011
Enumerative counting is hard. Zbl 0679.68072
Cai, Jin-Yi; Hemachandra, Lane A.
19
1989
Holographic algorithms with matchgates capture precisely tractable planar #CSP. Zbl 1370.68117
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
18
2017
Complexity of counting CSP with complex weights. Zbl 1286.68182
Cai, Jin-Yi; Chen, Xi
18
2012
Computational complexity of Holant problems. Zbl 1234.68130
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
18
2011
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy. Zbl 0668.68052
Cai, Jin-Yi
18
1989
A complete dichotomy rises from the capture of vanishing signatures (extended abstract). Zbl 1293.68162
Cai, Jin-Yi; Guo, Heng; Williams, Tyson
17
2013
On the correlation of symmetric functions. Zbl 0858.94033
Cai, Jin-Yi; Green, F.; Thierauf, T.
17
1996
On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line. Zbl 0824.68054
Cai, Jin-Yi; Hartmanis, Juris
17
1994
Holographic algorithms: from art to science. Zbl 1232.68055
Cai, Jin-Yi; Lu, Pinyan
16
2007
Graph homomorphisms with complex values: a dichotomy theorem. Zbl 1275.68073
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan
15
2013
Some results on matchgates and holographic algorithms. Zbl 1223.68120
Cai, Jin-Yi; Choudhary, Vinay
15
2006
The complexity of complex weighted Boolean #CSP. Zbl 1311.68074
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
14
2014
Graph homomorphisms with complex values: a dichotomy theorem (extended abstract). Zbl 1288.05178
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan
12
2010
Competing provers yield improved Karp-Lipton collapse results. Zbl 1066.68050
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori
12
2005
Multiplicative equations over commuting matrices. Zbl 0865.15012
Babai, László; Beals, Robert; Cai, Jin-yi; Ivanyos, Gábor; Luks, Eugene M.
12
1996
PSPACE survives constant-width bottlenecks. Zbl 0742.68022
Cai, Jin-Yi; Furst, Merrick
12
1991
Holographic algorithms by Fibonacci gates. Zbl 1257.05004
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
11
2013
Dichotomy for Holant* problems of Boolean domain. Zbl 1373.68256
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
11
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
11
2011
Holant problems for regular graphs with complex edge functions. Zbl 1250.68129
Kowalczyk, Michael; Cai, Jin-Yi
11
2010
Pseudorandom generators, measure theory, and natural proofs. Zbl 0938.68822
Regan, Kenneth W.; Sivakumar, D.; Cai, Jin-yi
11
1995
\(\#\)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
10
2016
From Holant to #CSP and back: dichotomy for Holant\(^{c}\) problems. Zbl 1255.68079
Cai, Jin-Yi; Huang, Sangxia; Lu, Pinyan
10
2012
A note on enumerative counting. Zbl 0733.68030
Cai, Jinyi; Hemachandra, Lane A.
10
1991
A complete dichotomy rises from the capture of vanishing signatures. Zbl 1350.68133
Cai, Jin-Yi; Guo, Heng; Williams, Tyson
9
2016
On symmetric signatures in holographic algorithms. Zbl 1186.68540
Cai, Jin-Yi; Lu, Pinyan
9
2007
\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\). Zbl 1133.68020
Cai, Jin-Yi
9
2007
Nonnegative weighted #CSP: an effective complexity dichotomy. Zbl 1356.68094
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan
8
2016
On a scheduling problem of time deteriorating jobs. Zbl 0910.68019
Cai, Jin-Yi; Cai, Pu; Zhu, Yixin
8
1998
Matchgates revisited. Zbl 1342.68156
Cai, Jin-Yi; Gorenstein, Aaron
7
2014
Spin systems on \(k\)-regular graphs with complex edge functions. Zbl 1252.68149
Cai, Jin-Yi; Kowalczyk, Michael
7
2012
A computational proof of complexity of some restricted counting problems. Zbl 1216.68122
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
7
2011
On the theory of matchgate computations. Zbl 1178.68254
Cai, Jin-Yi; Choudhary, Vinay; Lu, Pinyan
7
2009
Signature theory in holographic algorithms. Zbl 1183.68718
Cai, Jin-Yi; Lu, Pinyan
7
2008
Holographic algorithms: The power of dimensionality resolved. Zbl 1171.68841
Cai, Jin-Yi; Lu, Pinyan
7
2007
Valiant’s holant theorem and matchgate tensors. Zbl 1124.68113
Cai, Jin-Yi; Choudhary, Vinay
7
2007
Valiant’s holant theorem and matchgate tensors. Zbl 1178.68660
Cai, Jin-Yi; Choudhary, Vinay
7
2006
A relation of primal–dual lattices and the complexity of shortest lattice vector problem. Zbl 0926.11047
Cai, Jin-Yi
7
1998
PSPACE is provable by two provers in one round. Zbl 0802.68055
Cai, Jin-yi; Condon, Anne; Lipton, Richard J.
7
1994
Gadgets and anti-gadgets leading to a complexity dichotomy. Zbl 1347.68178
Cai, Jin-Yi; Kowalczyk, Michael; Williams, Tyson
6
2012
Holographic reduction, interpolation and hardness. Zbl 1282.68120
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
6
2012
From Holant to #CSP and back: dichotomy for Holant\(^{c }\) problems. Zbl 1310.68101
Cai, Jin-Yi; Huang, Sangxia; Lu, Pinyan
6
2010
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
6
1999
On the existence of hard sparse sets under weak reductions. Zbl 1379.68138
Cai, Jin-Yi; Naik, Ashish V.; Sivakumar, D.
6
1996
Quadratic lower bound for permanent vs. determinant in any characteristic. Zbl 1204.68100
Cai, Jin-Yi; Chen, Xi; Li, Dong
5
2010
A computational proof of complexity of some restricted counting problems. Zbl 1241.68068
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
5
2009
Holographic algorithms with unsymmetric signatures. Zbl 1192.68474
Cai, Jin-Yi; Lu, Pinyan
5
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
5
2008
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
5
1998
Sparse sets versus complexity classes. Zbl 0880.68038
Cai, Jin-Yi; Ogihara, Mitsunori
5
1997
The resolution of a Hartmanis conjecture. Zbl 0938.68666
Cai, Jin-yi; Sivakumar, D.
5
1995
A note on the determinant and permanent problem. Zbl 0687.68021
Cai, Jin-yi
5
1990
Complexity of counting CSP with complex weights. Zbl 1426.68114
Cai, Jin-Yi; Chen, Xi
4
2017
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
4
2016
Signature theory in holographic algorithms. Zbl 1238.68184
Cai, Jin-Yi; Lu, Pinyan
4
2011
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 symmetric signatures in holographic algorithms. Zbl 1204.68256
Cai, Jin-Yi; Lu, Pinyan
4
2010
Holographic algorithms: the power of dimensionality resolved. Zbl 1172.68058
Cai, Jin-Yi; Lu, Pinyan
4
2009
Basis collapse in holographic algorithms. Zbl 1149.68036
Cai, Jin-Yi; Lu, Pinyan
4
2008
Competing provers yield improved Karp-Lipton collapse results. Zbl 1035.68053
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori
4
2003
Promises and fault-tolerant database access. Zbl 0794.68059
Cai, Jin-yi; Hemachandra, Lane A.; Vyskoč, Jozef
4
1993
Taking random walks to grow trees in hypercubes. Zbl 0785.68005
Bhatt, Sandeep; Cai, Jin-Yi
4
1993
On games of incomplete information. Zbl 0757.90090
Cai, Jin-yi; Condon, Anne; Lipton, Richard J.
4
1992
Lower bounds for constant-depth circuits in the presence of help bits. Zbl 0704.68040
Cai, Jin-yi
4
1990
Probability one separation of the Boolean hierarchy. Zbl 0634.68028
Cai, Jin-yi
4
1987
Dichotomy for real Holant\(^{\mathrm c}\) problems. Zbl 1403.68076
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
3
2018
Holographic algorithms beyond matchgates. Zbl 1408.68143
Cai, Jin-Yi; Guo, Heng; Williams, Tyson
3
2014
Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions. Zbl 1300.05246
Cai, Jin-Yi; Kowalczyk, Michael
3
2013
Inapproximability after uniqueness phase transition in two-spin systems. Zbl 1358.82018
Cai, Jin-Yi; Chen, Xi; Guo, Heng; Lu, Pinyan
3
2012
Spin systems on graphs with complex edge functions and specified degree regularities. Zbl 1353.68110
Cai, Jin-Yi; Kowalczyk, Michael
3
2011
Approximation and hardness results for label cut and related problems. Zbl 1241.90129
Zhang, Peng; Cai, Jin-Yi; Tang, Linqing; Zhao, Wenbo
3
2009
Time-space tradeoff in derandomizing probabilistic logspace. Zbl 1101.68109
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; van Melkebeek, Dieter
3
2006
A new transference theorem in the geometry of numbers and new bounds for Ajtai’s connection factor. Zbl 1116.11050
Cai, Jin-Yi
3
2003
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
Computing Jordan normal forms exactly for commuting matrices in polynomial time. Zbl 0830.68061
Cai, Jin-Yi
3
1994
Playing games of incomplete information. Zbl 0786.90094
Cai, Jin-yi; Condon, Anne; Lipton, Richard J.
3
1990
Case-cohort studies with interval-censored failure time data. Zbl 07072179
Zhou, Q.; Zhou, H.; Cai, J.
2
2017
Complexity dichotomies for counting problems. Volume 1. Boolean domain. Zbl 06821418
Cai, Jin-Yi; Chen, Xi
2
2017
Holographic algorithm with matchgates is universal for planar #CSP over Boolean domain. Zbl 1369.68233
Cai, Jin-Yi; Fu, Zhiguo
2
2017
Dichotomy for Holant* problems with a function on domain size 3. Zbl 1421.68065
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
2
2013
On tractable exponential sums. Zbl 1288.68104
Cai, Jin-Yi; Chen, Xi; Lipton, Richard; Lu, Pinyan
2
2010
An attacker-defender game for honeynets. Zbl 1248.68072
Cai, Jin-Yi; Yegneswaran, Vinod; Alfeld, Chris; Barford, Paul
2
2009
On zero error algorithms having oracle access to one query. Zbl 1130.90068
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.
2
2006
On testing for zero polynomials by a set of points with bounded precision. Zbl 0991.68156
Cai, Jin-Yi; Bach, Eric
2
2001
The complexity of the \(A\) \(B\) \(C\) problem. Zbl 0967.20029
Cai, Jin-yi; Lipton, Richard J.; Zalcstein, Yechezkel
2
2000
Fine separation of average-time complexity classes. Zbl 0939.68041
Cai, Jin-Yi; Selman, Alan L.
2
1999
On the hardness of permanent. Zbl 0931.65048
Cai, Jin-Yi; Pavan, A.; Sivakumar, D.
2
1999
Resolution of Hartmanis’ conjecture for NL-hard sparse sets. Zbl 0884.68052
Cai, Jin-Yi; Sivakumar, D.
2
1997
Fine separation of average time complexity classes. Zbl 1379.68139
Cai, Jin-yi; Selman, Alan L.
2
1996
Advances in computational complexity theory. Zbl 0786.00007
Cai, Jin-Yi (ed.)
2
1993
Graph minimal uncolorability is \(D^ P\)-complete. Zbl 0626.05017
Cai, Jin-Yi; Meyer, Gabriele E.
2
1987
Dichotomy for real Holant\(^{\mathrm c}\) problems. Zbl 1403.68076
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
3
2018
Commuting mappings on the Hochschild extension of an algebra. Zbl 1410.16040
Chen, L.; Cai, J.
1
2018
Complexity classification of the six-vertex model. Zbl 1388.68107
Cai, Jin-Yi; Fu, Zhiguo; Xia, Mingji
1
2018
Holographic algorithms beyond matchgates. Zbl 1390.68338
Cai, Jin-Yi; Guo, Heng; Williams, Tyson
1
2018
Holographic algorithms with matchgates capture precisely tractable planar #CSP. Zbl 1370.68117
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
18
2017
Complexity of counting CSP with complex weights. Zbl 1426.68114
Cai, Jin-Yi; Chen, Xi
4
2017
Case-cohort studies with interval-censored failure time data. Zbl 07072179
Zhou, Q.; Zhou, H.; Cai, J.
2
2017
Complexity dichotomies for counting problems. Volume 1. Boolean domain. Zbl 06821418
Cai, Jin-Yi; Chen, Xi
2
2017
Holographic algorithm with matchgates is universal for planar #CSP over Boolean domain. Zbl 1369.68233
Cai, Jin-Yi; Fu, Zhiguo
2
2017
\(\#\)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
10
2016
A complete dichotomy rises from the capture of vanishing signatures. Zbl 1350.68133
Cai, Jin-Yi; Guo, Heng; Williams, Tyson
9
2016
Nonnegative weighted #CSP: an effective complexity dichotomy. Zbl 1356.68094
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan
8
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
4
2016
The complexity of complex weighted Boolean #CSP. Zbl 1311.68074
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
14
2014
Matchgates revisited. Zbl 1342.68156
Cai, Jin-Yi; Gorenstein, Aaron
7
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
1
2014
A complete dichotomy rises from the capture of vanishing signatures (extended abstract). Zbl 1293.68162
Cai, Jin-Yi; Guo, Heng; Williams, Tyson
17
2013
Graph homomorphisms with complex values: a dichotomy theorem. Zbl 1275.68073
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan
15
2013
Holographic algorithms by Fibonacci gates. Zbl 1257.05004
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
11
2013
Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions. Zbl 1300.05246
Cai, Jin-Yi; Kowalczyk, Michael
3
2013
Dichotomy for Holant* problems with a function on domain size 3. Zbl 1421.68065
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
2
2013
Complexity dichotomy for counting problems. Zbl 1377.68093
Cai, Jin-Yi
1
2013
Complexity of counting CSP with complex weights. Zbl 1286.68182
Cai, Jin-Yi; Chen, Xi
18
2012
From Holant to #CSP and back: dichotomy for Holant\(^{c}\) problems. Zbl 1255.68079
Cai, Jin-Yi; Huang, Sangxia; Lu, Pinyan
10
2012
Spin systems on \(k\)-regular graphs with complex edge functions. Zbl 1252.68149
Cai, Jin-Yi; Kowalczyk, Michael
7
2012
Gadgets and anti-gadgets leading to a complexity dichotomy. Zbl 1347.68178
Cai, Jin-Yi; Kowalczyk, Michael; Williams, Tyson
6
2012
Holographic reduction, interpolation and hardness. Zbl 1282.68120
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
6
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: from art to science. Zbl 1214.68170
Cai, Jin-Yi; Lu, Pinyan
20
2011
Computational complexity of Holant problems. Zbl 1234.68130
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
18
2011
Dichotomy for Holant* problems of Boolean domain. Zbl 1373.68256
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
11
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
11
2011
A computational proof of complexity of some restricted counting problems. Zbl 1216.68122
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
7
2011
Signature theory in holographic algorithms. Zbl 1238.68184
Cai, Jin-Yi; Lu, Pinyan
4
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
Graph homomorphisms with complex values: a dichotomy theorem (extended abstract). Zbl 1288.05178
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan
12
2010
Holant problems for regular graphs with complex edge functions. Zbl 1250.68129
Kowalczyk, Michael; Cai, Jin-Yi
11
2010
From Holant to #CSP and back: dichotomy for Holant\(^{c }\) problems. Zbl 1310.68101
Cai, Jin-Yi; Huang, Sangxia; Lu, Pinyan
6
2010
Quadratic lower bound for permanent vs. determinant in any characteristic. Zbl 1204.68100
Cai, Jin-Yi; Chen, Xi; Li, Dong
5
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 symmetric signatures in holographic algorithms. Zbl 1204.68256
Cai, Jin-Yi; Lu, Pinyan
4
2010
On tractable exponential sums. Zbl 1288.68104
Cai, Jin-Yi; Chen, Xi; Lipton, Richard; Lu, Pinyan
2
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
28
2009
On the theory of matchgate computations. Zbl 1178.68254
Cai, Jin-Yi; Choudhary, Vinay; Lu, Pinyan
7
2009
A computational proof of complexity of some restricted counting problems. Zbl 1241.68068
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
5
2009
Holographic algorithms: the power of dimensionality resolved. Zbl 1172.68058
Cai, Jin-Yi; Lu, Pinyan
4
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
Signature theory in holographic algorithms. Zbl 1183.68718
Cai, Jin-Yi; Lu, Pinyan
7
2008
Holographic algorithms with unsymmetric signatures. Zbl 1192.68474
Cai, Jin-Yi; Lu, Pinyan
5
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
5
2008
Basis collapse in holographic algorithms. Zbl 1149.68036
Cai, Jin-Yi; Lu, Pinyan
4
2008
Holographic algorithms: from art to science. Zbl 1232.68055
Cai, Jin-Yi; Lu, Pinyan
16
2007
On symmetric signatures in holographic algorithms. Zbl 1186.68540
Cai, Jin-Yi; Lu, Pinyan
9
2007
\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\). Zbl 1133.68020
Cai, Jin-Yi
9
2007
Holographic algorithms: The power of dimensionality resolved. Zbl 1171.68841
Cai, Jin-Yi; Lu, Pinyan
7
2007
Valiant’s holant theorem and matchgate tensors. Zbl 1124.68113
Cai, Jin-Yi; Choudhary, Vinay
7
2007
Holographic algorithms. Zbl 1167.68058
Cai, Jin-Yi
1
2007
On block-wise symmetric signatures for matchgates. Zbl 1135.68436
Cai, Jin-Yi; Lu, Pinyan
1
2007
Some results on matchgates and holographic algorithms. Zbl 1223.68120
Cai, Jin-Yi; Choudhary, Vinay
15
2006
Valiant’s holant theorem and matchgate tensors. Zbl 1178.68660
Cai, Jin-Yi; Choudhary, Vinay
7
2006
Time-space tradeoff in derandomizing probabilistic logspace. Zbl 1101.68109
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; van Melkebeek, Dieter
3
2006
On zero error algorithms having oracle access to one query. Zbl 1130.90068
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.
2
2006
Competing provers yield improved Karp-Lipton collapse results. Zbl 1066.68050
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori
12
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
Competing provers yield improved Karp-Lipton collapse results. Zbl 1035.68053
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori
4
2003
A new transference theorem in the geometry of numbers and new bounds for Ajtai’s connection factor. Zbl 1116.11050
Cai, Jin-Yi
3
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
2
2001
Circuit minimization problem. Zbl 1296.94182
Kabanets, Valentine; Cai, Jin-Yi
21
2000
The complexity of the \(A\) \(B\) \(C\) problem. Zbl 0967.20029
Cai, Jin-yi; Lipton, Richard J.; Zalcstein, Yechezkel
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
Resolution of Hartmanis’ conjecture for NL-hard sparse sets. Zbl 0945.68102
Cai, J.-Y.; Sivakumar, D.
1
2000
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
6
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
On the hardness of permanent. Zbl 0931.65048
Cai, Jin-Yi; Pavan, A.; Sivakumar, D.
2
1999
Hardness and hierarchy theorems for probabilistic quasi-polynomial time. Zbl 1346.68095
Cai, Jin-Yi; Nerurkar, Ajay; Sivakumar, D.
1
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
A relation of primal–dual lattices and the complexity of shortest lattice vector problem. Zbl 0926.11047
Cai, Jin-Yi
7
1998
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
5
1998
Robust reductions. Zbl 0912.68051
Cai, Jin-Yi; Hemaspaandra, Lane A.; Wechsung, Gerd
1
1998
Efficient algorithms for a scheduling problem and its applications to illicit drug market crackdowns. Zbl 0896.90136
Cai, Pu; Cai, Jin-Yi; Naik, Ashish V.
1
1998
Sparse sets versus complexity classes. Zbl 0880.68038
Cai, Jin-Yi; Ogihara, Mitsunori
5
1997
Resolution of Hartmanis’ conjecture for NL-hard sparse sets. Zbl 0884.68052
Cai, Jin-Yi; Sivakumar, D.
2
1997
On the 100% rule of sensitivity analysis in linear programming. Zbl 0898.90087
Cai, Pu; Cai, Jin-Yi
1
1997
On the correlation of symmetric functions. Zbl 0858.94033
Cai, Jin-Yi; Green, F.; Thierauf, T.
17
1996
Multiplicative equations over commuting matrices. Zbl 0865.15012
Babai, László; Beals, Robert; Cai, Jin-yi; Ivanyos, Gábor; Luks, Eugene M.
12
1996
On the existence of hard sparse sets under weak reductions. Zbl 1379.68138
Cai, Jin-Yi; Naik, Ashish V.; Sivakumar, D.
6
1996
Fine separation of average time complexity classes. Zbl 1379.68139
Cai, Jin-yi; Selman, Alan L.
2
1996
The bounded membership problem of the monoid \(\mathrm{SL}_2(N)\). Zbl 0860.68045
Cai, J.; Liu, Zicheng
1
1996
Pseudorandom generators, measure theory, and natural proofs. Zbl 0938.68822
Regan, Kenneth W.; Sivakumar, D.; Cai, Jin-yi
11
1995
The resolution of a Hartmanis conjecture. Zbl 0938.68666
Cai, Jin-yi; Sivakumar, D.
5
1995
Communication complexity of key agreement on small ranges. Zbl 1379.68127
Cai, Jin-Yi; Lipton, Richard J.; Longpré, Luc; Ogihara, Mitsunori; Regan, Kenneth W.; Sivakumar, D.
1
1995
...and 24 more Documents
all top 5

Cited by 708 Authors

48 Cai, Jin-Yi
31 Hemaspaandra, Lane A.
17 Lu, Pinyan
15 Goldberg, Leslie Ann
12 Allender, Eric W.
12 Beigel, Richard
10 Verbitsky, Oleg
9 Grohe, Martin
9 Guo, Heng
9 Köbler, Johannes
9 Ogihara, Mitsunori
8 Medina, Luis A.
8 Richerby, David M.
8 Rothe, Jörg-Matthias
7 Castro, Francis Noel
7 Fortnow, Lance J.
7 Gasarch, William Ian
7 Wagner, Klaus W.
6 Dawar, Anuj
6 Green, Frederic
6 Jerrum, Mark R.
6 Mayordomo, Elvira
6 van Melkebeek, Dieter
6 Xia, Mingji
5 Arvind, Vikraman
5 Buhrman, Harry
5 Chang, Richard
5 Curticapean, Radu
5 Fu, Zhiguo
5 Grädel, Erich
5 Hou, Jianfeng
5 Lutz, Jack H.
5 Ogiwara, Mitsunori
5 Pavan, Aduri
5 Regts, Guus
5 Selman, Alan L.
5 Williams, Tyson
5 Yamakami, Tomoyuki
4 Book, Ronald Vernon
4 Braga, Mónica
4 Bulatov, Andrei A.
4 Cygan, Marek
4 Dell, Holger
4 Dyer, Martin E.
4 Galanis, Andreas
4 Glaßer, Christian
4 Hitchcock, John M.
4 Kowalczyk, Michael
4 Li, Keqin
4 Liu, Guizhen
4 Marenco, Javier L.
4 Otto, Martin
4 Pikhurko, Oleg
4 Pilipczuk, Marcin
4 Pilipczuk, Michał
4 Potapov, Igor
4 Staiger, Ludwig
4 Stephan, Frank
4 Torán, Jacobo
4 Turner, Jacob M.
4 Watanabe, Osamu
4 Wechsung, Gerd
3 Barvinok, Alexander I.
3 Berkholz, Christoph
3 Chakaravarthy, Venkatesan T.
3 Chen, Xi
3 Evdokimov, Sergeĭ Alekseevich
3 Fu, Bin
3 Hartmanis, Juris
3 Hella, Lauri T.
3 Hemaspaandra, Edith
3 Hempel, Harald
3 Jalsenius, Markus
3 Kabanets, Valentine
3 Kolaitis, Phokion G.
3 Luosto, Kerkko
3 Mcquillan, Colin
3 Ponomarenko, Ilya Nikolaevich
3 Reimann, Jan
3 Roth, Marc
3 Sepúlveda, L. Brehsner
3 Severini, Simone
3 Silvestri, Riccardo
3 Štefankovič, Daniel
3 Thakur, Mayur
3 Torenvliet, Leen
3 Vigoda, Eric
3 Vinodchandran, N. Variyam
3 Zhang, Peng
3 Zimand, Marius
3 Živný, Stanislav
2 Alfeld, Chris
2 Amir, Amihood
2 Atserias, Albert
2 Aydinlioǧlu, Bariş
2 Barford, Paul
2 Baumeister, Dorothea
2 Bell, Paul C.
2 Beyersdorff, Olaf
2 Blass, Andreas Raphael
...and 608 more Authors
all top 5

Cited in 101 Serials

79 Theoretical Computer Science
58 Journal of Computer and System Sciences
43 Information and Computation
31 Information Processing Letters
23 Computational Complexity
21 Theory of Computing Systems
14 Discrete Applied Mathematics
14 SIAM Journal on Computing
13 The Journal of Symbolic Logic
12 Algorithmica
11 Mathematical Systems Theory
9 Annals of Pure and Applied Logic
8 Journal of Combinatorial Optimization
5 Journal of Symbolic Computation
5 The Bulletin of Symbolic Logic
4 Discrete Mathematics
4 European Journal of Combinatorics
4 International Journal of Foundations of Computer Science
4 Linear Algebra and its Applications
4 Journal of Scheduling
4 Logical Methods in Computer Science
3 Communications in Mathematical Physics
3 Advances in Mathematics
3 Journal of Combinatorial Theory. Series A
3 Journal of Combinatorial Theory. Series B
3 Journal of Number Theory
3 Journal of Pure and Applied Algebra
3 Combinatorica
3 RAIRO. Informatique Théorique et Applications
3 Mathematical Programming. Series A. Series B
3 Journal of Algebraic Combinatorics
3 Optimization Methods & Software
3 Science China. Mathematics
2 International Journal of Algebra and Computation
2 European Journal of Operational Research
2 Annals of Mathematics and Artificial Intelligence
2 Foundations of Computational Mathematics
2 Journal of Discrete Algorithms
2 ACM Transactions on Computation Theory
2 Research in the Mathematical Sciences
1 Artificial Intelligence
1 International Journal of Systems Science
1 Journal of Statistical Physics
1 Linear and Multilinear Algebra
1 Applied Mathematics and Computation
1 Biometrics
1 BIT
1 Journal of Graph Theory
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 Studia Logica
1 Transactions of the American Mathematical Society
1 Advances in Applied Mathematics
1 Operations Research Letters
1 Bulletin of the Iranian Mathematical Society
1 Graphs and Combinatorics
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 Neural Computation
1 International Journal of Computational Geometry & Applications
1 The Annals of Applied Probability
1 Differential Geometry and its Applications
1 The Journal of Geometric Analysis
1 International Journal of Computer Mathematics
1 Distributed Computing
1 Archive for Mathematical Logic
1 Applicable Algebra in Engineering, Communication and Computing
1 Combinatorics, Probability and Computing
1 Journal of Mathematical Sciences (New York)
1 Mathematical Logic Quarterly (MLQ)
1 Finite Fields and their Applications
1 Lifetime Data Analysis
1 Complexity
1 Journal of Heuristics
1 Journal of Graph Algorithms and Applications
1 Annals of Combinatorics
1 LMS Journal of Computation and Mathematics
1 RAIRO. Theoretical Informatics and Applications
1 CEJOR. Central European Journal of Operations Research
1 RAIRO. Operations Research
1 Theory and Practice of Logic Programming
1 Journal of Machine Learning Research (JMLR)
1 Comptes Rendus. Mathématique. Académie des Sciences, Paris
1 Journal of Applied Mathematics and Computing
1 ACM Transactions on Computational Logic
1 Discrete Optimization
1 Frontiers of Mathematics in China
1 Electronic Journal of Statistics
1 Involve
1 Mathematical Programming Computation
1 Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A: Matemáticas. RACSAM
1 RAIRO. Theoretical Informatics and Applications
1 Theory of Computing
1 Forum of Mathematics, Sigma
...and 1 more Serials

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.