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.

• Spyros Angelopoulos (CNRS and Sorbonne U., course supervisor)
• Christoph Dürr, CNRS and Sorbonne U.
• Adi Rosén, CNRS and U. of Paris

Language: English by default

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

1. [SA, Sep 15] Introduction to online computation and competitive analysis. Deterministic paging, upper and lower bounds. Introduction to randomized paging (topics from Chapters 3 and 4 in [BEY]). Homework 1.

2. [SA, Sep 22] Randomized paging. Online computation with predictions, in particular online set cover (see paper by Bamas et al.) Homework 2.

3. [SA, Sep 29] Continuing the analysis of online set cover. Combining online algorithms: paper by Mahdian et al. Homework 3

4. [SA, Oct 6] Predicting from expert advice: Section 2 in survey by Blum. Metrical task systems (MTS), and combining algorithms for MTS: mainly sections 2.2, 2.3 and 3 in this paper by Blum and Burch. Homework 4

5. [CD, Oct 13] The secretary problem and the postdoc problem. Homework 5 correction

6. [CD, Oct 20] Pandora's box. Lecture Notes Prophet inequalities. survey by Anupam Gupta single sample algorithm Homework 6

7. [CD, Oct 27] Graph Searching with Predictions Homework 7

8. [CD, Nov 3] Explorable uncertainty. Slides MST, scheduling with proc. time oracle, scheduling with testing, orienting hypergraphs

Grading scheme: 60% from the final exam, and 40% 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

- [Dec 1] final written exam. Personal lecture notes are allowed. But not books or printed articles.

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.

* [BEY] Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press 1998.

(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.