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

# Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-11-2 [2019/09/13 18:32]
magniez [Lectures Outline]
cours:c-2-11-2 [2019/09/13 18:32] (current)
magniez [Lectures Outline]
Line 35: Line 35:
- Property testing, Communication complexity, Streaming algorithms (12h)   - Property testing, Communication complexity, Streaming algorithms (12h)
- Complexity classes  BPP, IP and  PCP.   Introduction to Testers and streaming  algorithms.  Blum-Luby-Rubinfeld linearity test, proof with the discrete Fourier transform. [[https://www.irif.fr/~mdr/cours1-2019.pdf|Lecture notes]]     - Complexity classes  BPP, IP and  PCP.   Introduction to Testers and streaming  algorithms.  Blum-Luby-Rubinfeld linearity test, proof with the discrete Fourier transform. [[https://www.irif.fr/~mdr/cours1-2019.pdf|Lecture notes]]
-    - Communication complexity, 1-way, deterministic and randomized,  public and private coins. Index and Disjointness are hard, using the distributional complexity. +    - Communication complexity, 1-way, deterministic and randomized,  public and private coins. Index and Disjointness are hard, using the distributional complexity. [[https://www.irif.fr/~mdr/cours2-2019.pdf|Lecture notes]]
-    - Tester for Monotonicity, Tester for regular languages. Lower bounds for the number of queries for k-linearity and monotonicity, using a reduction to Disjointness. +    - Tester for Monotonicity, Tester for regular languages. Lower bounds for the number of queries for k-linearity and monotonicity, using a reduction to Disjointness. [[https://www.irif.fr/~mdr/cours3-2019.pdf|Lecture notes]]
-    - 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.+    - 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. [[https://www.irif.fr/~mdr/cours4-2019.pdf|Lecture notes]]
- Probabilistic checkable proofs (6h)   - 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.     - Probabilistically checkable proofs. PCP theorem statement. Application to inapproximability (3SAT, Vertex Cover…). Tools for the proof: expanders, error correcting codes… Beginning of the proof.