Jin-Yi Cai

Byron J. Gao, Martin Ester, Hui Xiong, Jin-Yi Cai, Oliver Schulte: The Minimum Consistent Subset Cover Problem: A Minimization View of Data Mining. IEEE Trans. Knowl. Data Eng. 25(3): 690-703 (2013)

Chen Zeng, Jin-Yi Cai, Pinyan Lu, Jeffrey F. Naughton: On optimal differentially private mechanisms for count-range queries. ICDT 2013: 261-271

Jin-Yi Cai: Complexity Dichotomy for Counting Problems. LATA 2013: 1-11

Jin-Yi Cai, Pinyan Lu, Mingji Xia: Dichotomy for Holant* Problems with Domain Size 3. SODA 2013: 1278-1295

Jin-Yi Cai, Aaron Gorenstein: Matchgates Revisited. CoRR abs/1303.6729 (2013)

Jin-Yi Cai, Aaron Gorenstein: Matchgates Revisited. Electronic Colloquium on Computational Complexity (ECCC) 20: 48 (2013)

Jin-Yi Cai, Sangxia Huang, Pinyan Lu: From Holant to #CSP and Back: Dichotomy for Holant c Problems. Algorithmica 64(3): 511-533 (2012)

Jin-Yi Cai, Pinyan Lu, Mingji Xia: Holographic reduction, interpolation and hardness. Computational Complexity 21(4): 573-604 (2012)

Chen Zeng, Jeffrey F. Naughton, Jin-Yi Cai: On differentially private frequent itemset mining. PVLDB 6(1): 25-36 (2012)

Jin-Yi Cai, Michael Kowalczyk: Spin systems on k-regular graphs with complex edge functions. Theor. Comput. Sci. 461: 2-16 (2012)

Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu: Inapproximability after Uniqueness Phase Transition in Two-Spin Systems. COCOA 2012: 336-347

Jin-yi Cai, Michael Kowalczyk, Tyson Williams: Gadgets and anti-gadgets leading to a complexity dichotomy. ITCS 2012: 452-467

Jin-Yi Cai, Xi Chen: Complexity of counting CSP with complex weights. STOC 2012: 909-920

Zhiguo Fu, Jin-Yi Cai: Holographic Algorithms on Domain Size k > 2. TAMC 2012: 346-359

Jin-Yi Cai, Heng Guo, Tyson Williams: A Complete Dichotomy Rises from the Capture of Vanishing Signatures. CoRR abs/1204.6445 (2012)

Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu: Inapproximability After Uniqueness Phase Transition in Two-Spin Systems. CoRR abs/1205.2934 (2012)

Jin-Yi Cai, Pinyan Lu, Mingji Xia: Dichotomy for Holant* Problems with a Function on Domain Size 3. CoRR abs/1207.2354 (2012)

Jin-yi Cai, Pinyan Lu: Signature Theory in Holographic Algorithms. Algorithmica 61(4): 779-816 (2011)

Peng Zhang, Jin-yi Cai, Linqing Tang, Wenbo Zhao: Approximation and hardness results for label cut and related problems. J. Comb. Optim. 21(2): 192-208 (2011)

Jin-yi Cai, Vinod Yegneswaran, Chris Alfeld, Paul Barford: Honeynet games: a game theoretic approach to defending network monitors. J. Comb. Optim. 22(3): 305-324 (2011)

Jin-yi Cai, Alan L. Selman: Foreword. J. Comput. Syst. Sci. 77(1): 1-2 (2011)

Jin-yi Cai, Pinyan Lu: Holographic algorithms: From art to science. J. Comput. Syst. Sci. 77(1): 41-61 (2011)

Jin-yi Cai, Pinyan Lu, Mingji Xia: Computational Complexity of Holant Problems. SIAM J. Comput. 40(4): 1101-1132 (2011)

Jin-yi Cai, Pinyan Lu, Mingji Xia: A computational proof of complexity of some restricted counting problems. Theor. Comput. Sci. 412(23): 2468-2485 (2011)

