CS 598 TMC, Fall 2020

Algorithms from the Fine-Grained Perspective


Instructor

Timothy Chan (tmc "at" illinois.edu, office hours: Thu 3:00pm-4:00pm on zoom, or email me to meet at a different time)

Meeting Time

Wed & Fri 11:00am-12:15pm on zoom (email me if you are not officially registered but wants to attend)

Course Overview

In undergraduate algorithms classes, you have studied classical problems such as all-pairs shortest paths (APSP), longest common subsequence (LCS), edit distance, 3SUM, subset sum, triangles in graphs, etc. Have you ever wondered whether the textbook algorithms you learned could be improved, or whether they are in fact the best possible? Here, we are interested not just in determining whether the problems are polynomial-time solvable vs. NP-hard, but in their "fine-grained" complexity (quadratic time? cubic time? etc.). We will describe the recent theoretical techniques for obtaining (slightly) improved algorithms for these classical problems and their variants (in general as well as in important special cases). We will also prove conditional lower bounds via reductions that relate the fine-grained complexity of one problem to another.

Prerequisite: Solid background in algorithm design and analysis, e.g., at the level of CS 374. (Although CS473 is not required, some previous exposure to randomized algorithms will be helpful.)

Course Work

(Assignments, presentations, and projects may be done in groups of at most 3.)

Outline

Lectures

(There is no textbook; I'll provide links to relevant papers, and to scribbles from class. Lectures will be also recorded, and for registered students, recordings may be accessed at mediaspace on the "CS598TMC Fall 2020" channel.)

Other Links