*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

**Abstract:**
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.

.