Jin-yi Cai: Progress in Complexity of Counting Problems. FAW-AAIM 2011: 1-3

Jin-yi Cai, Xi Chen, Pinyan Lu: Non-negatively Weighted #CSP: An Effective Complexity Dichotomy. IEEE Conference on Computational Complexity 2011: 45-54

Jin-yi Cai, Michael Kowalczyk: Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities. COCOON 2011: 146-157

Jin-yi Cai, Pinyan Lu, Mingji Xia: Dichotomy for Holant* Problems of Boolean Domain. SODA 2011: 1714-1728

Jin-yi Cai, Michael Kowalczyk, Tyson Williams: Gadgets and Anti-gadgets Leading to a Complexity Dichotomy. CoRR abs/1108.3383 (2011)

Jin-yi Cai, Xi Chen: Complexity of Counting CSP with Complex Weights. CoRR abs/1111.2384 (2011)

Jin-yi Cai, Xi Chen, Dong Li: Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic. Computational Complexity 19(1): 37-56 (2010)

Jin-yi Cai, Pinyan Lu: On Symmetric Signatures in Holographic Algorithms. Theory Comput. Syst. 46(3): 398-415 (2010)

Jin-yi Cai, Pinyan Lu: On blockwise symmetric signatures for matchgates. Theor. Comput. Sci. 411(4-5): 739-750 (2010)

Jin-yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu: On Tractable Exponential Sums. FAW 2010: 148-159

Jin-yi Cai, Pinyan Lu, Mingji Xia: Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP. FOCS 2010: 427-436

Jin-yi Cai, Xi Chen: A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights. FOCS 2010: 437-446

Jin-yi Cai, Xi Chen, Pinyan Lu: Graph Homomorphisms with Complex Values: A Dichotomy Theorem. ICALP (1) 2010: 275-286

Jin-yi Cai, Sangxia Huang, Pinyan Lu: From Holant to #CSP and Back: Dichotomy for Holant^c Problems. ISAAC (1) 2010: 253-265

Michael Kowalczyk, Jin-yi Cai: Holant Problems for Regular Graphs with Complex Edge Functions. STACS 2010: 525-536

Jin-yi Cai, Michael Kowalczyk: A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions. TAMC 2010: 328-339

Michael Kowalczyk, Jin-yi Cai: Holant Problems for Regular Graphs with Complex Edge Functions. CoRR abs/1001.0464 (2010)

Jin-yi Cai, Sangxia Huang, Pinyan Lu: From Holant To #CSP And Back: Dichotomy For Holant$^c$ Problems. CoRR abs/1004.0803 (2010)

Jin-yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu: On Tractable Exponential Sums. CoRR abs/1005.2632 (2010)

Jin-yi Cai, Pinyan Lu, Mingji Xia: Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. CoRR abs/1008.0683 (2010)

Jin-yi Cai, Xi Chen: A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights. CoRR abs/1008.0915 (2010)

Jin-yi Cai, Xi Chen, Pinyan Lu: Non-negative Weighted #CSPs: An Effective Complexity Dichotomy. CoRR abs/1012.5659 (2010)

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)

Jin-yi Cai, Vinay Choudhary, Pinyan Lu: On the Theory of Matchgate Computations. Theory Comput. Syst. 45(1): 108-132 (2009)

Jin-yi Cai, Pinyan Lu: Holographic algorithms: The power of dimensionality resolved. Theor. Comput. Sci. 410(18): 1618-1628 (2009)

Jin-yi Cai, Vinod Yegneswaran, Chris Alfeld, Paul Barford: An Attacker-Defender Game for Honeynets. COCOON 2009: 7-16

Jin-yi Cai, Pinyan Lu, Mingji Xia: Holant problems and counting CSP. STOC 2009: 715-724

Jin-yi Cai, Pinyan Lu, Mingji Xia: A Computational Proof of Complexity of Some Restricted Counting Problems. TAMC 2009: 138-149

