
This is an old revision of the document!
Main topics
Property testing, Communication complexity, Streaming algorithms (12h)
Probabilistic checkable proofs (6h)
Stable matchings (6h)
Teachers in 201920
Organization
8 lectures of 3 hours each (see schedule)
Lectures will be on Mondays, 16:1519: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.
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.
Property testing, Communication complexity, Streaming algorithms (12h)
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.
Tester for Monotonicity, Tester for regular languages. Lower bounds for the number of queries for klinearity and monotonicity, using a reduction to Disjointness.
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.
Probabilistic checkable proofs (6h)
Probabilistically checkable proofs. PCP theorem statement. Application to inapproximability (3SAT, Vertex Cover…). Tools for the proof: expanders, error correcting codes… Beginning of the proof.
Proof of PCP theorem: gap amplification (Dinur), alphabet reduction.
Stable matchings (6h)
Stability definition. Algorithm of Gale and Shapley. Properties : stability, manipulability, matched set, time complexity. Restrictions and variants : lengths of lists, capacities.
Stochastic models and probabilistic analysis.
On Mondays, 16:1519: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)
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.).
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
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 
