Jin-Yi Cai (̽һ)

Computer Sciences Department

Room 4393

University of Wisconsin - Madison

1210 West Dayton Street

Madison, WI 53706

U.S.A.

PHONE: (608) 262-3158

FAX: (608) 262-9777

EMAIL: jyc AT cs DOT wisc DOT edu

Dept Web Page

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

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

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