Peng Zhang, Jin-yi Cai, Linqing Tang, Wenbo Zhao: Approximation and Hardness Results for Label Cut and Related Problems. TAMC 2009: 460-469

Jin-yi Cai, Xi Chen, Pinyan Lu: Graph Homomorphisms with Complex Values: A Dichotomy Theorem. CoRR abs/0903.4728 (2009)

Jin-yi Cai, Pinyan Lu: Basis Collapse in Holographic Algorithms. Computational Complexity 17(2): 254-281 (2008)

Jin-yi Cai: Holographic algorithms: guest column. SIGACT News 39(2): 51-81 (2008)

Jin-yi Cai, Pinyan Lu, Mingji Xia: Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. FOCS 2008: 644-653

Jin-yi Cai, Pinyan Lu: Signature Theory in Holographic Algorithms. ISAAC 2008: 568-579

Jin-yi Cai, Pinyan Lu: Holographic algorithms with unsymmetric signatures. SODA 2008: 54-63

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

Jin-yi Cai, Pinyan Lu, Mingji Xia: A Family of Counter Examples to an Approach to Graph Isomorphism. CoRR abs/0801.1766 (2008)

Jin-yi Cai, Vinay Choudhary: Some Results on Matchgates and Holographic Algorithms. Int. J. Software and Informatics 1(1): 3-36 (2007)

Jin-yi Cai: S₂^p is subset of ZPP^NP. J. Comput. Syst. Sci. 73(1): 25-35 (2007)

Jin-yi Cai, Vinay Choudhary: Valiant's Holant Theorem and matchgate tensors. Theor. Comput. Sci. 384(1): 22-32 (2007)

Jin-yi Cai, Pinyan Lu: Bases Collapse in Holographic Algorithms. IEEE Conference on Computational Complexity 2007: 292-304

Jin-yi Cai, Vinay Choudhary, Pinyan Lu: On the Theory of Matchgate Computations. IEEE Conference on Computational Complexity 2007: 305-318

Eric Bach, Jin-yi Cai: A Novel Information Transmission Problem and Its Optimal Solution. FCT 2007: 64-75

Jin-yi Cai, Pinyan Lu: On Block-Wise Symmetric Signatures for Matchgates. FCT 2007: 187-198

Jin-yi Cai, Pinyan Lu: Holographic Algorithms: The Power of Dimensionality Resolved. ICALP 2007: 631-642

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

Jin-yi Cai, Pinyan Lu: On Symmetric Signatures in Holographic Algorithms. STACS 2007: 429-440

Jin-yi Cai, Pinyan Lu: Holographic algorithms: from art to science. STOC 2007: 401-410

Jin-yi Cai, S. Barry Cooper, Hong Zhu (Eds.): Theory and Applications of Models of Computation, 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, Proceedings. Lecture Notes in Computer Science 4484, Springer 2007, isbn 978-3-540-72503-9

Jin-yi Cai, Pinyan Lu: Bases Collapse in Holographic Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 14(003) (2007)

Jin-yi Cai, Pinyan Lu: On Block-wise Symmetric Signatures for Matchgates. Electronic Colloquium on Computational Complexity (ECCC) 14(019) (2007)

Jin-yi Cai, Pinyan Lu: Holographic Algorithms: The Power of Dimensionality Resolved. Electronic Colloquium on Computational Complexity (ECCC) 14(020) (2007)

Jin-yi Cai, Osamu Watanabe: Random Access to Advice Strings and Collapsing Results. Algorithmica 46(1): 43-57 (2006)

Jin-yi Cai, Venkatesan T. Chakaravarthy: On zero error algorithms having oracle access to one query. J. Comb. Optim. 11(2): 189-202 (2006)

Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek: Time-Space Tradeoff in Derandomizing Probabilistic Logspace. Theory Comput. Syst. 39(1): 189-208 (2006)

Jin-yi Cai, Vinay Choudhary: Some Results on Matchgates and Holographic Algorithms. ICALP (1) 2006: 703-714

