Jin-Yi Cai, Steenbock Professor

Jin-Yi Cai (̽һ)
Computer Sciences Department
Room 4393
University of Wisconsin - Madison
1210 West Dayton Street
Madison, WI 53706
PHONE: (608) 262-3158
FAX: (608) 262-9777
EMAIL: jyc AT cs DOT wisc DOT edu
Dept Web Page

Shor-Algorithm-Under-Noisy-Gates (poster) pdf

Shor-Algorithm-Under-Noisy-Gates (paper) pdf

Curriculum Vitae pdf

welcoming graduate students ppt

Twelve significant publications pdf
A book on the classification program of counting problems with Xi Chen has been published by the Cambridge University Press

Brief Bio: Jin-Yi Cai studied at Fudan University (class of 77). He continued his study at Temple University and at Cornell University, where he received his Ph. D. in 1986. He held faculty positions at Yale University (1986-1989), Princeton University (1989-1993), and SUNY Buffalo (1993-2000), rising from Assistant Professor to Full Professor in 1996. He is currently a Professor of Computer Science and Steenbock Professor of Mathematical Sciences at the University of Wisconsin--Madison.

He received a Presidential Young Investigator Award in 1990, an Alfred P. Sloan Fellowship in Computer Science in 1994, a John Simon Guggenheim Fellowship in 1998, and a Morningside Silver Medal of Mathematics in 2004. He also received the Humboldt Research Award for Senior U.S. Scientists. He has been elected a Fellow of ACM, AAAS, and a foreign member of Academia Europaea. He was awarded the Godel Prize in Theoretical Computer Science and the Fulkerson Prize in Discrete Mathematics.

He is an Editor of Journal of Computer and Systems Sciences (JCSS), member of the Editorial Board of Computational Complexity, an Associate Editor of Journal of Complexity, an Editor of The Chicago Journal of Theoretical Computer Science. He works in computational complexity theory. He has written and published over 100 research papers. A list of publications according to this web site.

Here is an article from American Scientist Magazine on Holographic Algorithms by Brian Hayes. (Go to American Scientist web site)

Here is an interview with Ubiquity Magazine Ubiquity interview

Talk at ICALP 06 on Matchgate Computations. pdf

Talk at STACS 07 on Symmetric Signatures. pdf

Talk at MIT and Brown 2008 on Holographic Algorithms. pdf

Talk at Univ. of Chicago on Complexity Dichotomy of Graph Homomorphisms. pdf

Talk at Les Valiant Celebration (STOC 2009) pdf

Talk at Asian Association for Algorithms and Computation (AAAC). pdf

Talk at Dagstuhl pdf

Talk at UW Madison Math Dept on Nov 6, 2012 pdf

Some representative publications:

The Resolution of a Hartmanis Conjecture ps pdf
Resolution of Hartmanis' Conjecture for NL-hard sparse sets ps pdf
An Improved Worst-Case to Average-Case Connection for Lattice Problems ps pdf
A relation of primal-dual lattices and the complexity of shortest lattice vector problem ps pdf
A new transference theorem and applications to Ajtai's connection factor ps pdf
Hardness and Hierarchy Theorems for Probabilistic Quasi-polynomial Time ps pdf
On the Hardness of Permanent ps pdf
S_2^p \subseteq ZPP^{NP} (updated) ps pdf
On Proving Circuit Lower Bounds Against the Polynomial-time Hierarchy: Positive and Negative Results ps pdf
Essentially Every Unimodular Matrix Defines an Expander (Revised) ps pdf
Progress in Computational Compexity Theory ps pdf
Valiant's Holant Theorem and Matchgate Tensors ps pdf
On the Theory of Matchgate Computations ps pdf
Some Results on Matchgates and Holographic Algorithms ps pdf
A Novel Information Transmission Problem and its Optimal Solution pdf
On Symmetric Signatures in Holographic Algorithms ps pdf
Holographic Algorithms: From Art to Science pdf
Bases Collapse in Holographic Algorithms pdf
On Block-wise Symmetric Signatures for Matchgates ps pdf
Holographic Algorithms: The Power of Dimensionality Resolved ps pdf
A Survey on Holographic Algorithms pdf
Signature Theory in Holographic Algorithms pdf
Approximation and Hardness Results for Label Cut and Related Problems pdf
A quadratic lower bound for the permanent and determinant problem over any characteristic $\not = 2$ pdf
An Attacker-Defender Game for Honeynets pdf
Holographic Algorithms by Fibonacci Gates pdf
Holographic Reduction, Interpolation and Hardness pdf
On Holant Problems pdf
The Complexity of Complex Weighted Boolean #CSP pdf
Graph Homomorphisms with Complex Values: A Dichotomy Theorem (updated version) paper in pdf
(My talk based on this paper at Brown ICERM workshop)
Holant Problems for Regular Graphs with Complex Edge Functions pdf
Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP pdf
A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights pdf
From Holant To #CSP And Back: Dichotomy For Holant^c Problems pdf
Dichotomy for Holant^* Problems of Boolean Domain pdf
Non-negative Weighted #CSPs: An Effective Complexity Dichotomy pdf
Inapproximability After Uniqueness Phase Transition in Two-Spin Systems pdf
Complexity of Counting CSP with Complex Weights. (STOC) 2012: 909-920. To appear in JACM
A Complete Dichotomy Rises from the Capture of Vanishing Signatures pdf
Dichotomy for Holant* Problems with a Function on Domain Size 3 pdf
A Holant Dichotomy: Is the FKT Algorithm Universal? (FOCS) 2015, 1259-1276. Full version at (128 pages)
Holographic Algorithm with Matchgates Is Universal for Planar #CSP Over Boolean Domain. (94 pages)

Position Papers on TCS:

Aho et. al. Report: Theory of Computing: Goals and Directions

Goldreich-Wigderson: Theory of Computing: A Scientific Prespective

Johnson Report: Challenges for Theoretical Computer Science

Lake view in Madison (webcam)

"Cosmologists are often in error, but never in doubt." ---Lev Landau

Peaceful Shangri-La?

WebCounter says that you are visitor number since June 9, 2004.