| 2011 | AAIM | Progress in Complexity of Counting Problems. | Jin-yi Cai |
| 2011 | COCOON | Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities. | Jin-yi Cai, Michael Kowalczyk |
| 2011 | SODA | Dichotomy for Holant* Problems of Boolean Domain. | Jin-yi Cai, Pinyan Lu, Mingji Xia |
| 2010 | FAW | On Tractable Exponential Sums. | Jin-yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu |
| 2010 | FOCS | A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights. | Jin-yi Cai, Xi Chen |
| 2010 | FOCS | Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP. | Jin-yi Cai, Pinyan Lu, Mingji Xia |
| 2010 | ICALP | Graph Homomorphisms with Complex Values: A Dichotomy Theorem. | Jin-yi Cai, Xi Chen, Pinyan Lu |
| 2010 | ISAAC | From Holant to #CSP and Back: Dichotomy for Holant | Jin-yi Cai, Sangxia Huang, Pinyan Lu |
| 2010 | STACS | Holant Problems for Regular Graphs with Complex Edge Functions. | Michael Kowalczyk, Jin-yi Cai |
| 2010 | TAMC | A Dichotomy for | Jin-yi Cai, Michael Kowalczyk |
| 2009 | COCOON | An Attacker-Defender Game for Honeynets. | Jin-yi Cai, Vinod Yegneswaran, Chris Alfeld, Paul Barford |
| 2009 | STOC | Holant problems and counting CSP. | Jin-yi Cai, Pinyan Lu, Mingji Xia |
| 2009 | TAMC | A Computational Proof of Complexity of Some Restricted Counting Problems. | Jin-yi Cai, Pinyan Lu, Mingji Xia |
| 2009 | TAMC | Approximation and Hardness Results for Label Cut and Related Problems. | Peng Zhang, Jin-yi Cai, Linqing Tang, Wenbo Zhao |
| 2008 | FOCS | Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. | Jin-yi Cai, Pinyan Lu, Mingji Xia |
| 2008 | ISAAC | Signature Theory in Holographic Algorithms. | Jin-yi Cai, Pinyan Lu |
| 2008 | SODA | Holographic algorithms with unsymmetric signatures. | Jin-yi Cai, Pinyan Lu |
| 2008 | STOC | A quadratic lower bound for the permanent and determinant problem over any characteristic != 2. | Jin-yi Cai, Xi Chen, Dong Li |
| 2007 | FCT | A Novel Information Transmission Problem and Its Optimal Solution. | Eric Bach, Jin-yi Cai |
| 2007 | FCT | On Block-Wise Symmetric Signatures for Matchgates. | Jin-yi Cai, Pinyan Lu |
| 2007 | ICALP | Holographic Algorithms: The Power of Dimensionality Resolved. | Jin-yi Cai, Pinyan Lu |
| 2007 | KDD | The minimum consistent subset cover problem and its applications in data mining. | Byron J. Gao, Martin Ester, Jin-yi Cai, Oliver Schulte, Hui Xiong |
| 2007 | STOC | Holographic algorithms: from art to science. | Jin-yi Cai, Pinyan Lu |
| 2007 | STACS | On Symmetric Signatures in Holographic Algorithms. | Jin-yi Cai, Pinyan Lu |
| 2006 | ICALP | Some Results on Matchgates and Holographic Algorithms. | Jin-yi Cai, Vinay Choudhary |
| 2006 | TAMC | Valiant's Holant Theorem and Matchgate Tensors. | Jin-yi Cai, Vinay Choudhary |
| 2005 | COCOON | A Note on Zero Error Algorithms Having Oracle Access to One NP Query. | Jin-yi Cai, Venkatesan T. Chakaravarthy |
| 2005 | ISAAC | Simulating Undirected | Pinyan Lu, Jialin Zhang, Chung Keung Poon, Jin-yi Cai |
| 2004 | ICDM | Mass Spectrum Labeling: Theory and Practice. | Zheng Huang, Lei Chen, Jin-yi Cai, Deborah S. Gross, David R. Musicant, Raghu Ramakrishnan, James J. Schauer, Stephen J. Wright |
| 2004 | ISAAC | Random Access to Advice Strings and Collapsing Results. | Jin-yi Cai, Osamu Watanabe |
| 2004 | STACS | Time-Space Tradeoff in Derandomizing Probabilistic Logspace. | Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek |
| 2003 | COCOON | On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results. | Jin-yi Cai, Osamu Watanabe |
| 2003 | ICDE | X-Diff: An Effective Change Detection Algorithm for XML Documents. | Yuan Wang, David J. DeWitt, Jin-yi Cai |
| 2003 | INFOCOM | Estimation of Congestion Price Using Probabilistic Packet Marking. | Micah Adler, Jin-yi Cai, Jonathan K. Shapiro, Donald F. Towsley |
| 2003 | STACS | Competing Provers Yield Improved Karp-Lipton Collapse Results. | Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara |
| 2002 | COCOON | On Higher Arthur-Merlin Classes. | Jin-yi Cai, Denis Charles, Aduri Pavan, Samik Sengupta |
| 2002 | ISAAC | On the Minimum Volume of a Perturbed Unit Cube. | Jin-yi Cai |
| 2001 | COCOON | On Testing for Zero Polynomials by a Set of Points with Bounded Precision. | Jin-yi Cai, Eric Bach |
| 2001 | FOCS | On the Average-Case Hardness of CVP. | Jin-yi Cai |
| 2001 | FOCS | S | Jin-yi Cai |
| 2001 | PODS | On the Complexity of Join Predicates. | Jin-yi Cai, Venkatesan T. Chakaravarthy, Raghav Kaushik, Jeffrey F. Naughton |
| 2000 | ISAAC | Essentially Every Unimodular Matrix Defines and Expander. | Jin-yi Cai |
| 2000 | STOC | Circuit minimization problem. | Valentine Kabanets, Jin-yi Cai |
| 1999 | COCOON | A New Transference Theorem in the Geometry of Numbers. | Jin-yi Cai |
| 1999 | COCOON | On Routing in Circulant Graphs. | Jin-yi Cai, George Havas, Bernard Mans, Ajay Nerurkar, Jean-Pierre Seifert, Igor E. Shparlinski |
| 1999 | STOC | Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. | Jin-yi Cai, Ajay Nerurkar, D. Sivakumar |
| 1999 | STACS | On the Hardness of Permanent. | Jin-yi Cai, Aduri Pavan, D. Sivakumar |
| 1998 | COCOON | Robust Reductions. | Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung |
| 1997 | COCOON | On the 100% Rule of Sensivity Analzsis in Linear Programming. | Pu Cai, Jin-yi Cai |
| 1997 | COCOON | Resolution of Hartmanis' Conjecture for NL-Hard Sparse Sets. | Jin-yi Cai, D. Sivakumar |
| 1997 | FOCS | An Improved Worst-Case to Average-Case Connection for Lattice Problems. | Jin-yi Cai, Ajay Nerurkar |
| 1997 | FOCS | Constant Depth Circuits and the Lutz Hypothesis. | Jin-yi Cai, D. Sivakumar, Martin Strauss |
| 1996 | SODA | Multiplicative Equations over Commuting Matrices. | Lszl Babai, Robert Beals, Jin-yi Cai, Gbor Ivanyos, Eugene M. Luks |
| 1996 | STACS | On the Existence of Hard Sparse Sets under Weak Reductions. | Jin-yi Cai, Ashish V. Naik, D. Sivakumar |
| 1996 | STACS | Fine Separation of Average Time Complexity Classes. | Jin-yi Cai, Alan L. Selman |
| 1995 | FOCS | The Resolution of a Hartmanis Conjecture. | Jin-yi Cai, D. Sivakumar |
| 1995 | FOCS | Pseudorandom Generators, Measure Theory, and Natural Proofs. | Kenneth W. Regan, D. Sivakumar, Jin-yi Cai |
| 1995 | STACS | Communication Complexity of Key Agreement on Small Ranges. | Jin-yi Cai, Richard J. Lipton, Luc Longpr, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar |
| 1994 | FOCS | Efficient Average-Case Algorithms for the Modular Group | Jin-yi Cai, Wolfgang H. J. Fuchs, Dexter Kozen, Zicheng Liu |
| 1994 | FOCS | The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices | Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein |
| 1994 | ISAAC | Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic Geometry. | Jin-yi Cai, Michael D. Hirsch |
| 1994 | SODA | Reliable Benchmarks Using Numerical Instability. | Sigal Ar, Jin-yi Cai |
| 1992 | MFCS | Promise Problems and Access to Unambiguous Computation. | Jin-yi Cai, Lane A. Hemachandra, Jozef Vyskoc |
| 1992 | STOC | Parallel Computation Over Hyperbolic Groups | Jin-yi Cai |
| 1991 | FCT | Computations Over Infinite Groups. | Jin-yi Cai |
| 1990 | STACS | Playing Games of Incomplete Information. | Jin-yi Cai, Anne Condon, Richard J. Lipton |
| 1989 | FOCS | Lower Bounds for Constant Depth Circuits in the Presence of Help Bits | Jin-yi Cai |
| 1989 | FOCS | An Optimal Lower Bound on the Number of Variables for Graph Identification | Jin-yi Cai, Martin Frer, Neil Immerman |
| 1989 | FOCS | Subquadratic Simulations of Circuits by Branching Programs | Jin-yi Cai, Richard J. Lipton |
| 1989 | STACS | On the Power of Parity Polynomial Time. | Jin-yi Cai, Lane A. Hemachandra |
| 1988 | FOCS | Take a Walk, Grow a Tree (Preliminary Version) | Sandeep N. Bhatt, Jin-yi Cai |
| 1987 | ICALP | On the Complexity of Graph Critical Uncolorability. | Jin-yi Cai, Gabriele E. Meyer |
| 1987 | STACS | Probability One Separation of the Boolean Hierarchy. | Jin-yi Cai |
| 1986 | STOC | With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy | Jin-yi Cai |