
Main topics
Teachers in 202021
Organization
8 lectures of 3 hours each (see schedule)
Lectures will be on Mondays mornings, 08:4511:45, room 1014 starting September 21.
Teaching mode will be on campus if possible, online with BBB otherwise:
October 26, November 2: Lectures will be held remotely. BBB link
November 9, 16 : Lectures will be held remotely. BBB link
Final exam in November 30 (usual time and room). The exam questions will be written in English. The answers may be written in French or in English, at the preference of the student taking the exam. All handwritten notes are allowed during the exam, as well as printouts of course notes provided on this webpage.
Probably one homework assignment will be given during the course.
For the exam you are allowed to access: your lecture notes and documents linked from the course web page. Please be aware that looking for answers on the internet would be unethical and also a waste of time.
The exam is individual: you are not allowed to communicate with other people, except for the three instructors.
Here is the procedure for the exam:

Each student acknowledges having received the exam in the BBB room. When all acknowledgements are received, the exam starts.
During the exam, the student either writes on a sheet of paper or in a file, using an editor with or without .tex, at their preference, while staying in the BBB room the whole time. You can ask questions on the BBB platform in the dialogue area.
Three hours later, the exam ends, each student takes pictures of their manuscripts or produces pdf files, and emails each file to the appropriate instructor (mdr@irif.fr for problems 1 and 2, claire.mathieu@irif.fr for problem 3, vladu@irif.fr for problem 4) with “MPRI exam problem number x” as subject title of the email.
Students stay in the BBB room until reception of their files is acknowledged by the instructors.
We study computational models in which data is only accessible through queries (Testing), data streams (Streaming algorithms), or online (Online algorithms). For those models, deterministic worst case analysis is often unsatisfactory, overly pessimistic, but randomization can make a big difference in performance. The common thread of the course is the use of randomness in algorithms and complexity. The goal may be to minimize the number of queries (Testing), the space used (Streaming), or the competitive ratio (Online). Some of the tools used are Communication Complexity (lower bounds), Linear Programming, and Continuous Optimization.
Property testing, Communication complexity, Streaming and Online algorithms (12h, 4 lectures bu Michel de Rougemont)
Complexity classes BPP, IP and PCP. Introduction to Testers and streaming algorithms. BlumLubyRubinfeld linearity test, proof with the discrete Fourier transform. Lecture notes.
Communication complexity, 1way, deterministic and randomized, public and private coins. Index and Disjointness are hard, using the distributional complexity. Lecture notes.
Tester for regular languages. Lower bounds for the number of queries for klinearity and monotonicity, using a reduction to Disjointness. Lecture notes.
Streaming algorithms: approximation of the F_0 and F_2 moments. $\Omega(n)$ space lower bounds for F_{\infty}. Online algorithms: Bipartite matching. Lecture notes.
Beyond Worst Case (12h, 2 lectures by Claire Mathieu and 2 lectures by Adrian Vladu)
The random order model for analyzing online algorithms. Secretary and Matroid secretary problems. Online facility location. Reference: Tim Roughgarden’s lecture notes.
Pricing with an unknown distribution with bounded valuations and application to auctions. Instance optimality, definition and analysis.
Online paging. Competitive algorithms, deterministic and randomized. From discrete to continuous – weighted online paging via mirror descent. Further reading: lecture notes, paper.
Sparse recovery. Recovering a sparse signal from few measurements via iterative methods, iterative hard thresholding. General framework – minimizing convex functions over nonconvex domains. Matrix completion. Further reading: slides, paper, Wikipedia page
On Monday mornings, 08:4511:45, room 2035 on campus if possible, online with BBB otherwise:
Some lectures will be in English, and others in French with English upon request. Homework assignments and exams will be available in English and can be written in either English or French.
The following is a coherent list of courses on the thematic 'Algorithms and Complexity'.
Basics of complexity theory (classes P, NP, etc.) and of undergraduatelevel algorithms.
Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995
Computational complexity: A modern approach, by Sanjeev Arora and Boaz Barak, Cambridge University Press, 2010
Data Stream Algorithms  Lecture notes, by Amit Chakrabarti, 2015, PDF file
Communication Complexity  Lecture notes, by Amit Chakrabarti, 2019, PDF file
Lecture Notes on Property Testing, by Oded Goldreich URL
Beyond the WorstCase Analysis of Algorithms, by Tim Roughgarden, 2020
S. Laplante  PR  Paris 7  IRIF 
F. Magniez  DR  CNRS  IRIF 
C. Mathieu  DR  CNRS  IRIF 
S. Périfel  MC  Paris 7  IRIF 
A. Rosen  DR  CNRS  IRIF 
M. de Rougemont  PR  Paris 2  IRIF 
A. Vladu  CR  CNRS  IRIF 
