Course Websites

CS 598 TMC - Fine-Grained Algorithms

Last offered Fall 2022

Official Description

Subject offerings of new and developing areas of knowledge in computer science intended to augment the existing curriculum. See Class Schedule or departmental course information for topics and prerequisites. Course Information: May be repeated in the same or separate terms if topics vary.

Section Description

In undergraduate algorithms classes, you have studied classical problems such as all-pairs shortest paths, longest common subsequence, edit distance, 3SUM, subset sum, triangles in graphs, etc. Have you ever wondered whether the textbook algorithms you have 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, but in their "fine-grained" complexity (quadratic time? cubic time? etc.). We will describe the latest theoretical techniques for obtaining (slightly) improved algorithms for these classical problems and their variants (in general as well as important special cases). We will also prove conditional lower bounds via reductions that relate the fine-grained complexity of one problem to another. For up-to-date information about CS course restrictions, please see the following link:

Related Faculty

Fine-Grained AlgorithmsTMC70199S1541100 - 1215 W F  1302 Siebel Center for Comp Sci Timothy Moon-Yew Chan