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/22 22:29]
magniez
cours:c-2-11-2 [2019/11/13 11:43] (current)
magniez [Course Outline 2019-2020]
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 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 36:
  
   - 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 46:
     - 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 ==== ==== Schedule ====
-  * September 9, 16, 23: MdR (1.I, 1.II, 1.III+On Mondays, 16:15-19:15room 1014: 
-  * September 30October 7: SP (2.I, 2.II) +  * September 16: MdR (1.I) 
-  * October 14: MdR (1.IV) +  * September 2330: SP (2.I, 2.II) 
-  * October 2128: CM (3.I, 3.II) +  * October 7, 14, 21: MdR (1.II, 1.III, 1.IV) 
 +  * October 28November 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