CS 598 TMC, Fall 2022

Algorithms from the Fine-Grained Perspective


Instructor

Timothy Chan (tmc "at" illinois.edu, office hours: Wed 12:30pm-1:20pm, Siebel 3230)

Meeting Time

Wed & Fri 11:00am-12:15pm, Siebel 1302

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.

Prerequisites: Solid background in algorithm design and analysis, at the level of CS 374. (CS 473 is not required, though some previous exposure to randomized algorithms might be helpful. Interested undergraduate students are welcomed, and may request for an UG petition.)

Course Work

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

See guidelines for presentation and project.

Outline

Lectures

(There is no textbook; I'll provide links to relevant papers below, and also scribbles from class. Lecture recordings may be accessed on mediaspace for registered students.)

Other Links

Statements on Anti-Racism, Mental Health, etc.