Jin-yi Cai, Vinay Choudhary: Valiant's Holant Theorem and Matchgate Tensors. TAMC 2006: 248-261

Jin-yi Cai, S. Barry Cooper, Angsheng Li (Eds.): Theory and Applications of Models of Computation, Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006, Proceedings. Lecture Notes in Computer Science 3959, Springer 2006, isbn 3-540-34021-1

Jin-yi Cai, Vinay Choudhary: On the Theory of Matchgate Computations. Electronic Colloquium on Computational Complexity (ECCC)(018) (2006)

Jin-yi Cai, Vinay Choudhary: Some Results on Matchgates and Holographic Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 13(048) (2006)

Jin-yi Cai, Pinyan Lu: On Symmetric Signatures in Holographic Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 13(135) (2006)

Jin-yi Cai, Pinyan Lu: Holographic Algorithms: From Art to Science. Electronic Colloquium on Computational Complexity (ECCC) 13(145) (2006)

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)

Jin-yi Cai, Hong Zhu: Progress in Computational Complexity Theory. J. Comput. Sci. Technol. 20(6): 735-750 (2005)

Jin-yi Cai, Venkatesan T. Chakaravarthy: A Note on Zero Error Algorithms Having Oracle Access to One NP Query. COCOON 2005: 339-348

Pinyan Lu, Jialin Zhang, Chung Keung Poon, Jin-yi Cai: Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs. ISAAC 2005: 767-776

Jin-yi Cai, Vinay Choudhary: Valiant's Holant Theorem and Matchgate Tensors. Electronic Colloquium on Computational Complexity (ECCC)(118) (2005)

Jin-yi Cai, Denis Charles, Aduri Pavan, Samik Sengupta: On Higher Arthur-Merlin Classes. Int. J. Found. Comput. Sci. 15(1): 3-19 (2004)

Jin-yi Cai, Osamu Watanabe: Relativized collapsing between BPP and PH under stringent oracle access. Inf. Process. Lett. 90(3): 147-154 (2004)

Jin-yi Cai, Robert A. Threlfall: A note on quadratic residuosity and UP. Inf. Process. Lett. 92(3): 127-131 (2004)

Jin-yi Cai, Osamu Watanabe: On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy. SIAM J. Comput. 33(4): 984-1009 (2004)

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

Jin-yi Cai, Osamu Watanabe: Random Access to Advice Strings and Collapsing Results. ISAAC 2004: 209-220

Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek: Time-Space Tradeoff in Derandomizing Probabilistic Logspace. STACS 2004: 571-583

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)

Jin-yi Cai: Essentially Every Unimodular Matrix Defines an Expander. Theory Comput. Syst. 36(2): 105-135 (2003)

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)

Jin-yi Cai, Osamu Watanabe: On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results. COCOON 2003: 202-211

Jin-yi Cai, Osamu Watanabe: Stringent Relativization. FSTTCS 2003: 408-419

Yuan Wang, David J. DeWitt, Jin-yi Cai: X-Diff: An Effective Change Detection Algorithm for XML Documents. ICDE 2003: 519-530

Micah Adler, Jin-yi Cai, Jonathan K. Shapiro, Donald F. Towsley: Estimation of Congestion Price Using Probabilistic Packet Marking. INFOCOM 2003

Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara: Competing Provers Yield Improved Karp-Lipton Collapse Results. STACS 2003: 535-546

Jin-yi Cai, Denis Charles, Aduri Pavan, Samik Sengupta: On Higher Arthur-Merlin Classes. COCOON 2002: 18-27

Jin-yi Cai: On the Minimum Volume of a Perturbed Unit Cube. ISAAC 2002: 67-78

Jin-yi Cai, Eric Bach: On Testing for Zero Polynomials by a Set of Points with Bounded Precision. COCOON 2001: 473-482

Jin-yi Cai: On the Average-Case Hardness of CVP. FOCS 2001: 308-317

