Follow
Jin-Yi Cai
Jin-Yi Cai
Verified email at cs.wisc.edu - Homepage
Title
Cited by
Cited by
Year
An optimal lower bound on the number of variables for graph identification
JY Cai, M Fürer, N Immerman
Combinatorica 12 (4), 389-410, 1992
7841992
X-Diff: An effective change detection algorithm for XML documents
Y Wang, DJ DeWitt, JY Cai
Proceedings 19th international conference on data engineering (Cat. No …, 2003
6432003
Decoupling control
QG Wang
Springer Science & Business Media, 2002
483*2002
The boolean hierarchy I: Structural properties
JY Cai, T Gundermann, J Hartmanis, LA Hemachandra, V Sewelson, ...
SIAM Journal on Computing 17 (6), 1232-1252, 1988
2661988
Circuit minimization problem
V Kabanets, JY Cai
Proceedings of the thirty-second annual ACM symposium on Theory of computing …, 2000
2112000
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
JY Cai
Proceedings of the eighteenth annual ACM symposium on Theory of computing, 21-29, 1986
1511986
The boolean hierarchy II: Applications
JY Cai, T Gundermann, J Hartmanis, LA Hemachandra, V Sewelson, ...
SIAM Journal on Computing 18 (1), 95-111, 1989
1471989
On differentially private frequent itemset mining
C Zeng, JF Naughton, JY Cai
The VLDB journal: very large data bases: a publication of the VLDB Endowment …, 2012
1402012
An improved worst-case to average-case connection for lattice problems
JY Cai, AP Nerurkar
Proceedings 38th Annual Symposium on Foundations of Computer Science, 468-477, 1997
1351997
Graph homomorphisms with complex values: A dichotomy theorem
JY Cai, X Chen, P Lu
SIAM Journal on Computing 42 (3), 924-1029, 2013
1332013
Holographic algorithms: From art to science
JY Cai, P Lu
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing …, 2007
1302007
The cyclic coloring problem and estimation of sparse Hessian matrices
TF Coleman, JY Cai
SIAM Journal on Algebraic Discrete Methods 7 (2), 221-235, 1986
1241986
2⊆ ZPPnp
JY Cai
Journal of Computer and System Sciences 73 (1), 25-35, 2007
122*2007
On the power of parity polynomial time
JY Cai, LA Hemachandra
Mathematical Systems Theory 23, 95-106, 1990
1181990
Approximating the SVP to within a factor (1-1/dim/sup/spl epsiv//) is NP-hard under randomized conditions
JY Cai, A Nerurkar
Proceedings. Thirteenth Annual IEEE Conference on Computational Complexity …, 1998
1161998
Holant problems and counting CSP
JY Cai, P Lu, M Xia
Proceedings of the forty-first annual ACM symposium on Theory of computing …, 2009
1132009
Complexity of counting CSP with complex weights
JY Cai, X Chen
Journal of the ACM (JACM) 64 (3), 1-39, 2017
1092017
The Boolean hierarchy: hardware over NP
J Cai, L Hemachandra
Structure in Complexity Theory: Proceedings of the Conference held at the …, 2005
1092005
Multiplicative equations over commuting matrices
L Babai, R Beals, J Cai, G Ivanyos, EM Luks
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms …, 1996
981996
On the hardness of permanent
JY Cai, A Pavan, D Sivakumar
Annual Symposium on Theoretical Aspects of Computer Science, 90-99, 1999
841999
The system can't perform the operation now. Try again later.
Articles 1–20