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

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. LaplantePRParis 7IRIF
F. MagniezDRCNRSIRIF
C. MathieuDRCNRSIRIF
S. PérifelMCParis 7IRIF
A. RosenDRCNRSIRIF
M. de RougemontPRParis 2IRIF
 
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