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/07/12 18:31]
magniez [Lectures Outline]
cours:c-2-11-2 [2019/09/13 18:32] (current)
magniez [Lectures Outline]
Line 16: Line 16:
   * [[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. 
Line 35: Line 34:
  
   - 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.
Line 45: Line 44:
     - 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 ====
  
 
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