From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting

Markus Hecher, Matthias Lanzinger

Counting problems are fundamental across mathematics and computer science. Among the most subtle are those whose associated decision problem is solvable in polynomial time, yet who…