Visit ShanghaiTech University | 中文 | How to find us
HOME > News and Events > Events
Siegel's Theorem, Edge Colorings, and a Holant Dichotomy
Date: 2018/7/26             Browse: 44

Speaker:     Prof. Jin-yi Cai

Time:          16:00—17:00, July 26 

Location:    Room 1A-200, SIST Building

Host:          Prof. Xiuxiong Chen, IMS


What does Siegel's theorem on finiteness of integer solutions have to do with complexity theory? In this talk we discuss a new complexity dichotomy theorem for counting problems. Such a dichotomy is a classification of a class of problems into exactly two kinds: those that are polynomial time computable, and those that are NP-hard, and thus intractable. An example problem in this dichotomy is the problem of counting the number of valid edge colorings of a graph. We will show that an effective version of Siegel's theorem and some Galois theory are key ingredients in the proof of this dichotomy. Along the way we will also meet the Tutte polynomial, medial graphs, Eulerian orientations, Puiseux series, and a certain lattice condition on the (logarithm of) the roots of polynomials with integer coefficients.


Joint work with Heng Guo and Tyson Williams.


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 is an Editor of Journal of Computer and Systems Sciences (JCSS), an Editor of International Journal of Foundations of Computer Science, an Associate Editor ofJournal of Complexity, 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. A list of publications according to this web site.

SIST-Seminar 18069