Jin-yi Cai Papers on DiSC'04 X-Diff: An Effective Change Detection Algorithm for XML Documents Publications Note: Links lead to the DBLP on the Web. Jin-yi Cai Jin-yi Cai, Venkatesan T. Chakaravarthy , Dieter van Melkebeek : Time-Space Tradeoff in Derandomizing Probabilistic Logspace. STACS 2004 : 571-583 Jin-yi Cai, Osamu Watanabe : On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results. COCOON 2003 : 202-211 Jin-yi Cai, Osamu Watanabe : Stringent Relativization. FSTTCS 2003 : 408-419 Yuan Wang , David J. DeWitt , Jin-yi Cai: X-Diff: An Effective Change Detection Algorithm for XML Documents. ICDE 2003 : 519-530 Micah Adler , Jin-yi Cai, Jonathan K. Shapiro , Donald F. Towsley : Estimation of Congestion Price Using Probabilistic Packet Marking. INFOCOM 2003 Jin-yi Cai, Venkatesan T. Chakaravarthy , Lane A. Hemaspaandra , Mitsunori Ogihara : Competing Provers Yield Improved Karp-Lipton Collapse Results. STACS 2003 : 535-546 Jin-yi Cai: A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor. Discrete Applied Mathematics 126 (1): 9-31 (2003) Jin-yi Cai, Eric Bach : On testing for zero polynomials by a set of points with bounded precision. Theor. Comput. Sci. 296 (1): 15-25 (2003) Jin-yi Cai: Essentially Every Unimodular Matrix Defines an Expander. Theory Comput. Syst. 36 (2): 105-135 (2003) Jin-yi Cai, Denis Charles , Aduri Pavan , Samik Sengupta : On Higher Arthur-Merlin Classes. COCOON 2002 : 18-27 Jin-yi Cai: On the Minimum Volume of a Perturbed Unit Cube. ISAAC 2002 : 67-78 Jin-yi Cai, Eric Bach : On Testing for Zero Polynomials by a Set of Points with Bounded Precision. COCOON 2001 : 473-482 Jin-yi Cai: On the Average-Case Hardness of CVP. FOCS 2001 : 308-317 Jin-yi Cai: S p 2 subseteq ZPP NP . FOCS 2001 : 620-629 Jin-yi Cai, Venkatesan T. Chakaravarthy , Raghav Kaushik , Jeffrey F. Naughton : On the Complexity of Join Predicates. PODS 2001 Jin-yi Cai: Essentially every unimodular matrix defines an expander Electronic Colloquium on Computational Complexity (ECCC) 8 (1): (2001) Jin-yi Cai: S_2 p \subseteq ZPP NP Electronic Colloquium on Computational Complexity (ECCC) 8 (30): (2001) Jin-yi Cai: The Complexity of Some Lattice Problems. ANTS 2000 : 1-32 Jin-yi Cai: Essentially Every Unimodular Matrix Defines and Expander. ISAAC 2000 : 2-22 Valentine Kabanets , Jin-yi Cai: Circuit minimization problem. STOC 2000 : 73-79 Jin-yi Cai, Ajay Nerurkar : A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. Inf. Process. Lett. 76 (1-2): 61-66 (2000) Jin-yi Cai, Richard J. Lipton , Yechezkel Zalcstein : The Complexity of the A B C Problem. SIAM J. Comput. 29 (6): 1878-1888 (2000) Jin-yi Cai, D. Sivakumar : Resolution of Hartmanis' conjecture for NL-hard sparse sets. Theor. Comput. Sci. 240 (2): 257-269 (2000) Jin-yi Cai: A New Transference Theorem in the Geometry of Numbers. COCOON 1999 : 113-122 Jin-yi Cai, George Havas , Bernard Mans , Ajay Nerurkar , Jean-Pierre Seifert , Igor Shparlinski : On Routing in Circulant Graphs. COCOON 1999 : 360-369 Jin-yi Cai: Some Recent Progress on the Complexity of Lattice Problems. IEEE Conference on Computational Complexity 1999 : 158- Jin-yi Cai: Applications of a New Transference Theorem to Ajtai's Connection Factor. IEEE Conference on Computational Complexity 1999 : 205-214 Jin-yi Cai, Aduri Pavan , D. Sivakumar : On the Hardness of Permanent. STACS 1999 : 90-99 Jin-yi Cai, Ajay Nerurkar , D. Sivakumar : Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. STOC 1999 : 726-735 Jin-yi Cai, C. K. Wong : Foreword. Algorithmica 23 (4): 277 (1999) Valentine Kabanets , Jin-yi Cai: Circuit Minimization Problem Electronic Colloquium on Computational Complexity (ECCC) (45): (1999) Jin-yi Cai: Some Recent Progress on the Complexity of Lattice Problems Electronic Colloquium on Computational Complexity (ECCC) 6 (6): (1999) Jin-yi Cai, Thomas W. Cusick : A Lattice-Based Public-Key Cryptosystem. Inf. Comput. 151 (1-2): 17-31 (1999) Jin-yi Cai: A Classification of the Probabilistic Polynomial Time Hierarchy Under Fault Tolerant Access to Oracle Classes. Inf. Process. Lett. 69 (4): 167-174 (1999) Jin-yi Cai, D. Sivakumar : Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis. J. Comput. Syst. Sci. 58 (2): 280-296 (1999) Jin-yi Cai, Ajay Nerurkar : Approximating the SVP to within a Factor (1+1/dim xi ) Is NP-Hard under Randomized Reductions. J. Comput. Syst. Sci. 59 (2): 221-239 (1999) Jin-yi Cai, Alan L. Selman : Fine Separation of Average-Time Complexity Classes. SIAM J. Comput. 28 (4): 1310-1325 (1999) Jin-yi Cai, Lane A. Hemaspaandra , Gerd Wechsung : Robust Reductions. Theory Comput. Syst. 32 (6): 625-647 (1999) Jin-yi Cai, Lane A. Hemaspaandra , Gerd Wechsung : Robust Reductions. COCOON 1998 : 174-183 Jin-yi Cai, Ajay Nerurkar : Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions. IEEE Conference on Computational Complexity 1998 : 46- Jin-yi Cai, Thomas W. Cusick : A Lattice-Based Public-Key Cryptosystem. Selected Areas in Cryptography 1998 : 219-233 Jin-yi Cai: A new transference theorem and applications to Ajtai's connection factor Electronic Colloquium on Computational Complexity (ECCC) 5 (5): (1998) Pu Cai , Jin-yi Cai, Ashish V. Naik : Efficient Algorithms for a Scheduling Problem and its Applications to Illicit Drug Market Crackdowns. J. Comb. Optim. 1 (4): 367-376 (1998) Jin-yi Cai: A Relation of Primal-Dual Lattices and the Complexity of Shortest Lattice Vector Problem. Theor. Comput. Sci. 207 (1): 105-116 (1998) Jin-yi Cai: Frobenius's Degree Formula and Toda's Polynomials. Theory Comput. Syst. 31 (1): 67-75 (1998) Pu Cai , Jin-yi Cai: On the 100% Rule of Sensivity Analzsis in Linear Programming. COCOON 1997 : 460-469 Jin-yi Cai, D. Sivakumar : Resolution of Hartmanis' Conjecture for NL-Hard Sparse Sets. COCOON 1997 : 62-71 Jin-yi Cai, Ajay Nerurkar : An Improved Worst-Case to Average-Case Connection for Lattice Problems. FOCS 1997 : 468-477 Jin-yi Cai, D. Sivakumar , Martin Strauss : Constant Depth Circuits and the Lutz Hypothesis. FOCS 1997 : 595-604 Jin-yi Cai, Ajay Nerurkar : Approximating the SVP to within a factor (1 + 1/dim epsilon ) is NP-hard under randomized reductions Electronic Colloquium on Computational Complexity (ECCC) 4 (59): (1997) Jin-yi Cai, C. K. Wong : Computing and Combinatorics, Second Annual International Conference, COCOON '96, Hong Kong, June 17-19, 1996, Proceedings Springer 1996 László Babai , Robert Beals , Jin-yi Cai, Gábor Ivanyos , Eugene M. Luks : Multiplicative Equations over Commuting Matrices. SODA 1996 : 498-507 Jin-yi Cai, Ashish V. Naik , D. Sivakumar : On the Existence of Hard Sparse Sets under Weak Reductions. STACS 1996 : 307-318 Jin-yi Cai, Alan L. Selman : Fine Separation of Average Time Complexity Classes. STACS 1996 : 331-343 Jin-yi Cai, Frederic Green , Thomas Thierauf : On the Correlation of Symmetric Functions. Mathematical Systems Theory 29 (3): 245-258 (1996) Jin-yi Cai, Zicheng Liu : The Bounded Membership Problem of the Monoid SL_2(N). Mathematical Systems Theory 29 (6): 573-587 (1996) Kenneth W. Regan , D. Sivakumar , Jin-yi Cai: Pseudorandom Generators, Measure Theory, and Natural Proofs. FOCS 1995 : 26-35 Jin-yi Cai, D. Sivakumar : The Resolution of a Hartmanis Conjecture. FOCS 1995 : 362-371 Jin-yi Cai, Richard J. Lipton , Luc Longpré , Mitsunori Ogihara , Kenneth W. Regan , D. Sivakumar : Communication Complexity of Key Agreement on Small Ranges. STACS 1995 : 38-49 Jin-yi Cai, Alan L. Selman : Average Time Complexity Classes Electronic Colloquium on Computational Complexity (ECCC) 2 (19): (1995) Kenneth W. Regan , D. Sivakumar , Jin-yi Cai: Pseudorandom Generators, Measure Theory, and Natural Proofs Electronic Colloquium on Computational Complexity (ECCC) 2 (6): (1995) Jin-yi Cai, Suresh Chari : On the Impossibility of Amplifying the Independence of Random Variables. Random Structures and Algorithms 7 (4): 301-310 (1995) Jin-yi Cai, Richard J. Lipton , Yechezkel Zalcstein : The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices FOCS 1994 : 135-142 Jin-yi Cai, Wolfgang H. J. Fuchs , Dexter Kozen , Zicheng Liu : Efficient Average-Case Algorithms for the Modular Group FOCS 1994 : 143-152 Jin-yi Cai, Michael D. Hirsch : Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic Geometry. ISAAC 1994 : 172-180 Sigal Ar , Jin-yi Cai: Reliable Benchmarks Using Numerical Instability. SODA 1994 : 34-43 Jin-yi Cai, Wolfgang H. J. Fuchs , Dexter Kozen , Zicheng Liu : Efficient Average-Case Algorithms for the Modular Group Electronic Colloquium on Computational Complexity (ECCC) 1 (16): (1994) Jin-yi Cai: Computing Jordan Normal Forms Exactly for Commuting Matrices in Polynomial Time. Int. J. Found. Comput. Sci. 5 (3/4): 293-302 (1994) Jin-yi Cai, Anne Condon , Richard J. Lipton : PSPACE Is Provable by Two Provers in One Round. J. Comput. Syst. Sci. 48 (1): 183-193 (1994) Jin-yi Cai, Juris Hartmanis : On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line. J. Comput. Syst. Sci. 49 (3): 605-619 (1994) Jin-yi Cai, Richard J. Lipton : Subquadratic Simulations of Balanced Formulae by Branching Programs. SIAM J. Comput. 23 (3): 563-572 (1994) Jin-yi Cai, Richard J. Lipton , Robert Sedgewick , Andrew Chi-Chih Yao : Towards Uncheatable benchmarks. Structure in Complexity Theory Conference 1993 : 2-11 Sandeep N. Bhatt , Jin-yi Cai: Taking Random Walks to Grow Trees in Hypercubes. J. ACM 40 (3): 741-764 (1993) Jin-yi Cai, Lane A. Hemachandra , Jozef Vyskoc : Promise Problems and Guarded Access to Unambiguous Computation. Complexity Theory: Current Research 1992 : 101-146 Jin-yi Cai, Lane A. Hemachandra , Jozef Vyskoc : Promise Problems and Access to Unambiguous Computation. MFCS 1992 : 162-171 Jin-yi Cai: Parallel Computation Over Hyperbolic Groups STOC 1992 : 106-115 Jin-yi Cai, Martin Fürer , Neil Immerman : An optimal lower bound on the number of variables for graph identifications. Combinatorica 12 (4): 389-410 (1992) Jin-yi Cai, Anne Condon , Richard J. Lipton : On Games of Incomplete Information. Theor. Comput. Sci. 103 (1): 25-38 (1992) Jin-yi Cai: Computations Over Infinite Groups. FCT 1991 : 22-32 Jin-yi Cai, Anne Condon , Richard J. Lipton : PSPACE Is Provable By Two Provers In One Round. Structure in Complexity Theory Conference 1991 : 110-115 Jin-yi Cai, Lane A. Hemachandra : A Note on Enumarative Counting. Inf. Process. Lett. 38 (4): 215-219 (1991) Jin-yi Cai, Merrick L. Furst : PSPACE Survives Constant-Width Bottlenecks. Int. J. Found. Comput. Sci. 2 (1): 67-76 (1991) Jin-yi Cai, Anne Condon , Richard J. Lipton : Playing Games of Incomplete Information. STACS 1990 : 58-69 Jin-yi Cai, Anne Condon , Richard J. Lipton : On Bounded Round Multi-Prover Interactive Proof Systems. Structure in Complexity Theory Conference 1990 : 45-54 Jin-yi Cai: A Note on the Determinant and Permanent Problem Inf. Comput. 84 (1): 119-127 (1990) Jin-yi Cai: Lower Bounds for Constant-Depth Circuits in the Presence of Help Bits. Inf. Process. Lett. 36 (2): 79-83 (1990) Jin-yi Cai, Lane A. Hemachandra : On the Power of Parity Polynomial Time. Mathematical Systems Theory 23 (2): 95-106 (1990) Jin-yi Cai: Lower Bounds for Constant Depth Circuits in the Presence of Help Bits FOCS 1989 : 532-537 Jin-yi Cai, Richard J. Lipton : Subquadratic Simulations of Circuits by Branching Programs FOCS 1989 : 568-573 Jin-yi Cai, Martin Fürer , Neil Immerman : An Optimal Lower Bound on the Number of Variables for Graph Identification FOCS 1989 : 612-617 Jin-yi Cai, Lane A. Hemachandra : On the Power of Parity Polynomial Time. STACS 1989 : 229-239 Jin-yi Cai, Juris Hartmanis : The Complexity Of The Real Line Is A Fractal. Structure in Complexity Theory Conference 1989 : 138-146 Jin-yi Cai, Lane A. Hemachandra : Enumerative Counting Is Hard Inf. Comput. 82 (1): 34-44 (1989) Jin-yi Cai: With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy. J. Comput. Syst. Sci. 38 (1): 68-85 (1989) Jin-yi Cai, Thomas Gundermann , Juris Hartmanis , Lane A. Hemachandra , Vivian Sewelson , Klaus W. Wagner , Gerd Wechsung : The Boolean Hierarchy II: Applications. SIAM J. Comput. 18 (1): 95-111 (1989) Sandeep N. Bhatt , Jin-yi Cai: Take a Walk, Grow a Tree (Preliminary Version) FOCS 1988 : 469-478 Jin-yi Cai, Thomas Gundermann , Juris Hartmanis , Lane A. Hemachandra , Vivian Sewelson , Klaus W. Wagner , Gerd Wechsung : The Boolean Hierarchy I: Structural Properties. SIAM J. Comput. 17 (6): 1232-1252 (1988) Jin-yi Cai, Gabriele E. Meyer : On the Complexity of Graph Critical Uncolorability. ICALP 1987 : 394-403 Jin-yi Cai: Probability One Separation of the Boolean Hierarchy. STACS 1987 : 148-158 Jin-yi Cai, Gabriele E. Meyer : Graph Minimal Uncolorability is D^P-Complete. SIAM J. Comput. 16 (2): 259-277 (1987) Jin-yi Cai: With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy STOC 1986 : 21-29 Jin-yi Cai: With Probability One, A Random Oracle Separates PSPACE from the Polynomial- Time Hierarchy. Structure in Complexity Theory Conference 1986 : 104-104 Jin-yi Cai, Lane A. Hemachandra : The Boolean Hierarchy: Hardware over NP. Structure in Complexity Theory Conference 1986 : 105-124 1 [ 99 ] 2 [ 38 ] 3 [ 52 ] 4 [ 92 ] [ 96 ] 5 [ 52 ] 6 [ 8 ] [ 31 ] 7 [ 58 ] [ 61 ] 8 [ 89 ] [ 98 ] [ 103 ] 9 [ 42 ] 10 [ 94 ] 11 [ 20 ] [ 21 ] [ 24 ] [ 26 ] [ 35 ] 12 [ 63 ] [ 71 ] 13 [ 100 ] 14 [ 37 ] [ 40 ] 15 [ 14 ] [ 27 ] 16 [ 22 ] 17 [ 49 ] 18 [ 7 ] [ 9 ] 19 [ 7 ] [ 9 ] [ 12 ] [ 34 ] 20 [ 79 ] 21 [ 1 ] [ 7 ] [ 9 ] [ 11 ] [ 13 ] [ 17 ] [ 23 ] [ 29 ] [ 30 ] 22 [ 65 ] [ 66 ] [ 98 ] 23 [ 39 ] 24 [ 14 ] [ 27 ] 25 [ 52 ] 26 [ 73 ] [ 84 ] 27 [ 89 ] 28 [ 37 ] [ 40 ] 29 [ 15 ] [ 20 ] [ 21 ] [ 24 ] [ 26 ] [ 32 ] [ 33 ] [ 35 ] [ 41 ] [ 45 ] [ 82 ] 30 [ 37 ] [ 40 ] [ 48 ] 31 [ 45 ] 32 [ 52 ] 33 [ 79 ] 34 [ 103 ] 35 [ 4 ] [ 6 ] 36 [ 51 ] [ 61 ] 37 [ 89 ] 38 [ 54 ] [ 56 ] [ 64 ] [ 68 ] [ 75 ] [ 79 ] [ 83 ] 39 [ 45 ] [ 98 ] 40 [ 76 ] [ 94 ] 41 [ 43 ] [ 45 ] [ 47 ] 42 [ 32 ] 43 [ 79 ] 44 [ 44 ] [ 50 ] [ 67 ] 45 [ 94 ] 46 [ 7 ] [ 9 ] 47 [ 99 ] 48 [ 79 ] 49 [ 43 ] [ 45 ] [ 46 ] [ 47 ] [ 51 ] [ 55 ] [ 57 ] [ 69 ] [ 75 ] [ 76 ] [ 81 ] 50 [ 55 ] 51 [ 49 ] 52 [ 99 ] 53 [ 29 ] [ 30 ] 54 [ 7 ] [ 9 ] 55 [ 100 ] 56 [ 101 ] [ 102 ] 57 [ 7 ] [ 9 ] [ 65 ] [ 66 ] 58 [ 53 ] [ 74 ] 59 [ 32 ] 60 [ 41 ] [ 82 ] ©2004 Association for Computing Machinery