Talks
Spring 2016
Fine-Grained Complexity Classification of Counting Problems
Monday, March 28th, 2016, 2:45 pm–3:15 pm
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.
Attachment | Size |
---|---|
Fine-Grained Complexity Classification of Counting Problems | 996.35 KB |