cours:c-2-11-2 [2019/07/12 18:31] magniez [Lectures Outline] |
cours:c-2-11-2 [2019/09/13 18:32] (current) magniez [Lectures Outline] |

| * [[https://www.irif.fr/~mdr/|Michel de Rougemont]] ([[https://www.irif.fr/|IRIF]]), 4 classes | | * [[https://www.irif.fr/~mdr/|Michel de Rougemont]] ([[https://www.irif.fr/|IRIF]]), 4 classes |

| | | |

- | | |

| Organization | | Organization |

| * **8 lectures of 3 hours each (see schedule)** | | * **8 lectures of 3 hours each (see schedule)** |

- | * Lectures will be on **??? starting at **??**:**??**** | + | * 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 | | * **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. | | * Probably one homework assignment will be given during the course. |

| | | |

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

| - Stability definition. Algorithm of Gale and Shapley. Properties : stability, manipulability, matched set, time complexity. Restrictions and variants : lengths of lists, capacities. | | - 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. | | - 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 ==== | | ==== Course Language ==== |

| | | |