Jin-yi Cai: S^p₂ subseteq ZPP^NP. FOCS 2001: 620-629

Jin-yi Cai, Venkatesan T. Chakaravarthy, Raghav Kaushik, Jeffrey F. Naughton: On the Complexity of Join Predicates. PODS 2001

Jin-yi Cai: Essentially every unimodular matrix defines an expander. Electronic Colloquium on Computational Complexity (ECCC) 8(1) (2001)

Jin-yi Cai: S_2^p \subseteq ZPP^NP. Electronic Colloquium on Computational Complexity (ECCC) 8(30) (2001)

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)

Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein: The Complexity of the A B C Problem. SIAM J. Comput. 29(6): 1878-1888 (2000)

Jin-yi Cai, D. Sivakumar: Resolution of Hartmanis' conjecture for NL-hard sparse sets. Theor. Comput. Sci. 240(2): 257-269 (2000)

Jin-yi Cai: The Complexity of Some Lattice Problems. ANTS 2000: 1-32

Jin-yi Cai: Essentially Every Unimodular Matrix Defines and Expander. ISAAC 2000: 2-22

Valentine Kabanets, Jin-yi Cai: Circuit minimization problem. STOC 2000: 73-79

Jin-yi Cai, C. K. Wong: Foreword. Algorithmica 23(4): 277 (1999)

Jin-yi Cai, Thomas W. Cusick: A Lattice-Based Public-Key Cryptosystem. Inf. Comput. 151(1-2): 17-31 (1999)

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)

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)

Jin-yi Cai, Ajay Nerurkar: Approximating the SVP to within a Factor (1+1/dim^xi) Is NP-Hard under Randomized Reductions. J. Comput. Syst. Sci. 59(2): 221-239 (1999)

Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung: Robust Reductions. Theory Comput. Syst. 32(6): 625-647 (1999)

Jin-yi Cai, Alan L. Selman: Fine Separation of Average-Time Complexity Classes. SIAM J. Comput. 28(4): 1310-1325 (1999)

Jin-yi Cai: Some Recent Progress on the Complexity of Lattice Problems. IEEE Conference on Computational Complexity 1999: 158-

Jin-yi Cai: Applications of a New Transference Theorem to Ajtai's Connection Factor. IEEE Conference on Computational Complexity 1999: 205-214

Jin-yi Cai: A New Transference Theorem in the Geometry of Numbers. COCOON 1999: 113-122

Jin-yi Cai, George Havas, Bernard Mans, Ajay Nerurkar, Jean-Pierre Seifert, Igor Shparlinski: On Routing in Circulant Graphs. COCOON 1999: 360-369

Jin-yi Cai, Aduri Pavan, D. Sivakumar: On the Hardness of Permanent. STACS 1999: 90-99

Jin-yi Cai, Ajay Nerurkar, D. Sivakumar: Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. STOC 1999: 726-735

Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung: Robust Reductions. CoRR cs.CC/9906033 (1999)

Jin-yi Cai: Some Recent Progress on the Complexity of Lattice Problems. Electronic Colloquium on Computational Complexity (ECCC) 6(6) (1999)

Valentine Kabanets, Jin-yi Cai: Circuit Minimization Problem. Electronic Colloquium on Computational Complexity (ECCC)(45) (1999)

Jin-yi Cai, Pu Cai, Yixin Zhu: On A Scheduling Problem of Time Deteriorating Jobs. J. Complexity 14(2): 190-209 (1998)

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)

Jin-yi Cai: Frobenius's Degree Formula and Toda's Polynomials. Theory Comput. Syst. 31(1): 67-75 (1998)

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)

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-

Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung: Robust Reductions. COCOON 1998: 174-183

Jin-yi Cai, Thomas W. Cusick: A Lattice-Based Public-Key Cryptosystem. Selected Areas in Cryptography 1998: 219-233

Jin-yi Cai: A new transference theorem and applications to Ajtai's connection factor. Electronic Colloquium on Computational Complexity (ECCC) 5(5) (1998)

