Search the dblp DataBase
Jin-yi Cai :
[Publications ]
[Author Rank by year ]
[Co-authors ]
[Prefers ]
[Cites ]
[Cited by ]
Publications of Author
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 ] 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 ] Jin-yi Cai The Complexity of Some Lattice Problems. [Citation Graph (0, 0)][DBLP ] ANTS, 2000, pp:1-32 [Conf ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] Jin-yi Cai A New Transference Theorem in the Geometry of Numbers. [Citation Graph (0, 0)][DBLP ] COCOON, 1999, pp:113-122 [Conf ] 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 ] 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 ] 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 ] 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 ] 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 ] Jin-yi Cai , Lane A. Hemaspaandra , Gerd Wechsung Robust Reductions. [Citation Graph (0, 0)][DBLP ] COCOON, 1998, pp:174-183 [Conf ] 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 ] 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 ] 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 ] Jin-yi Cai Computations Over Infinite Groups. [Citation Graph (0, 0)][DBLP ] FCT, 1991, pp:22-32 [Conf ] Jin-yi Cai On the Average-Case Hardness of CVP. [Citation Graph (0, 0)][DBLP ] FOCS, 2001, pp:308-317 [Conf ] 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 ] 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 ] Jin-yi Cai Sp 2 subseteq ZPPNP . [Citation Graph (0, 0)][DBLP ] FOCS, 2001, pp:620-629 [Conf ] 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 ] Jin-yi Cai , Richard J. Lipton Subquadratic Simulations of Circuits by Branching Programs [Citation Graph (0, 0)][DBLP ] FOCS, 1989, pp:568-573 [Conf ] 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 ] 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 ] Jin-yi Cai , D. Sivakumar The Resolution of a Hartmanis Conjecture. [Citation Graph (0, 0)][DBLP ] FOCS, 1995, pp:362-371 [Conf ] 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 ] 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 ] Jin-yi Cai , Osamu Watanabe Stringent Relativization. [Citation Graph (0, 0)][DBLP ] FSTTCS, 2003, pp:408-419 [Conf ] Jin-yi Cai , Vinay Choudhary Some Results on Matchgates and Holographic Algorithms. [Citation Graph (0, 0)][DBLP ] ICALP (1), 2006, pp:703-714 [Conf ] Jin-yi Cai , Gabriele E. Meyer On the Complexity of Graph Critical Uncolorability. [Citation Graph (0, 0)][DBLP ] ICALP, 1987, pp:394-403 [Conf ] 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 ] 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 ] 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 ] Jin-yi Cai Essentially Every Unimodular Matrix Defines and Expander. [Citation Graph (0, 0)][DBLP ] ISAAC, 2000, pp:2-22 [Conf ] Jin-yi Cai On the Minimum Volume of a Perturbed Unit Cube. [Citation Graph (0, 0)][DBLP ] ISAAC, 2002, pp:67-78 [Conf ] 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 ] Jin-yi Cai , Osamu Watanabe Random Access to Advice Strings and Collapsing Results. [Citation Graph (0, 0)][DBLP ] ISAAC, 2004, pp:209-220 [Conf ] 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 ] 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 ] 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 ] 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 ] Sigal Ar , Jin-yi Cai Reliable Benchmarks Using Numerical Instability. [Citation Graph (0, 0)][DBLP ] SODA, 1994, pp:34-43 [Conf ] 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 ] Jin-yi Cai Probability One Separation of the Boolean Hierarchy. [Citation Graph (0, 0)][DBLP ] STACS, 1987, pp:148-158 [Conf ] 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 ] Jin-yi Cai , Anne Condon , Richard J. Lipton Playing Games of Incomplete Information. [Citation Graph (0, 0)][DBLP ] STACS, 1990, pp:58-69 [Conf ] 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 ] Jin-yi Cai , Lane A. Hemachandra On the Power of Parity Polynomial Time. [Citation Graph (0, 0)][DBLP ] STACS, 1989, pp:229-239 [Conf ] 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 ] 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 ] Jin-yi Cai , Aduri Pavan , D. Sivakumar On the Hardness of Permanent. [Citation Graph (0, 0)][DBLP ] STACS, 1999, pp:90-99 [Conf ] Jin-yi Cai , Alan L. Selman Fine Separation of Average Time Complexity Classes. [Citation Graph (0, 0)][DBLP ] STACS, 1996, pp:331-343 [Conf ] Jin-yi Cai , Pinyan Lu On Symmetric Signatures in Holographic Algorithms. [Citation Graph (0, 0)][DBLP ] STACS, 2007, pp:429-440 [Conf ] 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 ] Jin-yi Cai Parallel Computation Over Hyperbolic Groups [Citation Graph (0, 0)][DBLP ] STOC, 1992, pp:106-115 [Conf ] 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 ] Valentine Kabanets , Jin-yi Cai Circuit minimization problem. [Citation Graph (0, 0)][DBLP ] STOC, 2000, pp:73-79 [Conf ] Jin-yi Cai , Vinay Choudhary Valiant's Holant Theorem and Matchgate Tensors. [Citation Graph (0, 0)][DBLP ] TAMC, 2006, pp:248-261 [Conf ] Jin-yi Cai , C. K. Wong Foreword. [Citation Graph (0, 0)][DBLP ] Algorithmica, 1999, v:23, n:4, pp:277- [Journal ] 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 ] 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 ] Jin-yi Cai , Lane A. Hemaspaandra , Gerd Wechsung Robust Reductions [Citation Graph (0, 0)][DBLP ] CoRR, 1999, v:0, n:, pp:- [Journal ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] Jin-yi Cai S2 p is subset of ZPPNP . [Citation Graph (0, 0)][DBLP ] J. Comput. Syst. Sci., 2007, v:73, n:1, pp:25-35 [Journal ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] 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 ] Jin-yi Cai , Pinyan Lu On Block-Wise Symmetric Signatures for Matchgates. [Citation Graph (0, 0)][DBLP ] FCT, 2007, pp:187-198 [Conf ] Jin-yi Cai , Pinyan Lu Holographic Algorithms: The Power of Dimensionality Resolved. [Citation Graph (0, 0)][DBLP ] ICALP, 2007, pp:631-642 [Conf ] 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 ] Jin-yi Cai , Pinyan Lu Holographic algorithms: from art to science. [Citation Graph (0, 0)][DBLP ] STOC, 2007, pp:401-410 [Conf ] 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 ] An Attacker-Defender Game for Honeynets. [Citation Graph (, )][DBLP ] Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. [Citation Graph (, )][DBLP ] Graph Homomorphisms with Complex Values: A Dichotomy Theorem. [Citation Graph (, )][DBLP ] Signature Theory in Holographic Algorithms. [Citation Graph (, )][DBLP ] Holographic algorithms with unsymmetric signatures. [Citation Graph (, )][DBLP ] Holant Problems for Regular Graphs with Complex Edge Functions. [Citation Graph (, )][DBLP ] A quadratic lower bound for the permanent and determinant problem over any characteristic != 2. [Citation Graph (, )][DBLP ] Holant problems and counting CSP. [Citation Graph (, )][DBLP ] A Computational Proof of Complexity of Some Restricted Counting Problems. [Citation Graph (, )][DBLP ] Approximation and Hardness Results for Label Cut and Related Problems. [Citation Graph (, )][DBLP ] A Dichotomy for k -Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions. [Citation Graph (, )][DBLP ] On Tractable Exponential Sums. [Citation Graph (, )][DBLP ] Basis Collapse in Holographic Algorithms. [Citation Graph (, )][DBLP ] Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic. [Citation Graph (, )][DBLP ] A Family of Counter Examples to an Approach to Graph Isomorphism [Citation Graph (, )][DBLP ] Graph Homomorphisms with Complex Values: A Dichotomy Theorem [Citation Graph (, )][DBLP ] Holant Problems for Regular Graphs with Complex Edge Functions [Citation Graph (, )][DBLP ] From Holant To #CSP And Back: Dichotomy For Holant$^c$ Problems [Citation Graph (, )][DBLP ] On Tractable Exponential Sums [Citation Graph (, )][DBLP ] Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP [Citation Graph (, )][DBLP ] A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights [Citation Graph (, )][DBLP ] On Block-wise Symmetric Signatures for Matchgates. [Citation Graph (, )][DBLP ] Holographic Algorithms: The Power of Dimensionality Resolved. [Citation Graph (, )][DBLP ] Bases Collapse in Holographic Algorithms. [Citation Graph (, )][DBLP ] On Symmetric Signatures in Holographic Algorithms. [Citation Graph (, )][DBLP ] Some Results on Matchgates and Holographic Algorithms. [Citation Graph (, )][DBLP ] Holographic Algorithms: From Art to Science. [Citation Graph (, )][DBLP ] Search in 0.010secs, Finished in 0.018secs