 | 2010 |
|---|
| 158 |       | Michael Kowalczyk,
Jin-yi Cai:
Holant Problems for Regular Graphs with Complex Edge Functions
CoRR abs/1001.0464: (2010) |
| 157 | | Jin-yi Cai,
Pinyan Lu:
On blockwise symmetric signatures for matchgates.
Theor. Comput. Sci. 411(4-5): 739-750 (2010) |
| 156 | | Jin-yi Cai,
Pinyan Lu:
On Symmetric Signatures in Holographic Algorithms.
Theory Comput. Syst. 46(3): 398-415 (2010) |
| 2009 |
|---|
| 155 | | Jin-yi Cai,
Vinod Yegneswaran,
Chris Alfeld,
Paul Barford:
An Attacker-Defender Game for Honeynets.
COCOON 2009: 7-16 |
| 154 | | Jin-yi Cai,
Pinyan Lu,
Mingji Xia:
Holant problems and counting CSP.
STOC 2009: 715-724 |
| 153 | | Jin-yi Cai,
Pinyan Lu,
Mingji Xia:
A Computational Proof of Complexity of Some Restricted Counting Problems.
TAMC 2009: 138-149 |
| 152 | | Peng Zhang,
Jin-yi Cai,
Linqing Tang,
Wenbo Zhao:
Approximation and Hardness Results for Label Cut and Related Problems.
TAMC 2009: 460-469 |
| 151 | | Jin-yi Cai,
Xi Chen,
Pinyan Lu:
Graph Homomorphisms with Complex Values: A Dichotomy Theorem
CoRR abs/0903.4728: (2009) |
| 150 | | Jin-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) |
| 149 | | Jin-yi Cai,
Pinyan Lu:
Holographic algorithms: The power of dimensionality resolved.
Theor. Comput. Sci. 410(18): 1618-1628 (2009) |
| 148 | | Jin-yi Cai,
Vinay Choudhary,
Pinyan Lu:
On the Theory of Matchgate Computations.
Theory Comput. Syst. 45(1): 108-132 (2009) |
| 2008 |
|---|
| 147 | | Jin-yi Cai,
Pinyan Lu,
Mingji Xia:
Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness.
FOCS 2008: 644-653 |
| 146 | | Jin-yi Cai,
Pinyan Lu:
Signature Theory in Holographic Algorithms.
ISAAC 2008: 568-579 |
| 145 | | Jin-yi Cai,
Pinyan Lu:
Holographic algorithms with unsymmetric signatures.
SODA 2008: 54-63 |
| 144 | | Jin-yi Cai,
Xi Chen,
Dong Li:
A quadratic lower bound for the permanent and determinant problem over any characteristic != 2.
STOC 2008: 491-498 |
| 143 | | Jin-yi Cai,
Pinyan Lu,
Mingji Xia:
A Family of Counter Examples to an Approach to Graph Isomorphism
CoRR abs/0801.1766: (2008) |
| 142 | | Jin-yi Cai,
Pinyan Lu:
Basis Collapse in Holographic Algorithms.
Computational Complexity 17(2): 254-281 (2008) |
| 141 | | Jin-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 |
| 139 | | Jin-yi Cai,
Pinyan Lu:
On Block-Wise Symmetric Signatures for Matchgates.
FCT 2007: 187-198 |
| 138 | | Eric Bach,
Jin-yi Cai:
A Novel Information Transmission Problem and Its Optimal Solution.
FCT 2007: 64-75 |
| 137 | | Jin-yi Cai,
Pinyan Lu:
Holographic Algorithms: The Power of Dimensionality Resolved.
ICALP 2007: 631-642 |
| 136 | | Jin-yi Cai,
Pinyan Lu:
Bases Collapse in Holographic Algorithms.
IEEE Conference on Computational Complexity 2007: 292-304 |
| 135 | | Jin-yi Cai,
Vinay Choudhary,
Pinyan Lu:
On the Theory of Matchgate Computations.
IEEE Conference on Computational Complexity 2007: 305-318 |
| 134 | | Byron 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 |
| 133 | | Jin-yi Cai,
Pinyan Lu:
On Symmetric Signatures in Holographic Algorithms.
STACS 2007: 429-440 |
| 132 | | Jin-yi Cai,
Pinyan Lu:
Holographic algorithms: from art to science.
STOC 2007: 401-410 |
| 131 | | Jin-yi Cai,
Pinyan Lu:
Bases Collapse in Holographic Algorithms.
Electronic Colloquium on Computational Complexity (ECCC) 14(003): (2007) |
| 130 | | Jin-yi Cai,
Pinyan Lu:
On Block-wise Symmetric Signatures for Matchgates.
Electronic Colloquium on Computational Complexity (ECCC) 14(019): (2007) |
| 129 | | Jin-yi Cai,
Pinyan Lu:
Holographic Algorithms: The Power of Dimensionality Resolved.
Electronic Colloquium on Computational Complexity (ECCC) 14(020): (2007) |
| 128 | | Jin-yi Cai:
S2p is subset of ZPPNP.
J. Comput. Syst. Sci. 73(1): 25-35 (2007) |
| 127 | | Jin-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 |
| 125 | | Jin-yi Cai,
Vinay Choudhary:
Some Results on Matchgates and Holographic Algorithms.
ICALP (1) 2006: 703-714 |
| 124 | | Jin-yi Cai,
Vinay Choudhary:
Valiant's Holant Theorem and Matchgate Tensors.
TAMC 2006: 248-261 |
| 123 | | Jin-yi Cai,
Osamu Watanabe:
Random Access to Advice Strings and Collapsing Results.
Algorithmica 46(1): 43-57 (2006) |
| 122 | | Jin-yi Cai,
Vinay Choudhary:
On the Theory of Matchgate Computations
Electronic Colloquium on Computational Complexity (ECCC)(018): (2006) |
| 121 | | Jin-yi Cai,
Vinay Choudhary:
Some Results on Matchgates and Holographic Algorithms.
Electronic Colloquium on Computational Complexity (ECCC) 13(048): (2006) |
| 120 | | Jin-yi Cai,
Pinyan Lu:
On Symmetric Signatures in Holographic Algorithms.
Electronic Colloquium on Computational Complexity (ECCC) 13(135): (2006) |
| 119 | | Jin-yi Cai,
Pinyan Lu:
Holographic Algorithms: From Art to Science.
Electronic Colloquium on Computational Complexity (ECCC) 13(145): (2006) |
| 118 | | Jin-yi Cai,
Venkatesan T. Chakaravarthy:
On zero error algorithms having oracle access to one query.
J. Comb. Optim. 11(2): 189-202 (2006) |
| 117 | | Jin-yi Cai,
Venkatesan T. Chakaravarthy,
Dieter van Melkebeek:
Time-Space Tradeoff in Derandomizing Probabilistic Logspace.
Theory Comput. Syst. 39(1): 189-208 (2006) |
| 2005 |
|---|
| 116 | | Jin-yi Cai,
Venkatesan T. Chakaravarthy:
A Note on Zero Error Algorithms Having Oracle Access to One NP Query.
COCOON 2005: 339-348 |
| 115 | | Pinyan Lu,
Jialin Zhang,
Chung Keung Poon,
Jin-yi Cai:
Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs.
ISAAC 2005: 767-776 |
| 114 | | Jin-yi Cai,
Vinay Choudhary:
Valiant's Holant Theorem and Matchgate Tensors
Electronic Colloquium on Computational Complexity (ECCC)(118): (2005) |
| 113 | | Jin-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) |
| 112 | | Jin-yi Cai,
Hong Zhu:
Progress in Computational Complexity Theory.
J. Comput. Sci. Technol. 20(6): 735-750 (2005) |
| 2004 |
|---|
| 111 | | Zheng 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 |
| 110 | | Jin-yi Cai,
Osamu Watanabe:
Random Access to Advice Strings and Collapsing Results.
ISAAC 2004: 209-220 |
| 109 | | Jin-yi Cai,
Venkatesan T. Chakaravarthy,
Dieter van Melkebeek:
Time-Space Tradeoff in Derandomizing Probabilistic Logspace.
STACS 2004: 571-583 |
| 108 | | Jin-yi Cai,
Osamu Watanabe:
Relativized collapsing between BPP and PH under stringent oracle access.
Inf. Process. Lett. 90(3): 147-154 (2004) |
| 107 | | Jin-yi Cai,
Robert A. Threlfall:
A note on quadratic residuosity and UP.
Inf. Process. Lett. 92(3): 127-131 (2004) |
| 106 | | Jin-yi Cai,
Denis Charles,
Aduri Pavan,
Samik Sengupta:
On Higher Arthur-Merlin Classes.
Int. J. Found. Comput. Sci. 15(1): 3-19 (2004) |
| 105 | | Jin-yi Cai,
Osamu Watanabe:
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy.
SIAM J. Comput. 33(4): 984-1009 (2004) |
| 2003 |
|---|
| 104 | | Jin-yi Cai,
Osamu Watanabe:
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results.
COCOON 2003: 202-211 |
| 103 | | Jin-yi Cai,
Osamu Watanabe:
Stringent Relativization.
FSTTCS 2003: 408-419 |
| 102 | | Yuan Wang,
David J. DeWitt,
Jin-yi Cai:
X-Diff: An Effective Change Detection Algorithm for XML Documents.
ICDE 2003: 519-530 |
| 101 | | Micah Adler,
Jin-yi Cai,
Jonathan K. Shapiro,
Donald F. Towsley:
Estimation of Congestion Price Using Probabilistic Packet Marking.
INFOCOM 2003 |
| 100 | | Jin-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) |
| 98 | | 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) |
| 97 | | Jin-yi Cai:
Essentially Every Unimodular Matrix Defines an Expander.
Theory Comput. Syst. 36(2): 105-135 (2003) |
| 2002 |
|---|
| 96 | | Jin-yi Cai,
Denis Charles,
Aduri Pavan,
Samik Sengupta:
On Higher Arthur-Merlin Classes.
COCOON 2002: 18-27 |
| 95 | | Jin-yi Cai:
On the Minimum Volume of a Perturbed Unit Cube.
ISAAC 2002: 67-78 |
| 2001 |
|---|
| 94 | | Jin-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 |
| 91 | | Jin-yi Cai,
Venkatesan T. Chakaravarthy,
Raghav Kaushik,
Jeffrey F. Naughton:
On the Complexity of Join Predicates.
PODS 2001 |
| 90 | | Jin-yi Cai:
Essentially every unimodular matrix defines an expander
Electronic Colloquium on Computational Complexity (ECCC) 8(1): (2001) |
| 89 | | Jin-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 |
| 87 | | Jin-yi Cai:
Essentially Every Unimodular Matrix Defines and Expander.
ISAAC 2000: 2-22 |
| 86 | | Valentine Kabanets,
Jin-yi Cai:
Circuit minimization problem.
STOC 2000: 73-79 |
| 85 | | 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) |
| 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) |
| 83 | | Jin-yi Cai,
D. Sivakumar:
Resolution of Hartmanis' conjecture for NL-hard sparse sets.
Theor. Comput. Sci. 240(2): 257-269 (2000) |
| 1999 |
|---|
| 82 | | Jin-yi Cai:
A New Transference Theorem in the Geometry of Numbers.
COCOON 1999: 113-122 |
| 81 | | Jin-yi Cai,
George Havas,
Bernard Mans,
Ajay Nerurkar,
Jean-Pierre Seifert,
Igor Shparlinski:
On Routing in Circulant Graphs.
COCOON 1999: 360-369 |
| 80 | | Jin-yi Cai:
Some Recent Progress on the Complexity of Lattice Problems.
IEEE Conference on Computational Complexity 1999: 158- |
| 79 | | Jin-yi Cai:
Applications of a New Transference Theorem to Ajtai's Connection Factor.
IEEE Conference on Computational Complexity 1999: 205-214 |
| 78 | | Jin-yi Cai,
Aduri Pavan,
D. Sivakumar:
On the Hardness of Permanent.
STACS 1999: 90-99 |
| 77 | | Jin-yi Cai,
Ajay Nerurkar,
D. Sivakumar:
Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time.
STOC 1999: 726-735 |
| 76 | | Jin-yi Cai,
C. K. Wong:
Foreword.
Algorithmica 23(4): 277 (1999) |
| 75 | | Jin-yi Cai,
Lane A. Hemaspaandra,
Gerd Wechsung:
Robust Reductions
CoRR cs.CC/9906033: (1999) |
| 74 | | Valentine Kabanets,
Jin-yi Cai:
Circuit Minimization Problem
Electronic Colloquium on Computational Complexity (ECCC)(45): (1999) |
| 73 | | Jin-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) |
| 71 | | 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) |
| 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) |
| 67 | | Jin-yi Cai,
Lane A. Hemaspaandra,
Gerd Wechsung:
Robust Reductions.
Theory Comput. Syst. 32(6): 625-647 (1999) |
| 1998 |
|---|
| 66 | | Jin-yi Cai,
Lane A. Hemaspaandra,
Gerd Wechsung:
Robust Reductions.
COCOON 1998: 174-183 |
| 65 | | 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- |
| 64 | | Jin-yi Cai,
Thomas W. Cusick:
A Lattice-Based Public-Key Cryptosystem.
Selected Areas in Cryptography 1998: 219-233 |
| 63 | | Jin-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) |
| 61 | | Jin-yi Cai,
Pu Cai,
Yixin Zhu:
On A Scheduling Problem of Time Deteriorating Jobs.
J. Complexity 14(2): 190-209 (1998) |
| 60 | | 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) |
| 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 |
| 56 | | Jin-yi Cai,
Ajay Nerurkar:
An Improved Worst-Case to Average-Case Connection for Lattice Problems.
FOCS 1997: 468-477 |
| 55 | | Jin-yi Cai,
D. Sivakumar,
Martin Strauss:
Constant Depth Circuits and the Lutz Hypothesis.
FOCS 1997: 595-604 |
| 54 | | Jin-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 |
| 44 | | Jin-yi Cai,
Alan L. Selman:
Average Time Complexity Classes
Electronic Colloquium on Computational Complexity (ECCC) 2(19): (1995) |
| 43 | | Kenneth 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 |
| 37 | | 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) |
| 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 |
| 31 | | Sandeep 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,
|
