Abstract
What do Siegel's theorem on finiteness of integer solutions have to do with complexity theory? In this talk we discuss a complexity dichotomy theorem for counting problems, which are expressible as certain Sum-of-Product computations. The space of problems are parametrized by local constraint functions, which are expressible as tensors. 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. 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 statement of Siegel's theorem with respect to some specific polynomials 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 and Eulerian partitions, 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.