CS 598 TMC - Special Topics - Fine-Grained Algorithms

Campus: Urbana-Champaign

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.

Special Instructions:

All class meetings will be online and synchronous. Algorithms from the Fine-Grained Perspective. 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

Option 1

Course Level: Graduate

Credit: 4

Term(s): Fall