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
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 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 and AAAS.
He is an Associate Editor of Journal of Complexity, Journal of Computer and Systems Sciences (JCSS), an Editor of International Journal of Foundations of Computer Science, an Editor of The Chicago Journal of Theoretical Computer Science, and an Area Editor for International Journal of Software and Informatics. He works in computational complexity theory. He has written and published over 100 research papers. His recent paper with Pinyan Lu on holographic algorithms won the best paper award at ICALP 2007.
Here is an article from American Scientist Magazine on Holographic Algorithms by Brian Hayes. (Go to American Scientist web site)
List of publications according to this web site.
Here is an interview with Ubiquity Magazine Ubiquity interview
Recent 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
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
ps
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
Graph Homomorphisms with Complex Values:
A Dichotomy Theorem
pdf
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
"格物、致知、诚意、正心、修身、齐家、治国、平天下" ---Confucius
WebCounter
says that you are visitor number
since June 9, 2004.
