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:28]
magniez [Lectures Outline]
cours:c-2-11-2 [2019/07/12 18:31] (current)
magniez [Lectures Outline]
Line 38: Line 38:
     - 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.
     - 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.
-    - Streaming algorithms: approximation of the $F_0et $F_2moments. 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.
   - 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.
     - Proof of PCP theorem: gap amplification (Dinur), alphabet reduction.     - Proof of PCP theorem: gap amplification (Dinur), alphabet reduction.
-  - Stable matchings (3h+  - Stable matchings (6h
-    - Définition de stabilitéAlgorithme de Gale et Shapley. Propriétés stabilitémanipulabilitéensemble mariécomplexité en temps. Restrictions et variantes longueurs de listescapacités+    - Stability definitionAlgorithm of Gale and Shapley. Properties stabilitymanipulabilitymatched settime complexity. Restrictions and variants lengths of listscapacities
-    - Modèles stochastiques et analyses probabilistes.+    - Stochastic models and probabilistic analysis.
 ==== 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