| |
 |      |
                                            |
Note: Links lead to the DBLP on the Web. Jin-yi Cai 88 Jin-yi Cai, Eric Bach : On Testing for Zero Polynomials by a Set of Points with Bounded Precision. COCOON 2001 : 473-482 87 Jin-yi Cai: On the Average-Case Hardness of CVP. FOCS 2001 : 308-317 86 Jin-yi Cai: S p 2 subseteq ZPP NP . FOCS 2001 : 620-629 85 Jin-yi Cai, Venkatesan T. Chakaravarthy , Raghav Kaushik , Jeffrey F. Naughton : On the Complexity of Join Predicates. PODS 2001 84 Jin-yi Cai: Essentially every unimodular matrix defines an expander. Electronic Colloquium on Computational Complexity (ECCC) 8 (1): (2001) 83 Jin-yi Cai: S_2 p \subseteq ZPP NP . Electronic Colloquium on Computational Complexity (ECCC) 8 (30): (2001) 82 Jin-yi Cai: The Complexity of Some Lattice Problems. ANTS 2000 : 1-32 81 Jin-yi Cai: Essentially Every Unimodular Matrix Defines and Expander. ISAAC 2000 : 2-22 80 Valentine Kabanets , Jin-yi Cai: Circuit minimization problem. STOC 2000 : 73-79 79 Jin-yi Cai, Ajay Nerurkar : A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. Information Processing Letters 76 (1-2): 61-66 (2000) 78 Jin-yi Cai, Richard J. Lipton , Yechezkel Zalcstein : The Complexity of the A B C Problem. SIAM J. Comput. 29 (6): 1878-1888 (2000) 77 Jin-yi Cai, D. Sivakumar : Resolution of Hartmanis' conjecture for NL-hard sparse sets. TCS 240 (2): 257-269 (2000) 76 Jin-yi Cai: A New Transference Theorem in the Geometry of Numbers. COCOON 1999 : 113-122 75 Jin-yi Cai, George Havas , Bernard Mans , Ajay Nerurkar , Jean-Pierre Seifert , Igor Shparlinski : On Routing in Circulant Graphs. COCOON 1999 : 360-369 74 Jin-yi Cai: Some Recent Progress on the Complexity of Lattice Problems. IEEE Conference on Computational Complexity 1999 : 158- 73 Jin-yi Cai: Applications of a New Transference Theorem to Ajtai's Connection Factor. IEEE Conference on Computational Complexity 1999 : 205-214 72 Jin-yi Cai, Aduri Pavan , D. Sivakumar : On the Hardness of Permanent. STACS 1999 : 90-99 71 Jin-yi Cai, Ajay Nerurkar , D. Sivakumar : Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. STOC 1999 : 726-735 70 Jin-yi Cai, C. K. Wong : Foreword. Algorithmica 23 (4): 277 (1999) 69 Valentine Kabanets , Jin-yi Cai: Circuit Minimization Problem. Electronic Colloquium on Computational Complexity (ECCC) (45): (1999) 68 Jin-yi Cai: Some Recent Progress on the Complexity of Lattice Problems. Electronic Colloquium on Computational Complexity (ECCC) 6 (6): (1999) 67 Jin-yi Cai: A Classification of the Probabilistic Polynomial Time Hierarchy Under Fault Tolerant Access to Oracle Classes. Information Processing Letters 69 (4): 167-174 (1999) 66 Jin-yi Cai, Thomas W. Cusick : A Lattice-Based Public-Key Cryptosystem. Information and Computation 151 (1-2): 17-31 (1999) 65 Jin-yi Cai, D. Sivakumar : Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis. JCSS 58 (2): 280-296 (1999) 64 Jin-yi Cai, Ajay Nerurkar : Approximating the SVP to within a Factor (1+1/dim xi ) Is NP-Hard under Randomized Reductions. JCSS 59 (2): 221-239 (1999) 63 Jin-yi Cai, Alan L. Selman : Fine Separation of Average-Time Complexity Classes. SIAM J. Comput. 28 (4): 1310-1325 (1999) 62 Jin-yi Cai, Lane A. Hemaspaandra , Gerd Wechsung : Robust Reductions. Theory of Computing Systems 32 (6): 625-647 (1999) 61 Jin-yi Cai, Lane A. Hemaspaandra , Gerd Wechsung : Robust Reductions. COCOON 1998 : 174-183 60 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- 59 Jin-yi Cai, Thomas W. Cusick : A Lattice-Based Public-Key Cryptosystem. Selected Areas in Cryptography 1998 : 219-233 58 Jin-yi Cai: A new transference theorem and applications to Ajtai's connection factor. Electronic Colloquium on Computational Complexity (ECCC) 5 (5): (1998) 57 Pu Cai , Jin-yi Cai, Ashish V. Naik : Efficient Algorithms for a Scheduling Problem and its Applications to Illicit Drug Market Crackdowns. Journal of Combinatorial Optimization 1 (4): 367-376 (1998) 56 Jin-yi Cai: A Relation of Primal-Dual Lattices and the Complexity of Shortest Lattice Vector Problem. TCS 207 (1): 105-116 (1998) 55 Jin-yi Cai: Frobenius's Degree Formula and Toda's Polynomials. Theory of Computing Systems 31 (1): 67-75 (1998) 54 Pu Cai , Jin-yi Cai: On the 100% Rule of Sensivity Analzsis in Linear Programming. COCOON 1997 : 460-469 53 Jin-yi Cai, D. Sivakumar : Resolution of Hartmanis' Conjecture for NL-Hard Sparse Sets. COCOON 1997 : 62-71 52 Jin-yi Cai, Ajay Nerurkar : An Improved Worst-Case to Average-Case Connection for Lattice Problems. FOCS 1997 : 468-477 51 Jin-yi Cai, D. Sivakumar , Martin Strauss : Constant Depth Circuits and the Lutz Hypothesis. FOCS 1997 : 595-604 50 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) 49 Jin-yi Cai, C. K. Wong : Computing and Combinatorics, Second Annual International Conference, COCOON '96, Hong Kong, June 17-19, 1996, Proceedings. Springer 1996 48 László Babai , Robert Beals , Jin-yi Cai, Gábor Ivanyos , Eugene M. Luks : Multiplicative Equations over Commuting Matrices. SODA 1996 : 498-507 47 Jin-yi Cai, Ashish V. Naik , D. Sivakumar : On the Existence of Hard Sparse Sets under Weak Reductions. STACS 1996 : 307-318 46 Jin-yi Cai, Alan L. Selman : Fine Separation of Average Time Complexity Classes. STACS 1996 : 331-343 45 Jin-yi Cai, Frederic Green , Thomas Thierauf : On the Correlation of Symmetric Functions. Mathematical Systems Theory 29 (3): 245-258 (1996) 44 Jin-yi Cai, Zicheng Liu : The Bounded Membership Problem of the Monoid SL_2(N). Mathematical Systems Theory 29 (6): 573-587 (1996) 43 Kenneth W. Regan , D. Sivakumar , Jin-yi Cai: Pseudorandom Generators, Measure Theory, and Natural Proofs. FOCS 1995 : 26-35 42 Jin-yi Cai, D. Sivakumar : The Resolution of a Hartmanis Conjecture. FOCS 1995 : 362-371 41 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 40 Jin-yi Cai, Alan L. Selman : Average Time Complexity Classes. Electronic Colloquium on Computational Complexity (ECCC) 2 (19): (1995) 39 Kenneth W. Regan , D. Sivakumar , Jin-yi Cai: Pseudorandom Generators, Measure Theory, and Natural Proofs. Electronic Colloquium on Computational Complexity (ECCC) 2 (6): (1995) 38 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 37 Jin-yi Cai, Wolfgang H. J. Fuchs , Dexter Kozen , Zicheng Liu : Efficient Average-Case Algorithms for the Modular Group. FOCS 1994 : 143-152 36 Jin-yi Cai, Michael D. Hirsch : Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic Geometry. ISAAC 1994 : 172-180 35 Sigal Ar , Jin-yi Cai: Reliable Benchmarks Using Numerical Instability. SODA 1994 : 34-43 34 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) 33 Jin-yi Cai: Computing Jordan Normal Forms Exactly for Commuting Matrices in Polynomial Time. International Journal of Foundations of Computer Science 5 (3/4): 293-302 (1994) 32 Jin-yi Cai, Anne Condon , Richard J. Lipton : PSPACE Is Provable by Two Provers in One Round. JCSS 48 (1): 183-193 (1994) 31 Jin-yi Cai, Juris Hartmanis : On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line. JCSS 49 (3): 605-619 (1994) 30 Jin-yi Cai, Richard J. Lipton : Subquadratic Simulations of Balanced Formulae by Branching Programs. SIAM J. Comput. 23 (3): 563-572 (1994) 29 Jin-yi Cai, Richard J. Lipton , Robert Sedgewick , Andrew Chi-Chih Yao : Towards Uncheatable benchmarks. Structure in Complexity Theory Conference 1993 : 2-11 28 Sandeep N. Bhatt , Jin-yi Cai: Taking Random Walks to Grow Trees in Hypercubes. JACM 40 (3): 741-764 (1993) 27 Jin-yi Cai, Lane A. Hemachandra , Jozef Vyskoc : Promise Problems and Guarded Access to Unambiguous Computation. Complexity Theory: Current Research 1992 : 101-146 26 Jin-yi Cai, Lane A. Hemachandra , Jozef Vyskoc : Promise Problems and Access to Unambiguous Computation. MFCS 1992 : 162-171 25 Jin-yi Cai: Parallel Computation Over Hyperbolic Groups. STOC 1992 : 106-115 24 Jin-yi Cai, Anne Condon , Richard J. Lipton : On Games of Incomplete Information. TCS 103 (1): 25-38 (1992) 23 Jin-yi Cai: Computations Over Infinite Groups. FCT 1991 : 22-32 22 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 21 Jin-yi Cai, Lane A. Hemachandra : A Note on Enumarative Counting. Information Processing Letters 38 (4): 215-219 (1991) 20 Jin-yi Cai, Merrick L. Furst : PSPACE Survives Constant-Width Bottlenecks. International Journal of Foundations of Computer Science 2 (1): 67-76 (1991) 19 Jin-yi Cai, Anne Condon , Richard J. Lipton : Playing Games of Incomplete Information. STACS 1990 : 58-69 18 Jin-yi Cai, Anne Condon , Richard J. Lipton : On Bounded Round Multi-Prover Interactive Proof Systems. Structure in Complexity Theory Conference 1990 : 45-54 17 Jin-yi Cai: Lower Bounds for Constant-Depth Circuits in the Presence of Help Bits. Information Processing Letters 36 (2): 79-83 (1990) 16 Jin-yi Cai: A Note on the Determinant and Permanent Problem. Information and Computation 84 (1): 119-127 (1990) 15 Jin-yi Cai, Lane A. Hemachandra : On the Power of Parity Polynomial Time. Mathematical Systems Theory 23 (2): 95-106 (1990) 14 Jin-yi Cai: Lower Bounds for Constant Depth Circuits in the Presence of Help Bits. FOCS 1989 : 532-537 13 Jin-yi Cai, Richard J. Lipton : Subquadratic Simulations of Circuits by Branching Programs. FOCS 1989 : 568-573 12 Jin-yi Cai, Martin Fürer , Neil Immerman : An Optimal Lower Bound on the Number of Variables for Graph Identification. FOCS 1989 : 612-617 11 Jin-yi Cai, Lane A. Hemachandra : On the Power of Parity Polynomial Time. STACS 1989 : 229-239 10 Jin-yi Cai, Juris Hartmanis : The Complexity Of The Real Line Is A Fractal. Structure in Complexity Theory Conference 1989 : 138-146 9 Jin-yi Cai, Lane A. Hemachandra : Enumerative Counting Is Hard. Information and Computation 82 (1): 34-44 (1989) 8 Jin-yi Cai: With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy. JCSS 38 (1): 68-85 (1989) 7 Jin-yi Cai, Thomas Gundermann , Juris Hartmanis , Lane A. Hemachandra , Vivan Sewelson , Klaus W. Wagner , Gerd Wechsung : The Boolean Hierarchy II: Applications. SIAM J. Comput. 18 (1): 95-111 (1989) 6 Sandeep N. Bhatt , Jin-yi Cai: Take a Walk, Grow a Tree (Preliminary Version). FOCS 1988 : 469-478 5 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) 4 Jin-yi Cai, Gabriele E. Meyer : On the Complexity of Graph Critical Uncolorability. ICALP 1987 : 394-403 3 Jin-yi Cai: Probability One Separation of the Boolean Hierarchy. STACS 1987 : 148-158 2 Jin-yi Cai, Gabriele E. Meyer : Graph Minimal Uncolorability is D^P-Complete. SIAM J. Comput. 16 (2): 259-277 (1987) 1 Jin-yi Cai: With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy. STOC 1986 : 21-29  DiSC'02 © 2003 Association for Computing Machinery |
