dblp.uni-trier.dewww.uni-trier.de

Jin-yi Cai

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

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

Coauthor Index

1Micah Adler [101]
2Sigal Ar [38]
3László Babai [52]
4Eric Bach [94] [98] [138]
5Robert Beals [52]
6Sandeep N. Bhatt [8] [31]
7Pu Cai [58] [61] [62]
8Venkatesan T. Chakaravarthy [91] [100] [109] [113] [116] [117] [118]
9Suresh Chari [42]
10Denis Charles [96] [106]
11Xi Chen [144] [150]
12Lei Chen [111]
13Vinay Choudhary [114] [121] [122] [124] [125] [127] [135]
14Anne Condon [20] [21] [24] [26] [35]
15S. Barry Cooper [126] [140] [149]
16Thomas W. Cusick [64] [72]
17David J. DeWitt [102]
18Martin Ester [134]
19Wolfgang H. J. Fuchs [37] [40]
20Martin Fürer [14] [27]
21Merrick L. Furst [22]
22Byron J. Gao [134]
23Frederic Green [49]
24Deborah S. Gross [111]
25Thomas Gundermann [7] [9]
26Juris Hartmanis [7] [9] [12] [34]
27George Havas [81]
28Lane A. Hemaspaandra (Lane A. Hemachandra) [1] [7] [9] [11] [13] [17] [23] [29] [30] [66] [67] [75] [100] [113]
29Michael D. Hirsch [39]
30Zheng Huang [111]
31Neil Immerman [14] [27]
32Gábor Ivanyos [52]
33Valentine Kabanets [74] [86]
34Raghav Kaushik [91]
35Dexter Kozen [37] [40]
36Angsheng Li [126] [149]
37Dong Li [144]
38Richard J. Lipton [15] [20] [21] [24] [26] [32] [33] [35] [41] [45] [84]
39Zicheng Liu [37] [40] [48]
40Luc Longpré [45]
41Pinyan Lu [115] [119] [120] [129] [130] [131] [132] [133] [135] [136] [137] [139] [142] [143] [145] [146] [147] [148] [150]
42Eugene M. Luks [52]
43Bernard Mans [81]
44Dieter van Melkebeek [109] [117]
45Gabriele E. Meyer [4] [6]
46David R. Musicant [111]
47Ashish V. Naik [51] [62]
48Jeffrey F. Naughton [91]
49Ajay Nerurkar [54] [56] [65] [69] [77] [81] [85]
50Mitsunori Ogihara (Mitsunori Ogiwara) [45] [100] [113]
51Aduri Pavan [78] [96] [106]
52Chung Keung Poon [115]
53Raghu Ramakrishnan [111]
54Kenneth W. Regan [43] [45] [47]
55James J. Schauer [111]
56Oliver Schulte [134]
57Robert Sedgewick [32]
58Jean-Pierre Seifert [81]
59Alan L. Selman [44] [50] [68]
60Samik Sengupta [96] [106]
61Vivian Sewelson [7] [9]
62Jonathan K. Shapiro [101]
63Igor Shparlinski [81]
64D. Sivakumar [43] [45] [46] [47] [51] [55] [57] [70] [77] [78] [83]
65Martin Strauss (Martin J. Strauss) [55]
66Thomas Thierauf [49]
67Robert A. Threlfall [107]
68Donald F. Towsley [101]
69Jozef Vyskoc [29] [30]
70Klaus W. Wagner [7] [9]
71Yuan Wang [102]
72Osamu Watanabe [103] [104] [105] [108] [110] [123]
73Gerd Wechsung [7] [9] [66] [67] [75]
74Chak-Kuen Wong (C. K. Wong) [53] [76]
75Stephen J. Wright [111]
76Mingji Xia [143] [147]
77Hui Xiong [134]
78Andrew Chi-Chih Yao [32]
79Yechezkel Zalcstein [41] [84]
80Jialin Zhang [115]
81Hong Zhu [112] [140]
82Yixin Zhu [61]

Colors in the list of coauthors

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Complete | Author
Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)