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
5502003
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
4861992
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
2511988
The boolean hierarchy II: Applications
JY Cai, T Gundermann, J Hartmanis, LA Hemachandra, V Sewelson, ...
SIAM Journal on Computing 18 (1), 95-111, 1989
1431989
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
1361989
S2 ZPPNP
JY Cai
Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 620-628, 2001
128*2001
Circuit minimization problem
V Kabanets, JY Cai
Proceedings of the thirty-second annual ACM symposium on Theory of computing …, 2000
1242000
Holographic algorithms: From art to science
JY Cai, P Lu
Journal of Computer and System Sciences 77 (1), 41-61, 2011
1212011
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
1211997
On the power of parity polynomial time
JY Cai, LA Hemachandra
Mathematical Systems Theory 23 (1), 95-106, 1990
1141990
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
1052012
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
1041986
Holant problems and counting CSP
JY Cai, P Lu, M Xia
Proceedings of the forty-first annual ACM symposium on Theory of computing …, 2009
1012009
The Boolean hierarchy: hardware over NP
J Cai, L Hemachandra
Structure in Complexity Theory, 105-124, 1986
981986
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
971998
Enumerative counting is hard
JY Cai, LA Hemachandra
Information and Computation 82 (1), 34-44, 1989
831989
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
721996
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
721994
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
712008
Graph homomorphisms with complex values: A dichotomy theorem
JY Cai, X Chen, P Lu
International Colloquium on Automata, Languages, and Programming, 275-286, 2010
652010
The system can't perform the operation now. Try again later.
Articles 1–20