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] |
| | - 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. |