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

This is an old revision of the document!

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

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

### Course Outline 2019-2020

Main topics

• Property testing, Communication complexity, Streaming algorithms (12h)
• Probabilistic checkable proofs (6h)
• Stable matchings (6h)

Teachers in 2019-20

Organization

• 8 lectures of 3 hours each (see schedule)
• Lectures will be on Mondays, 16:15-19:15, room 1014 starting September 16th
• Final exam in November (date and location to be announced). All handwritten notes are allowed during the exam, as well as course notes provided on this webpage
• Probably one homework assignment will be given during the course.

### Objectives

We present a framework to approximate decision problems, solutions of optimization problems and properties of these solutions. Data could be in some case only accessible through queries or data streams. In that case, instead of minimizing time complexity only, we also want to minimize the number of data queries or the amount of internal memory for processing the data stream.

Communication complexity provides lower bounds for some classical problems and we obtain optimal algorithms in some cases. The PCP theorem is a characterisation of NP where certificates are verified in a very efficient probabilistic manner. It enables in particular to show that certain problems cannot be approximated in polynomial time unless P=NP. We will see these applications as well as the proof of the theorem.

### Lectures Outline

1. Property testing, Communication complexity, Streaming algorithms (12h)
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.
3. Tester for Monotonicity, Tester for regular languages. Lower bounds for the number of queries for k-linearity and monotonicity, using a reduction to Disjointness.
4. Streaming algorithms: approximation of the F_0 et F_2 moments. Graph properties, dense subgraphs. $\Omega(n)$ space lower bounds for F_{\infty} and for the densest subgraph.
2. Probabilistic checkable proofs (6h)
1. Probabilistically checkable proofs. PCP theorem statement. Application to inapproximability (3SAT, Vertex Cover…). Tools for the proof: expanders, error correcting codes… Beginning of the proof.
2. Proof of PCP theorem: gap amplification (Dinur), alphabet reduction.
3. Stable matchings (6h)
1. Stability definition. Algorithm of Gale and Shapley. Properties : stability, manipulability, matched set, time complexity. Restrictions and variants : lengths of lists, capacities.
2. Stochastic models and probabilistic analysis.

### Schedule

On Mondays, 16:15-19:15, room 1014:

• September 16: MdR (1.I)
• September 23, 30: SP (2.I, 2.II)
• October 7, 14, 21: MdR (1.II, 1.III, 1.IV)
• October 28, November 4: CM (3.I, 3.II)

### 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.).

### 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
• Complexité algorithmique, by Sylvain Périfel URL with electronic version
• 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

### É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

Universités partenaires
Établissements associés