cours:c-2-11-2 [2019/09/13 18:32] magniez [Lectures Outline] |
cours:c-2-11-2 [2019/11/13 11:43] (current) magniez [Course Outline 2019-2020] |

| Organization | | Organization |

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

- | * Lectures will be on Mondays, 16:15-19:15, room 1014 starting September 16th | + | * 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 **25th **(**usual time **and **room**)****. The exam questions will be written in English. The answers may be written in French or in English, at the preference of the student taking the exam**. All handwritten notes are allowed during the exam, as well as **printouts of **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. |

| + | |

| + | |

| ==== Objectives ==== | | ==== Objectives ==== |

| | | |

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