Abstract
This talk offers an introduction to the fine-grained complexity of counting problems. We review some known results from the polynomial time world, and we survey some known exact algorithms as well as hardness results under the counting version of the exponential time hypothesis (#ETH). Some problems we discuss are the permanent, computing the number of perfect matchings, counting satisfying assignments of k-CNF formulas, evaluating the chromatic and the Tutte polynomial, and counting solutions in constraint satisfaction problems (CSPs). On the hardness side, we delineate the block interpolation framework due to Curticapean (2015), which allows us to use polynomial interpolation to prove #ETH-hardness results.