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.