Jin-yi Cai, D. Sivakumar: Resolution of Hartmanis' Conjecture for NL-Hard Sparse Sets. COCOON 1997: 62-71

Pu Cai, Jin-yi Cai: On the 100% Rule of Sensivity Analzsis in Linear Programming. COCOON 1997: 460-469

Jin-yi Cai, Ajay Nerurkar: An Improved Worst-Case to Average-Case Connection for Lattice Problems. FOCS 1997: 468-477

Jin-yi Cai, D. Sivakumar, Martin Strauss: Constant Depth Circuits and the Lutz Hypothesis. FOCS 1997: 595-604

Jin-yi Cai, Ajay Nerurkar: Approximating the SVP to within a factor (1 + 1/dim^epsilon) is NP-hard under randomized reductions. Electronic Colloquium on Computational Complexity (ECCC) 4(59) (1997)

Jin-yi Cai, Frederic Green, Thomas Thierauf: On the Correlation of Symmetric Functions. Mathematical Systems Theory 29(3): 245-258 (1996)

Jin-yi Cai, Zicheng Liu: The Bounded Membership Problem of the Monoid SL_2(N). Mathematical Systems Theory 29(6): 573-587 (1996)

László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, Eugene M. Luks: Multiplicative Equations over Commuting Matrices. SODA 1996: 498-507

Jin-yi Cai, Ashish V. Naik, D. Sivakumar: On the Existence of Hard Sparse Sets under Weak Reductions. STACS 1996: 307-318

Jin-yi Cai, Alan L. Selman: Fine Separation of Average Time Complexity Classes. STACS 1996: 331-343

Steven Homer, Jin-Yi Cai (Eds.): Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996. IEEE Computer Society 1996, isbn 0-8186-7386-9

Jin-yi Cai, C. K. Wong (Eds.): Computing and Combinatorics, Second Annual International Conference, COCOON '96, Hong Kong, June 17-19, 1996, Proceedings. Lecture Notes in Computer Science 1090, Springer 1996, isbn 3-540-61332-3

Jin-yi Cai, Suresh Chari: On the Impossibility of Amplifying the Independence of Random Variables. Random Struct. Algorithms 7(4): 301-310 (1995)

Kenneth W. Regan, D. Sivakumar, Jin-yi Cai: Pseudorandom Generators, Measure Theory, and Natural Proofs. FOCS 1995: 26-35

Jin-yi Cai, D. Sivakumar: The Resolution of a Hartmanis Conjecture. FOCS 1995: 362-371

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

Kenneth W. Regan, D. Sivakumar, Jin-yi Cai: Pseudorandom Generators, Measure Theory, and Natural Proofs. Electronic Colloquium on Computational Complexity (ECCC) 2(6) (1995)

Jin-yi Cai, Alan L. Selman: Average Time Complexity Classes. Electronic Colloquium on Computational Complexity (ECCC) 2(19) (1995)

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)

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)

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)

Jin-yi Cai, Richard J. Lipton: Subquadratic Simulations of Balanced Formulae by Branching Programs. SIAM J. Comput. 23(3): 563-572 (1994)

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

Jin-yi Cai, Wolfgang H. J. Fuchs, Dexter Kozen, Zicheng Liu: Efficient Average-Case Algorithms for the Modular Group. FOCS 1994: 143-152

Jin-yi Cai, Michael D. Hirsch: Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic Geometry. ISAAC 1994: 172-180

Sigal Ar, Jin-yi Cai: Reliable Benchmarks Using Numerical Instability. SODA 1994: 34-43

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)

Sandeep N. Bhatt, Jin-yi Cai: Taking Random Walks to Grow Trees in Hypercubes. J. ACM 40(3): 741-764 (1993)

Jin-yi Cai, Richard J. Lipton, Robert Sedgewick, Andrew Chi-Chih Yao: Towards Uncheatable benchmarks. Structure in Complexity Theory Conference 1993: 2-11

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)

