Fine-Grained Complexity and Algorithms
Competency Goals: Students know the foundations of fundamental algorithmic barriers in the polynomial-time and exponential-time regimes.
They are able to use fine-grained reductions to relate the time complexity of different problems. They can derive conditional lower bounds from such reductions, based on established hardness assumptions.
Furthermore, they know about the techniques underlying the fastest known algorithms for central problems in the field.
Content:
- fine-grained reductions:
- conditional lower bounds
- main techniques for obtaining such reductions
- central hardness assumptions and their applications:
- (Strong) Exponential Time Hypothesis
- Orthogonal Vectors Hypothesis
- 3SUM Hypothesis
- APSP Hypothesis
- conditional lower bounds for string problems, algorithmic graph theory, geometry
- algorithmic techniques:
- fastest known algorithms for central problems (SAT, Orthogonal Vectors, 3SUM, APSP)
- polynomial method
- applications of fast matrix multiplication
- Fast Fourier Transform/polynomial multiplication