Jin-Yi Cai
Jin-Yi Cai
Verified email at cs.wisc.edu - Homepage
Title
Cited by
Cited by
Year
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
5962003
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
5591992
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
2521988
Circuit minimization problem
V Kabanets, JY Cai
Proceedings of the thirty-second annual ACM symposium on Theory of computing …, 2000
1582000
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
JY Cai
Journal of Computer and System Sciences 38 (1), 68-85, 1989
1411989
The boolean hierarchy II: Applications
JY Cai, T Gundermann, J Hartmanis, LA Hemachandra, V Sewelson, ...
SIAM Journal on Computing 18 (1), 95-111, 1989
1401989
Holographic algorithms: From art to science
JY Cai, P Lu
Journal of Computer and System Sciences 77 (1), 41-61, 2011
1302011
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
1272012
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
1221997
On the power of parity polynomial time
JY Cai, LA Hemachandra
Mathematical Systems Theory 23 (1), 95-106, 1990
1141990
Holant problems and counting CSP
JY Cai, P Lu, M Xia
Proceedings of the forty-first annual ACM symposium on Theory of computing …, 2009
1112009
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
1091986
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
1061998
The Boolean hierarchy: hardware over NP
J Cai, L Hemachandra
Structure in Complexity Theory, 105-124, 1986
991986
2⊆ ZPPNP
JY Cai
87*2001
Enumerative counting is hard
JY Cai, LA Hemachandra
Information and Computation 82 (1), 34-44, 1989
841989
Holographic algorithms by fibonacci gates and holographic reductions for hardness
JY Cai, P Lu, M Xia
2008 49th Annual IEEE Symposium on Foundations of Computer Science, 644-653, 2008
782008
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
761996
On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
JY Cai, J Hartmanis
Journal of Computer and System Sciences 49 (3), 605-619, 1994
761994
A complete dichotomy rises from the capture of vanishing signatures
JY Cai, H Guo, T Williams
SIAM Journal on Computing 45 (5), 1671-1728, 2016
712016
The system can't perform the operation now. Try again later.
Articles 1–20