Jin-yi Cai, Anne Condon, Richard J. Lipton: On Games of Incomplete Information. Theor. Comput. Sci. 103(1): 25-38 (1992)

Jin-yi Cai, Lane A. Hemachandra, Jozef Vyskoc: Promise Problems and Guarded Access to Unambiguous Computation. Complexity Theory: Current Research 1992: 101-146

Jin-yi Cai, Lane A. Hemachandra, Jozef Vyskoc: Promise Problems and Access to Unambiguous Computation. MFCS 1992: 162-171

Jin-yi Cai: Parallel Computation Over Hyperbolic Groups. STOC 1992: 106-115

Jin-yi Cai, Merrick L. Furst: PSPACE Survives Constant-Width Bottlenecks. Int. J. Found. Comput. Sci. 2(1): 67-76 (1991)

Jin-yi Cai, Lane A. Hemachandra: A Note on Enumarative Counting. Inf. Process. Lett. 38(4): 215-219 (1991)

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

Jin-yi Cai: Computations Over Infinite Groups. FCT 1991: 22-32

Jin-yi Cai: A Note on the Determinant and Permanent Problem. Inf. Comput. 84(1): 119-127 (1990)

Jin-yi Cai: Lower Bounds for Constant-Depth Circuits in the Presence of Help Bits. Inf. Process. Lett. 36(2): 79-83 (1990)

Jin-yi Cai, Lane A. Hemachandra: On the Power of Parity Polynomial Time. Mathematical Systems Theory 23(2): 95-106 (1990)

Jin-yi Cai, Anne Condon, Richard J. Lipton: On Bounded Round Multi-Prover Interactive Proof Systems. Structure in Complexity Theory Conference 1990: 45-54

Jin-yi Cai, Anne Condon, Richard J. Lipton: Playing Games of Incomplete Information. STACS 1990: 58-69

Jin-yi Cai, Lane A. Hemachandra: Enumerative Counting Is Hard. Inf. Comput. 82(1): 34-44 (1989)

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)

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)

Jin-yi Cai, Juris Hartmanis: The Complexity Of The Real Line Is A Fractal. Structure in Complexity Theory Conference 1989: 138-146

Jin-yi Cai: Lower Bounds for Constant Depth Circuits in the Presence of Help Bits. FOCS 1989: 532-537

Jin-yi Cai, Richard J. Lipton: Subquadratic Simulations of Circuits by Branching Programs. FOCS 1989: 568-573

Jin-yi Cai, Martin Fürer, Neil Immerman: An Optimal Lower Bound on the Number of Variables for Graph Identification. FOCS 1989: 612-617

Jin-yi Cai, Lane A. Hemachandra: On the Power of Parity Polynomial Time. STACS 1989: 229-239

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)

Jin-Yi Cai, Lane A. Hemachandra: Enumerative counting is hard. Structure in Complexity Theory Conference 1988: 194-203

Sandeep N. Bhatt, Jin-yi Cai: Take a Walk, Grow a Tree (Preliminary Version). FOCS 1988: 469-478

Jin-yi Cai, Gabriele E. Meyer: Graph Minimal Uncolorability is D^P-Complete. SIAM J. Comput. 16(2): 259-277 (1987)

Jin-Yi Cai, Merrick L. Furst: PSPACE survives three-bit bottlenecks. Structure in Complexity Theory Conference 1987

Jin-yi Cai, Gabriele E. Meyer: On the Complexity of Graph Critical Uncolorability. ICALP 1987: 394-403

Jin-yi Cai: Probability One Separation of the Boolean Hierarchy. STACS 1987: 148-158

Jin-yi Cai: With Probability One, A Random Oracle Separates PSPACE from the Polynomial- Time Hierarchy. Structure in Complexity Theory Conference 1986: 104-104

Jin-yi Cai, Lane A. Hemachandra: The Boolean Hierarchy: Hardware over NP. Structure in Complexity Theory Conference 1986: 105-124

Jin-yi Cai: With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy. STOC 1986: 21-29