Colloquium Details
Computational Complexity of Counting Edge Colorings
| Author: | Tyson Williams University of Wisconsin-Madison |
|---|---|
| Date: | March 10, 2015 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
Abstract
A fundamental goal in the study of counting problems is to give a complexity classification. A strong classification theorem takes the form of a dichotomy theorem, which classifies every problem in some large class to be either efficiently computable or intractable. In this talk, I will describe our classification program and, in particular, the resolution of the complexity of counting edge colorings, which solves a long-standing open problem. Some techniques used in our classification program include polynomial interpolation, Galois theory, and an effective variant of Siegel's theorem.
Biography
Tyson Williams is a Ph.D. candidate and Cisco Fellow in the Department of Computer Science at the University of Wisconsin-Madison under the mentorship of Jin-Yi Cai. His research interests concern the computational complexity of counting problems, with the primary goal of obtaining complexity dichotomy theorems. Publications by Tyson have appeared at leading theory of computing conferences, including STOC, FOCS, and ICALP. His work has also been invited to appear in two book chapters (to be published by CRC Press and Springer).