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/11/13 11:43] (current)
magniez [Course Outline 2019-2020]
Line 18: Line 18:
 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 ====
  
Line 35: Line 37:
   - 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.
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA