Spring 2016

Fine-Grained Complexity Classification of Counting Problems

Monday, March 28th, 2016 2:45 pm3:15 pm

Add to Calendar

In this light-hearted talk, we will adopt the unconventional viewpoint that a "polynomial time" vs. "probably not polynomial time" dichotomy for a counting problem may not be a stopping point for further research on the same problem. We will survey different ways to classify the problem further by providing faster exponential-time algorithms, or by proving hardness results under hypotheses such as the exponential time hypothesis.