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

## Randomness in Complexity (24h, 3 ECTS)

Course manager: Frédéric Magniez (IRIF)

### Course Outline 2020-2021

Main topics

• Property testing, Communication complexity, Streaming and online algorithms (12h)
• Beyond Worst Case (12h)

Teachers in 2020-21

Organization

• 8 lectures of 3 hours each (see schedule)
• Lectures will be on Mondays mornings, 08:45-11: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.

### IMPORTANT. Procedure for the exam on November 30, 8:45am

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:

1. The exam will take place remotely with students connected to the BBB room: https://bbb-front.math.univ-paris-diderot.fr/recherche/mic-lfh-5z7-arq. Students connect before 8:45am on Monday Nov 30. At 8:45am, the exam is emailed to all as a pdf file.
2. Each student acknowledges having received the exam in the BBB room. When all acknowledgements are received, the exam starts.
3. 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.
4. 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.
5. Students stay in the BBB room until reception of their files is acknowledged by the instructors.

### Objectives

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.

### Lectures Outline

1. Property testing, Communication complexity, Streaming and Online algorithms (12h, 4 lectures bu Michel de Rougemont)
1. Complexity classes BPP, IP and PCP. Introduction to Testers and streaming algorithms. Blum-Luby-Rubinfeld linearity test, proof with the discrete Fourier transform. Lecture notes.
2. Communication complexity, 1-way, deterministic and randomized, public and private coins. Index and Disjointness are hard, using the distributional complexity. Lecture notes.
3. Tester for regular languages. Lower bounds for the number of queries for k-linearity and monotonicity, using a reduction to Disjointness. Lecture notes.
4. 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.
1. Beyond Worst Case (12h, 2 lectures by Claire Mathieu and 2 lectures by Adrian Vladu)
1. The random order model for analyzing online algorithms. Secretary and Matroid secretary problems. Online facility location. Reference: Tim Roughgarden’s lecture notes.
2. Pricing with an unknown distribution with bounded valuations and application to auctions. Instance optimality, definition and analysis.
3. Online paging. Competitive algorithms, deterministic and randomized. From discrete to continuous – weighted online paging via mirror descent. Further reading: lecture notes, paper.
4. Sparse recovery. Recovering a sparse signal from few measurements via iterative methods, iterative hard thresholding. General framework – minimizing convex functions over non-convex domains. Matrix completion. Further reading: slides, paper, Wikipedia page

### Schedule

On Monday mornings, 08:45-11:45, room 2035 on campus if possible, online with BBB otherwise:

• September 21, 28
• October 5, 12
• October 26, November 2: Lectures will be held remotely. BBB link
• November 9, 16 : Lectures will be held remotely. |BBB link
• November 30: Exam (a priori remotely) will be available in English and can be written in either English or French. Students can access their notes as well as the class notes.

### Course Language

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.

### Relevant Courses

The following is a coherent list of courses on the thematic 'Algorithms and Complexity'.

### Pre-requisites

Basics of complexity theory (classes P, NP, etc.) and of undergraduate-level algorithms.

### Stages/Internships

Internships in the area of Randomized Complexity are available. Please contact the Algorithms and Complexity group of IRIF

### Bibliography

• 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 Worst-Case Analysis of Algorithms, by Tim Roughgarden, 2020

### Équipe pédagogique

 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

Universités partenaires
Établissements associés