The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Jin-yi Cai: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

  1. Jin-yi Cai, Martin Fürer, Neil Immerman
    An Optimal Lower Bound on the Number of Variables for Graph Identification [Citation Graph (5, 0)][DBLP]
    FOCS, 1989, pp:612-617 [Conf]
  2. Jin-yi Cai
    Lower Bounds for Constant-Depth Circuits in the Presence of Help Bits. [Citation Graph (2, 0)][DBLP]
    Inf. Process. Lett., 1990, v:36, n:2, pp:79-83 [Journal]
  3. Jin-yi Cai
    The Complexity of Some Lattice Problems. [Citation Graph (0, 0)][DBLP]
    ANTS, 2000, pp:1-32 [Conf]
  4. Jin-yi Cai
    Some Recent Progress on the Complexity of Lattice Problems. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 1999, pp:158-0 [Conf]
  5. Jin-yi Cai
    Applications of a New Transference Theorem to Ajtai's Connection Factor. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 1999, pp:205-214 [Conf]
  6. Jin-yi Cai
    With Probability One, A Random Oracle Separates PSPACE from the Polynomial- Time Hierarchy. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1986, pp:104-104 [Conf]
  7. Jin-yi Cai, Anne Condon, Richard J. Lipton
    On Bounded Round Multi-Prover Interactive Proof Systems. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1990, pp:45-54 [Conf]
  8. Jin-yi Cai, Anne Condon, Richard J. Lipton
    PSPACE Is Provable By Two Provers In One Round. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1991, pp:110-115 [Conf]
  9. Jin-yi Cai, Lane A. Hemachandra
    The Boolean Hierarchy: Hardware over NP. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1986, pp:105-124 [Conf]
  10. Jin-yi Cai, Juris Hartmanis
    The Complexity Of The Real Line Is A Fractal. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1989, pp:138-146 [Conf]
  11. Jin-yi Cai, Richard J. Lipton, Robert Sedgewick, Andrew Chi-Chih Yao
    Towards Uncheatable benchmarks. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1993, pp:2-11 [Conf]
  12. Jin-yi Cai, Ajay Nerurkar
    Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 1998, pp:46-0 [Conf]
  13. Jin-yi Cai
    A New Transference Theorem in the Geometry of Numbers. [Citation Graph (0, 0)][DBLP]
    COCOON, 1999, pp:113-122 [Conf]
  14. Jin-yi Cai, Eric Bach
    On Testing for Zero Polynomials by a Set of Points with Bounded Precision. [Citation Graph (0, 0)][DBLP]
    COCOON, 2001, pp:473-482 [Conf]
  15. Jin-yi Cai, Venkatesan T. Chakaravarthy
    A Note on Zero Error Algorithms Having Oracle Access to One NP Query. [Citation Graph (0, 0)][DBLP]
    COCOON, 2005, pp:339-348 [Conf]
  16. Pu Cai, Jin-yi Cai
    On the 100% Rule of Sensivity Analzsis in Linear Programming. [Citation Graph (0, 0)][DBLP]
    COCOON, 1997, pp:460-469 [Conf]
  17. Jin-yi Cai, Denis Charles, Aduri Pavan, Samik Sengupta
    On Higher Arthur-Merlin Classes. [Citation Graph (0, 0)][DBLP]
    COCOON, 2002, pp:18-27 [Conf]
  18. Jin-yi Cai, George Havas, Bernard Mans, Ajay Nerurkar, Jean-Pierre Seifert, Igor Shparlinski
    On Routing in Circulant Graphs. [Citation Graph (0, 0)][DBLP]
    COCOON, 1999, pp:360-369 [Conf]
  19. Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung
    Robust Reductions. [Citation Graph (0, 0)][DBLP]
    COCOON, 1998, pp:174-183 [Conf]
  20. Jin-yi Cai, D. Sivakumar
    Resolution of Hartmanis' Conjecture for NL-Hard Sparse Sets. [Citation Graph (0, 0)][DBLP]
    COCOON, 1997, pp:62-71 [Conf]
  21. Jin-yi Cai, Osamu Watanabe
    On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results. [Citation Graph (0, 0)][DBLP]
    COCOON, 2003, pp:202-211 [Conf]
  22. Jin-yi Cai, Lane A. Hemachandra, Jozef Vyskoc
    Promise Problems and Guarded Access to Unambiguous Computation. [Citation Graph (0, 0)][DBLP]
    Complexity Theory: Current Research, 1992, pp:101-146 [Conf]
  23. Jin-yi Cai
    Computations Over Infinite Groups. [Citation Graph (0, 0)][DBLP]
    FCT, 1991, pp:22-32 [Conf]
  24. Jin-yi Cai
    On the Average-Case Hardness of CVP. [Citation Graph (0, 0)][DBLP]
    FOCS, 2001, pp:308-317 [Conf]
  25. Jin-yi Cai
    Lower Bounds for Constant Depth Circuits in the Presence of Help Bits [Citation Graph (0, 0)][DBLP]
    FOCS, 1989, pp:532-537 [Conf]
  26. Sandeep N. Bhatt, Jin-yi Cai
    Take a Walk, Grow a Tree (Preliminary Version) [Citation Graph (0, 0)][DBLP]
    FOCS, 1988, pp:469-478 [Conf]
  27. Jin-yi Cai
    Sp2 subseteq ZPPNP. [Citation Graph (0, 0)][DBLP]
    FOCS, 2001, pp:620-629 [Conf]
  28. Jin-yi Cai, Wolfgang H. J. Fuchs, Dexter Kozen, Zicheng Liu
    Efficient Average-Case Algorithms for the Modular Group [Citation Graph (0, 0)][DBLP]
    FOCS, 1994, pp:143-152 [Conf]
  29. Jin-yi Cai, Richard J. Lipton
    Subquadratic Simulations of Circuits by Branching Programs [Citation Graph (0, 0)][DBLP]
    FOCS, 1989, pp:568-573 [Conf]
  30. Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein
    The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices [Citation Graph (0, 0)][DBLP]
    FOCS, 1994, pp:135-142 [Conf]
  31. Jin-yi Cai, Ajay Nerurkar
    An Improved Worst-Case to Average-Case Connection for Lattice Problems. [Citation Graph (0, 0)][DBLP]
    FOCS, 1997, pp:468-477 [Conf]
  32. Jin-yi Cai, D. Sivakumar
    The Resolution of a Hartmanis Conjecture. [Citation Graph (0, 0)][DBLP]
    FOCS, 1995, pp:362-371 [Conf]
  33. Jin-yi Cai, D. Sivakumar, Martin Strauss
    Constant Depth Circuits and the Lutz Hypothesis. [Citation Graph (0, 0)][DBLP]
    FOCS, 1997, pp:595-604 [Conf]
  34. Kenneth W. Regan, D. Sivakumar, Jin-yi Cai
    Pseudorandom Generators, Measure Theory, and Natural Proofs. [Citation Graph (0, 0)][DBLP]
    FOCS, 1995, pp:26-35 [Conf]
  35. Jin-yi Cai, Osamu Watanabe
    Stringent Relativization. [Citation Graph (0, 0)][DBLP]
    FSTTCS, 2003, pp:408-419 [Conf]
  36. Jin-yi Cai, Vinay Choudhary
    Some Results on Matchgates and Holographic Algorithms. [Citation Graph (0, 0)][DBLP]
    ICALP (1), 2006, pp:703-714 [Conf]
  37. Jin-yi Cai, Gabriele E. Meyer
    On the Complexity of Graph Critical Uncolorability. [Citation Graph (0, 0)][DBLP]
    ICALP, 1987, pp:394-403 [Conf]
  38. Yuan Wang, David J. DeWitt, Jin-yi Cai
    X-Diff: An Effective Change Detection Algorithm for XML Documents. [Citation Graph (0, 0)][DBLP]
    ICDE, 2003, pp:519-530 [Conf]
  39. Zheng Huang, Lei Chen 0003, Jin-yi Cai, Deborah S. Gross, David R. Musicant, Raghu Ramakrishnan, James J. Schauer, Stephen J. Wright
    Mass Spectrum Labeling: Theory and Practice. [Citation Graph (0, 0)][DBLP]
    ICDM, 2004, pp:122-129 [Conf]
  40. Micah Adler, Jin-yi Cai, Jonathan K. Shapiro, Donald F. Towsley
    Estimation of Congestion Price Using Probabilistic Packet Marking. [Citation Graph (0, 0)][DBLP]
    INFOCOM, 2003, pp:- [Conf]
  41. Jin-yi Cai
    Essentially Every Unimodular Matrix Defines and Expander. [Citation Graph (0, 0)][DBLP]
    ISAAC, 2000, pp:2-22 [Conf]
  42. Jin-yi Cai
    On the Minimum Volume of a Perturbed Unit Cube. [Citation Graph (0, 0)][DBLP]
    ISAAC, 2002, pp:67-78 [Conf]
  43. Jin-yi Cai, Michael D. Hirsch
    Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic Geometry. [Citation Graph (0, 0)][DBLP]
    ISAAC, 1994, pp:172-180 [Conf]
  44. Jin-yi Cai, Osamu Watanabe
    Random Access to Advice Strings and Collapsing Results. [Citation Graph (0, 0)][DBLP]
    ISAAC, 2004, pp:209-220 [Conf]
  45. Pinyan Lu, Jialin Zhang, Chung Keung Poon, Jin-yi Cai
    Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs. [Citation Graph (0, 0)][DBLP]
    ISAAC, 2005, pp:767-776 [Conf]
  46. Jin-yi Cai, Lane A. Hemachandra, Jozef Vyskoc
    Promise Problems and Access to Unambiguous Computation. [Citation Graph (0, 0)][DBLP]
    MFCS, 1992, pp:162-171 [Conf]
  47. Jin-yi Cai, Venkatesan T. Chakaravarthy, Raghav Kaushik, Jeffrey F. Naughton
    On the Complexity of Join Predicates. [Citation Graph (0, 0)][DBLP]
    PODS, 2001, pp:- [Conf]
  48. Jin-yi Cai, Thomas W. Cusick
    A Lattice-Based Public-Key Cryptosystem. [Citation Graph (0, 0)][DBLP]
    Selected Areas in Cryptography, 1998, pp:219-233 [Conf]
  49. Sigal Ar, Jin-yi Cai
    Reliable Benchmarks Using Numerical Instability. [Citation Graph (0, 0)][DBLP]
    SODA, 1994, pp:34-43 [Conf]
  50. László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, Eugene M. Luks
    Multiplicative Equations over Commuting Matrices. [Citation Graph (0, 0)][DBLP]
    SODA, 1996, pp:498-507 [Conf]
  51. Jin-yi Cai
    Probability One Separation of the Boolean Hierarchy. [Citation Graph (0, 0)][DBLP]
    STACS, 1987, pp:148-158 [Conf]
  52. Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara
    Competing Provers Yield Improved Karp-Lipton Collapse Results. [Citation Graph (0, 0)][DBLP]
    STACS, 2003, pp:535-546 [Conf]
  53. Jin-yi Cai, Anne Condon, Richard J. Lipton
    Playing Games of Incomplete Information. [Citation Graph (0, 0)][DBLP]
    STACS, 1990, pp:58-69 [Conf]
  54. Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek
    Time-Space Tradeoff in Derandomizing Probabilistic Logspace. [Citation Graph (0, 0)][DBLP]
    STACS, 2004, pp:571-583 [Conf]
  55. Jin-yi Cai, Lane A. Hemachandra
    On the Power of Parity Polynomial Time. [Citation Graph (0, 0)][DBLP]
    STACS, 1989, pp:229-239 [Conf]
  56. Jin-yi Cai, Richard J. Lipton, Luc Longpré, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar
    Communication Complexity of Key Agreement on Small Ranges. [Citation Graph (0, 0)][DBLP]
    STACS, 1995, pp:38-49 [Conf]
  57. Jin-yi Cai, Ashish V. Naik, D. Sivakumar
    On the Existence of Hard Sparse Sets under Weak Reductions. [Citation Graph (0, 0)][DBLP]
    STACS, 1996, pp:307-318 [Conf]
  58. Jin-yi Cai, Aduri Pavan, D. Sivakumar
    On the Hardness of Permanent. [Citation Graph (0, 0)][DBLP]
    STACS, 1999, pp:90-99 [Conf]
  59. Jin-yi Cai, Alan L. Selman
    Fine Separation of Average Time Complexity Classes. [Citation Graph (0, 0)][DBLP]
    STACS, 1996, pp:331-343 [Conf]
  60. Jin-yi Cai, Pinyan Lu
    On Symmetric Signatures in Holographic Algorithms. [Citation Graph (0, 0)][DBLP]
    STACS, 2007, pp:429-440 [Conf]
  61. Jin-yi Cai
    With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy [Citation Graph (0, 0)][DBLP]
    STOC, 1986, pp:21-29 [Conf]
  62. Jin-yi Cai
    Parallel Computation Over Hyperbolic Groups [Citation Graph (0, 0)][DBLP]
    STOC, 1992, pp:106-115 [Conf]
  63. Jin-yi Cai, Ajay Nerurkar, D. Sivakumar
    Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. [Citation Graph (0, 0)][DBLP]
    STOC, 1999, pp:726-735 [Conf]
  64. Valentine Kabanets, Jin-yi Cai
    Circuit minimization problem. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:73-79 [Conf]
  65. Jin-yi Cai, Vinay Choudhary
    Valiant's Holant Theorem and Matchgate Tensors. [Citation Graph (0, 0)][DBLP]
    TAMC, 2006, pp:248-261 [Conf]
  66. Jin-yi Cai, C. K. Wong
    Foreword. [Citation Graph (0, 0)][DBLP]
    Algorithmica, 1999, v:23, n:4, pp:277- [Journal]
  67. Jin-yi Cai, Osamu Watanabe
    Random Access to Advice Strings and Collapsing Results. [Citation Graph (0, 0)][DBLP]
    Algorithmica, 2006, v:46, n:1, pp:43-57 [Journal]
  68. Jin-yi Cai, Martin Fürer, Neil Immerman
    An optimal lower bound on the number of variables for graph identifications. [Citation Graph (0, 0)][DBLP]
    Combinatorica, 1992, v:12, n:4, pp:389-410 [Journal]
  69. Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung
    Robust Reductions [Citation Graph (0, 0)][DBLP]
    CoRR, 1999, v:0, n:, pp:- [Journal]
  70. Jin-yi Cai
    A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor. [Citation Graph (0, 0)][DBLP]
    Discrete Applied Mathematics, 2003, v:126, n:1, pp:9-31 [Journal]
  71. Jin-yi Cai
    Essentially every unimodular matrix defines an expander [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:8, n:1, pp:- [Journal]
  72. Jin-yi Cai
    S_2p \subseteq ZPPNP [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:8, n:30, pp:- [Journal]
  73. Jin-yi Cai, Vinay Choudhary
    Valiant's Holant Theorem and Matchgate Tensors [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:118, pp:- [Journal]
  74. Jin-yi Cai, Vinay Choudhary
    On the Theory of Matchgate Computations [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2006, v:, n:018, pp:- [Journal]
  75. Jin-yi Cai, Wolfgang H. J. Fuchs, Dexter Kozen, Zicheng Liu
    Efficient Average-Case Algorithms for the Modular Group [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1994, v:1, n:16, pp:- [Journal]
  76. Kenneth W. Regan, D. Sivakumar, Jin-yi Cai
    Pseudorandom Generators, Measure Theory, and Natural Proofs [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1995, v:2, n:6, pp:- [Journal]
  77. Jin-yi Cai
    A new transference theorem and applications to Ajtai's connection factor [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:5, pp:- [Journal]
  78. Jin-yi Cai
    Some Recent Progress on the Complexity of Lattice Problems [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1999, v:6, n:6, pp:- [Journal]
  79. Valentine Kabanets, Jin-yi Cai
    Circuit Minimization Problem [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1999, v:, n:45, pp:- [Journal]
  80. Jin-yi Cai
    A Note on the Determinant and Permanent Problem [Citation Graph (0, 0)][DBLP]
    Inf. Comput., 1990, v:84, n:1, pp:119-127 [Journal]
  81. Jin-yi Cai, Thomas W. Cusick
    A Lattice-Based Public-Key Cryptosystem. [Citation Graph (0, 0)][DBLP]
    Inf. Comput., 1999, v:151, n:1-2, pp:17-31 [Journal]
  82. Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara
    Competing provers yield improved Karp-Lipton collapse results. [Citation Graph (0, 0)][DBLP]
    Inf. Comput., 2005, v:198, n:1, pp:1-23 [Journal]
  83. Jin-yi Cai, Lane A. Hemachandra
    Enumerative Counting Is Hard [Citation Graph (0, 0)][DBLP]
    Inf. Comput., 1989, v:82, n:1, pp:34-44 [Journal]
  84. Jin-yi Cai
    Computing Jordan Normal Forms Exactly for Commuting Matrices in Polynomial Time. [Citation Graph (0, 0)][DBLP]
    Int. J. Found. Comput. Sci., 1994, v:5, n:3/4, pp:293-302 [Journal]
  85. Jin-yi Cai, Denis Charles, Aduri Pavan, Samik Sengupta
    On Higher Arthur-Merlin Classes. [Citation Graph (0, 0)][DBLP]
    Int. J. Found. Comput. Sci., 2004, v:15, n:1, pp:3-19 [Journal]
  86. Jin-yi Cai, Merrick L. Furst
    PSPACE Survives Constant-Width Bottlenecks. [Citation Graph (0, 0)][DBLP]
    Int. J. Found. Comput. Sci., 1991, v:2, n:1, pp:67-76 [Journal]
  87. Jin-yi Cai
    A Classification of the Probabilistic Polynomial Time Hierarchy Under Fault Tolerant Access to Oracle Classes. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 1999, v:69, n:4, pp:167-174 [Journal]
  88. Jin-yi Cai, Lane A. Hemachandra
    A Note on Enumarative Counting. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 1991, v:38, n:4, pp:215-219 [Journal]
  89. Jin-yi Cai, Ajay Nerurkar
    A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 2000, v:76, n:1-2, pp:61-66 [Journal]
  90. Jin-yi Cai, Robert A. Threlfall
    A note on quadratic residuosity and UP. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 2004, v:92, n:3, pp:127-131 [Journal]
  91. Jin-yi Cai, Osamu Watanabe
    Relativized collapsing between BPP and PH under stringent oracle access. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 2004, v:90, n:3, pp:147-154 [Journal]
  92. Sandeep N. Bhatt, Jin-yi Cai
    Taking Random Walks to Grow Trees in Hypercubes. [Citation Graph (0, 0)][DBLP]
    J. ACM, 1993, v:40, n:3, pp:741-764 [Journal]
  93. Jin-yi Cai, Pu Cai, Yixin Zhu
    On A Scheduling Problem of Time Deteriorating Jobs. [Citation Graph (0, 0)][DBLP]
    J. Complexity, 1998, v:14, n:2, pp:190-209 [Journal]
  94. Pu Cai, Jin-yi Cai, Ashish V. Naik
    Efficient Algorithms for a Scheduling Problem and its Applications to Illicit Drug Market Crackdowns. [Citation Graph (0, 0)][DBLP]
    J. Comb. Optim., 1998, v:1, n:4, pp:367-376 [Journal]
  95. Jin-yi Cai, Venkatesan T. Chakaravarthy
    On zero error algorithms having oracle access to one query. [Citation Graph (0, 0)][DBLP]
    J. Comb. Optim., 2006, v:11, n:2, pp:189-202 [Journal]
  96. Jin-yi Cai
    With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1989, v:38, n:1, pp:68-85 [Journal]
  97. Jin-yi Cai, Anne Condon, Richard J. Lipton
    PSPACE Is Provable by Two Provers in One Round. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1994, v:48, n:1, pp:183-193 [Journal]
  98. Jin-yi Cai, Juris Hartmanis
    On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1994, v:49, n:3, pp:605-619 [Journal]
  99. Jin-yi Cai, Ajay Nerurkar
    Approximating the SVP to within a Factor (1+1/dimxi) Is NP-Hard under Randomized Reductions. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1999, v:59, n:2, pp:221-239 [Journal]
  100. Jin-yi Cai, D. Sivakumar
    Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1999, v:58, n:2, pp:280-296 [Journal]
  101. Jin-yi Cai
    S2p is subset of ZPPNP. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 2007, v:73, n:1, pp:25-35 [Journal]
  102. Jin-yi Cai, Hong Zhu
    Progress in Computational Complexity Theory. [Citation Graph (0, 0)][DBLP]
    J. Comput. Sci. Technol., 2005, v:20, n:6, pp:735-750 [Journal]
  103. Jin-yi Cai
    Essentially Every Unimodular Matrix Defines an Expander. [Citation Graph (0, 0)][DBLP]
    Theory Comput. Syst., 2003, v:36, n:2, pp:105-135 [Journal]
  104. Jin-yi Cai
    Frobenius's Degree Formula and Toda's Polynomials. [Citation Graph (0, 0)][DBLP]
    Theory Comput. Syst., 1998, v:31, n:1, pp:67-75 [Journal]
  105. Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek
    Time-Space Tradeoff in Derandomizing Probabilistic Logspace. [Citation Graph (0, 0)][DBLP]
    Theory Comput. Syst., 2006, v:39, n:1, pp:189-208 [Journal]
  106. Jin-yi Cai, Frederic Green, Thomas Thierauf
    On the Correlation of Symmetric Functions. [Citation Graph (0, 0)][DBLP]
    Mathematical Systems Theory, 1996, v:29, n:3, pp:245-258 [Journal]
  107. Jin-yi Cai, Lane A. Hemachandra
    On the Power of Parity Polynomial Time. [Citation Graph (0, 0)][DBLP]
    Mathematical Systems Theory, 1990, v:23, n:2, pp:95-106 [Journal]
  108. Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung
    Robust Reductions. [Citation Graph (0, 0)][DBLP]
    Theory Comput. Syst., 1999, v:32, n:6, pp:625-647 [Journal]
  109. Jin-yi Cai, Zicheng Liu
    The Bounded Membership Problem of the Monoid SL_2(N). [Citation Graph (0, 0)][DBLP]
    Mathematical Systems Theory, 1996, v:29, n:6, pp:573-587 [Journal]
  110. Jin-yi Cai, Suresh Chari
    On the Impossibility of Amplifying the Independence of Random Variables. [Citation Graph (0, 0)][DBLP]
    Random Struct. Algorithms, 1995, v:7, n:4, pp:301-310 [Journal]
  111. Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung
    The Boolean Hierarchy I: Structural Properties. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1988, v:17, n:6, pp:1232-1252 [Journal]
  112. Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung
    The Boolean Hierarchy II: Applications. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1989, v:18, n:1, pp:95-111 [Journal]
  113. Jin-yi Cai, Richard J. Lipton
    Subquadratic Simulations of Balanced Formulae by Branching Programs. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1994, v:23, n:3, pp:563-572 [Journal]
  114. Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein
    The Complexity of the A B C Problem. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2000, v:29, n:6, pp:1878-1888 [Journal]
  115. Jin-yi Cai, Gabriele E. Meyer
    Graph Minimal Uncolorability is D^P-Complete. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1987, v:16, n:2, pp:259-277 [Journal]
  116. Jin-yi Cai, Alan L. Selman
    Fine Separation of Average-Time Complexity Classes. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1999, v:28, n:4, pp:1310-1325 [Journal]
  117. Jin-yi Cai, Osamu Watanabe
    On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2004, v:33, n:4, pp:984-1009 [Journal]
  118. Jin-yi Cai, Eric Bach
    On testing for zero polynomials by a set of points with bounded precision. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2003, v:296, n:1, pp:15-25 [Journal]
  119. Jin-yi Cai
    A Relation of Primal-Dual Lattices and the Complexity of Shortest Lattice Vector Problem. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1998, v:207, n:1, pp:105-116 [Journal]
  120. Jin-yi Cai, Anne Condon, Richard J. Lipton
    On Games of Incomplete Information. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1992, v:103, n:1, pp:25-38 [Journal]
  121. Jin-yi Cai, D. Sivakumar
    Resolution of Hartmanis' conjecture for NL-hard sparse sets. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2000, v:240, n:2, pp:257-269 [Journal]
  122. Jin-yi Cai, Pinyan Lu
    Bases Collapse in Holographic Algorithms. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2007, pp:292-304 [Conf]
  123. Jin-yi Cai, Vinay Choudhary, Pinyan Lu
    On the Theory of Matchgate Computations. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2007, pp:305-318 [Conf]
  124. Eric Bach, Jin-yi Cai
    A Novel Information Transmission Problem and Its Optimal Solution. [Citation Graph (0, 0)][DBLP]
    FCT, 2007, pp:64-75 [Conf]
  125. Jin-yi Cai, Pinyan Lu
    On Block-Wise Symmetric Signatures for Matchgates. [Citation Graph (0, 0)][DBLP]
    FCT, 2007, pp:187-198 [Conf]
  126. Jin-yi Cai, Pinyan Lu
    Holographic Algorithms: The Power of Dimensionality Resolved. [Citation Graph (0, 0)][DBLP]
    ICALP, 2007, pp:631-642 [Conf]
  127. Byron J. Gao, Martin Ester, Jin-yi Cai, Oliver Schulte, Hui Xiong
    The minimum consistent subset cover problem and its applications in data mining. [Citation Graph (0, 0)][DBLP]
    KDD, 2007, pp:310-319 [Conf]
  128. Jin-yi Cai, Pinyan Lu
    Holographic algorithms: from art to science. [Citation Graph (0, 0)][DBLP]
    STOC, 2007, pp:401-410 [Conf]
  129. Jin-yi Cai, Vinay Choudhary
    Valiant's Holant Theorem and matchgate tensors. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2007, v:384, n:1, pp:22-32 [Journal]

  130. An Attacker-Defender Game for Honeynets. [Citation Graph (, )][DBLP]


  131. Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. [Citation Graph (, )][DBLP]


  132. Graph Homomorphisms with Complex Values: A Dichotomy Theorem. [Citation Graph (, )][DBLP]


  133. Signature Theory in Holographic Algorithms. [Citation Graph (, )][DBLP]


  134. Holographic algorithms with unsymmetric signatures. [Citation Graph (, )][DBLP]


  135. Holant Problems for Regular Graphs with Complex Edge Functions. [Citation Graph (, )][DBLP]


  136. A quadratic lower bound for the permanent and determinant problem over any characteristic != 2. [Citation Graph (, )][DBLP]


  137. Holant problems and counting CSP. [Citation Graph (, )][DBLP]


  138. A Computational Proof of Complexity of Some Restricted Counting Problems. [Citation Graph (, )][DBLP]


  139. Approximation and Hardness Results for Label Cut and Related Problems. [Citation Graph (, )][DBLP]


  140. A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions. [Citation Graph (, )][DBLP]


  141. On Tractable Exponential Sums. [Citation Graph (, )][DBLP]


  142. Basis Collapse in Holographic Algorithms. [Citation Graph (, )][DBLP]


  143. Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic. [Citation Graph (, )][DBLP]


  144. A Family of Counter Examples to an Approach to Graph Isomorphism [Citation Graph (, )][DBLP]


  145. Graph Homomorphisms with Complex Values: A Dichotomy Theorem [Citation Graph (, )][DBLP]


  146. Holant Problems for Regular Graphs with Complex Edge Functions [Citation Graph (, )][DBLP]


  147. From Holant To #CSP And Back: Dichotomy For Holant$^c$ Problems [Citation Graph (, )][DBLP]


  148. On Tractable Exponential Sums [Citation Graph (, )][DBLP]


  149. Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP [Citation Graph (, )][DBLP]


  150. A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights [Citation Graph (, )][DBLP]


  151. On Block-wise Symmetric Signatures for Matchgates. [Citation Graph (, )][DBLP]


  152. Holographic Algorithms: The Power of Dimensionality Resolved. [Citation Graph (, )][DBLP]


  153. Bases Collapse in Holographic Algorithms. [Citation Graph (, )][DBLP]


  154. On Symmetric Signatures in Holographic Algorithms. [Citation Graph (, )][DBLP]


  155. Some Results on Matchgates and Holographic Algorithms. [Citation Graph (, )][DBLP]


  156. Holographic Algorithms: From Art to Science. [Citation Graph (, )][DBLP]


Search in 0.026secs, Finished in 0.033secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002