Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Algorithms and Uncertainty (24h, 3 ECTS)

☝ This course is suspended during the academic year 2022/2023.

Course Outline

In many settings such as routing calls in a network, scheduling jobs in processors, or even trading in the stock market, the decision-maker operates in a status of uncertainty. The objective of the course is to study algorithmic models, techniques, analyses, and approaches that have been developed specifically for dealing with this class of problems. The course is will be focused on the following specific aspects of computation under uncertainty:

  1. Online algorithms, in which the input is not known ahead of time;
  2. Regret minimization and online optimization in machine learning; and
  3. Recently introduced frameworks such as algorithms with predictions, and algorithms with explorable uncertainty.

The course will focus on the analytical/theoretical analysis of algorithms with uncertainty, but also on concrete applications.

Instructor team

Related courses within MPRI

The following is a list of courses related to the topics of Algorithms and Uncertainty. (To be updated)

Lectures and homeworks (will be updated as course progresses)

1. [SA, Sep 17] Introduction to online computation. Deterministic and randomized algorithms for the ski rental problem

2. [CD, Sep 24] Prophet inequality

3. [CD, Oct 1] Pandora’s box and the secretary problem.

4. [CD, Oct 8] Algorithms with explorable uncertainty.

5. [SA, Oct 15] Stochastic matchings, online matchings, and the Adwords problem.

6. [SA, Oct 22] Extensions of secretary problems.

7. [SA] Advice complexity of online algorithms. Online algorithms with untrusted and noisy advice.

8. [SA] Learning-augmented online algorithms.

Grading scheme and homework policy

Grading scheme: 50% from the final exam, and 50% from weekly homeworks.

Homework policy: Homeworks are due at the beginning of class. No late homework will be accepted, except for serious reasons (please notify the instructors in time). You should not collaborate with other students, and should not search the internet for similar problems. If you end up using any material outside notes, you must acknowledge your sources.

EXAM INFORMATION The exam will take place during the regular course hours on Friday, December 3rd. You are allowed to bring the handwritten notes you took during the class, printout of course slides, and papers that we have uploaded on the course web page. The following are NOT allowed: books, any papers other that those on the course web page, homework solutions.

Internships

We will propose internships early in the course. We urge all students who are interested to talk to the instructors as soon as possible. The internships will be related to the topics of research of the instructors and the lectures given in the course, or, more broadly, to the research interests of the instructors.

Reading material

* [DPV] S. Dasgupta, C.H. Papadimitriou, U. Vazirani, Algorithms, Mc Graw Hill, 2006 Book

* [Vaz] V. Vazirani, Approximation Algorithms, Springer, 2001 Book

Related courses outside of MPRI

(to be updated)

- Nikhil Bansal's course on “Algorithms and Uncertainty” at TU Eindhoven.

- Kamesh Munagala’s course on “Optimization and Decision Making under Uncertainty” at Duke University.

- Sebastien Bubeck’s and James Lee’s course on “Competitive analysis via Convex Optimization” at the University of Washington.

- Allan Borodin’s course on “Online Algorithms and Other Myopic Algorithms” at the University of Toronto.

- Nicole Megow’s course on “Algorithms and Uncertainty” at the University of Bremen.

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA