FINE-GRAINED COMPLEXITY

Course Description

For decades, the gold standard for "efficient" algorithms has been polynomial running time, and we have a (relatively) good understanding of which problems can be solved quickly under this metric. However, massive data sets are becoming more commonplace, which makes it imperative to revisit these problems and further improve our techniques. We show that speedups are possible for many problems, while others seem immune to any improvements. Using the conjectured “hardness” of the latter set, we prove (by means of reductions) that many other problems must also be “hard.”

This is a student-led colloquium led by Isaac Hair under the supervision of Daniel Lokshtanov