Offerings from the Classification Program for Counting Problems


Jin-Yi Cai, University of Wisconsin

Monday, March 26th, 2018
114 Gates Hall at 4:00 pm


Suppose $\alpha$ and $\beta$ are two angles satisfying
$\tan(\alpha) = r  \tan(\beta)  > 0$, for some rational number $r > 1$.
Can both $\alpha$ and $\beta$ be rational multiples of $\pi$?

Let \[p(x,y) = x^5 - (2 y + 1) x^3 - (y^2 + 2) x^2 + y (y-1) x + y^3.\]
Is it true that for every integer $y \ge 4$, $p(x, y)$ is
an irreducible polynomial in $\mathbb{Q}[x]$, whereby we can determine
its Galois group?

We encounter questions like this in our quest to achieve complexity
classfications for counting problems.  In this talk I will outline
a proof to the first question (using character theory), and describe
at a high level how answers to such questions lead to complexity
dichotomy theorems.  Then I will give an overview of the status
of the Classification Program for Counting Problems, including
all partition functions for graph homomorphisms, counting constraint
satisfation problems, and Holant problems.