From Galois, Puiseux and Siegel to a complexity dichotomy theorem
11:00 AM - 12:00 PM, Friday Feb. 10, 911 Van Vleck
I will describe briefly the complexity classification program for counting problems. This theory classifies every problem in a broad class of problems expressible as Sum-of-Product computations into either polynomial time computable or #P-hard. Then I will describe a concrete problem called Edge-Coloring: Given a graph G, count the number of valid edge colorings of G. The complexity of this problem was open for some decades. (It is known that over planar 3-regular bridgeless graphs the existence of 3-edge coloring is equivalent to the 4-Color Theorem. The decision complexity is "known" in the sense that the 4-Color Theorem is known.) We will present a classification theorem for a class of problems; Edge-Coloring is one point in that space of problems. I will describe several steps in the proof of this theorem, including: (1) Use Puiseux series to show that certain integral bivariable polynomial has a specific finite set of integer solutions, which is an effective version of Siegel's Theorem, (2) Determine the Galois groups of a family of polynomials using (1), and (3) Show that a certain lattice condition is satisfied using (2). Joint work with Heng Guo and Tyson Williams.