A book on the classification program of counting problems with Xi Chen
has been published by the Cambridge University Press
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
Shor-Algorithm-Under-Noisy-Gates (journal paper) (poster)
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.
