Course Identification

Fine-Grained Complexity
20244172

Lecturers and Teaching Assistants

Dr. Amir Abboud, Dr. Nick Fischer
N/A

Course Schedule and Location

2024
Second Semester
Wednesday, 14:15 - 16:00
12/04/2023
10/07/2024

Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Lecture; Elective; Regular; 3.00 points
Chemical Sciences: Lecture; 2.00 points

Comments

The course will take place in Ziskind, Rm 155

Prerequisites

A basic course in algorithms and in complexity theory.

Restrictions

50

Language of Instruction

English

Attendance and participation

Expected and Recommended

Grade Type

Numerical (out of 100)

Grade Breakdown (in %)

50%
50%

Evaluation Type

Take-home exam

Scheduled date 1

N/A
N/A
-
N/A

Estimated Weekly Independent Workload (in hours)

8

Syllabus

Whereas traditional complexity theory classifies problems into polynomial time solvable (easy) or NP-hard, a more modern complexity theory aims to achieve a more fine-grained classification. For example, we'd like to know if the time complexity is near-linear or quadratic? This is motivated by the fact that, with the growing sizes of data, even quadratic time can be impractical. 

This course will present the current approach for obtaining fine-grained complexity results: we start with a small set of conjectures (similar to P \neq NP) about the exact complexity of certain core problems and devise a host of combinatorial reductions to achieve fine-grained lower bounds for many other problems.

The course will cover:
- The main conjectured-to-be-hard problems, what we know about them algorithmically, and how to reduce them to other problems. These problems include: k-SAT, 3-SUM, All-Pairs Shortest Paths, and k-Clique.
- Various examples of fine-grained results for important problems on strings (e.g. Edit-Distance), graphs (e.g. Diameter), and geometric data (e.g. Closest Pair).
- Other topics such as hardness of approximation, parameterized complexity, and barriers for reductions.

Learning Outcomes

1. Whereas a basic course in complexity theory provides the students with tools to prove whether a problem that they encounter is in P or not (assuming P \neq NP), this course provides them with tools to prove whether a problem is in near-linear time or probably not (assuming certain conjectures).

2. Familiarity with the most basic computational problems that are not known to be solvable in near-linear time.

3. Ability to understand state of the art research in fine-grained complexity.

Reading List

N/A

Website

N/A