Advanced Algorithms
A foray into measured compromises.
When designing algorithms, we usually demand speed and accuracy on all inputs. This course explores what happens when we relax just one of these demands.
Themes
Coping Strategies
Core Techniques
Combined Strategies
Advanced Techniques
Hardness
Lower Bounds
- Hardness of Approximation
- ETH, SETH & Fine-Grained Complexity
- PCP Theorem & Unique Games
Course Runs
This course has been offered multiple times at IIT Gandhinagar. Each edition includes schedules, materials, and grading policies.
References
Parameterized Algorithms
Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh — Springer, 2015
Book websiteThe Design of Approximation Algorithms
Williamson & Shmoys — Cambridge University Press, 2011
Free PDF availableProbability and Computing
Mitzenmacher & Upfal — Cambridge University Press, 2017
Exact Exponential Algorithms
Fomin & Kratsch — Springer, 2010