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 | 615 | 2003 |
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 | 599 | 1992 |
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 | 255 | 1988 |
Circuit minimization problem V Kabanets, JY Cai Proceedings of the thirty-second annual ACM symposium on Theory of computing …, 2000 | 173 | 2000 |
The boolean hierarchy II: Applications JY Cai, T Gundermann, J Hartmanis, LA Hemachandra, V Sewelson, ... SIAM Journal on Computing 18 (1), 95-111, 1989 | 142 | 1989 |
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 | 141 | 1989 |
Holographic algorithms: From art to science JY Cai, P Lu Journal of Computer and System Sciences 77 (1), 41-61, 2011 | 134 | 2011 |
S2 ZPPNP JY Cai Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 620-628, 2001 | 132* | 2001 |
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 | 126 | 2012 |
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 | 120 | 1997 |
Holant problems and counting CSP JY Cai, P Lu, M Xia Proceedings of the forty-first annual ACM symposium on Theory of computing …, 2009 | 114 | 2009 |
On the power of parity polynomial time JY Cai, LA Hemachandra Mathematical Systems Theory 23 (1), 95-106, 1990 | 113 | 1990 |
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 | 111 | 1986 |
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 | 104 | 1998 |
The Boolean hierarchy: hardware over NP J Cai, L Hemachandra Structure in Complexity Theory, 105-124, 1986 | 94 | 1986 |
Enumerative counting is hard JY Cai, LA Hemachandra Information and Computation 82 (1), 34-44, 1989 | 85 | 1989 |
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 | 80 | 2008 |
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 | 79 | 1996 |
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 | 75 | 1994 |
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 | 74 | 2016 |