Topics in theoretical computer science
Summary
The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of fundamental questions that underlie some of the key problems of modern computer science.
Content
This course develops a broad toolbox of techniques for designing and analysing algorithms for difficult combinatorial optimization problems. Rather than treating each technique in isolation, the course studies them through a common running example, set cover, making it possible to compare different algorithmic ideas, analyses, and guarantees within a clean and unified framework. Students will learn not only how these methods work, but also how to recognize when they are useful and how to transfer them to more complex problems.
Topics may include greedy algorithms and charging arguments; local search and non-oblivious potential functions; linear-programming relaxations and integrality gaps; deterministic and randomized rounding, including threshold rounding and exponential-clock techniques; structural integrality results, such as total unimodularity and methods based on VC dimension; linear-programming duality; dual fitting, primal-dual algorithms, and complementary slackness; multiplicative-weights methods; and online algorithms in adversarial and random-order models.
The course will also cover approximation-preserving reductions and hardness of approximation. In particular, we will introduce the PCP theorem and explain how PCP-based reductions are used to prove limits on the approximation guarantees achievable by polynomial-time algorithms.
The emphasis is on the main ideas underlying each technique, on rigorous approximation and competitive guarantees, and on understanding the relationships between apparently different algorithmic approaches. Set cover serves as the principal running example, but the techniques are intended as reusable tools for a much wider range of optimization problems. The planned material follows the organization of the developing course monograph, including combinatorial algorithms, LP rounding, duality, online algorithms, and hardness of approximation.
Keywords
Approximation Algorithms, Combinatorial Optimization, Greedy Algorithms, Local Search, Linear Programming, Randomized Rounding, LP Duality, Primal-Dual Algorithms, Multiplicative Weights, Online Algorithms, PCP Theorem, Hardness of Approximation, Set Cover
Learning Prerequisites
Required courses
Bachelor-level courses in algorithms, discrete mathematics, and probability, together with mathematical maturity.
Students should be comfortable with:
- Basic algorithm design and analysis;
- Discrete probability and expected-value arguments;
- Elementary linear algebra.
Prior knowledge of linear programming is useful but not required; the relevant concepts will be introduced in the course.
Recommended courses
CS-250 Algorithms I, MATH-232 Probability and statistics (for IC), or equivalent courses.
Learning Outcomes
By the end of the course, the student must be able to:
- Design and analyse deterministic and randomized rounding algorithms
- Analyze online algorithms using competitive analysis
- Analyze approximation guarantees and construct examples showing that an analysis is tight
- Explain how PCP-based reductions yield hardness-of-approximation results
- Recognize and apply major algorithm-design paradigms such as greedy algorithms, local search, LP rounding, and primal-dual methods
- Elaborate on related research questions
- Formulate suitable linear-programming relaxations for combinatorial optimization problem
- Use LP duality, dual fitting, and complementary slackness in approximation analyses
- Apply a technique studied in class to a new or more complex optimization problem
Teaching methods
Ex cathedra, homeworks, reading
Expected student activities
Attendance at lectures, completing exercises, independent project, reading written material
Assessment methods
- Continuous control
Supervision
| Office hours | Yes |
| Assistant.e.s | Yes |
| Others | Electronique forum : Yes |
Resources
Bibliography
Ressources en bibliothèque
Moodle Link
Dans les plans d'études
- Semestre: Automne
- Forme de l'examen: Pendant le semestre (session d'hiver)
- Matière examinée: Topics in theoretical computer science
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Automne
- Forme de l'examen: Pendant le semestre (session d'hiver)
- Matière examinée: Topics in theoretical computer science
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Automne
- Forme de l'examen: Pendant le semestre (session d'hiver)
- Matière examinée: Topics in theoretical computer science
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Automne
- Forme de l'examen: Pendant le semestre (session d'hiver)
- Matière examinée: Topics in theoretical computer science
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Automne
- Forme de l'examen: Pendant le semestre (session d'hiver)
- Matière examinée: Topics in theoretical computer science
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Automne
- Forme de l'examen: Pendant le semestre (session d'hiver)
- Matière examinée: Topics in theoretical computer science
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Automne
- Forme de l'examen: Pendant le semestre (session d'hiver)
- Matière examinée: Topics in theoretical computer science
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Automne
- Forme de l'examen: Pendant le semestre (session d'hiver)
- Matière examinée: Topics in theoretical computer science
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Automne
- Forme de l'examen: Pendant le semestre (session d'hiver)
- Matière examinée: Topics in theoretical computer science
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- Type: optionnel