[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

THEORY SEMINAR

Jin-Yi Cai
University of Wisconsin – Madison
http://pages.cs.wisc.edu/~jyc
 
Title: “Siegel's Theorem, Edge Coloring, and a Holant Dichotomy”
 
Abstract: What do 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 #P-hard, and thus intractable. (For logicians, a complexity dichotomy theorem is a kind of restricted anti-Friedberg-Muchnick Theorem.) 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 (logarithms of) the roots of polynomials with integer coefficients.
 
Joint work with Heng Guo and Tyson Williams.
 
Host: Prof. Alexander Razborov
*Refreshments will be served prior to the talk in Ryerson 255*

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140326/5a1a90a9/attachment.htm