Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Probabilistic Aspects of Computer Science
(48h, 6 ECTS)

In charge: Serge Haddad (LSV, ENS Cachan).

Lecturers

2017-2018

  • Serge Haddad (lectures)
  • XXX (exercices)
  • Anne Bouillard (lectures and exercises)

2016-2017

2015-2016

2012-2014

2011-2012

2010-2011

Language

The default language of the teachers is French.
But the lectures may be given in English if attended by non French-speaking and English-speaking students.

Motivations and main objectives

Probability occurs more and more often in computer science
both to address the modelling and simulation of systems where the specification is incomplete,
to design efficient (yet simple) algorithms, to study the robustness of security protocols agains attack, etc.
The goal of this course is to cover several of these aspects in order to show the versatility
of the probability applied to computer science. Every part of this course is intended
to be a introduction revealing ideas, principles and techniques while more elaborated
techniques will be described in M2 courses.

Short description

The course is divided in several parts:

  • Discrete Time Markov Chains
    • Discrete event systems
    • Renewal processes with arithmetic distribution
    • Discrete time Markov chains
    • Finite discrete time Markov chains
  • Continuous Time Markov Chains
    • Renewal processes with non arithmetic distribution
    • Continuous time Markov chains
    • Finite continuous time Markov chains
  • Markov Decision Processes
    • Presentation
    • Finite horizon analysis
    • Discounted reward analysis
    • Average reward analysis
  • Probabilistic Automata
    • Presentation
    • Properties of stochastic languages
    • Decidability results
  • Randomized Algorithms
    • Introduction and definitions
    • Better than deterministic: saving time and space (Min-cut, AND/OR trees)
    • Yao's principle: optimal randomized algorithms (Hard-drive consumption optimization)
    • Search for positive certificates: polynomial identity testing,...
    • Auto-correction of buggy codes: matrix multiplication
    • Random solution and LP-rounding for Max-SAT
    • Random walks for k-SAT
    • Constant-time approximation scheme
    • Connections with greedy algorithms: conditional expectation method (Max-Cut)
  • Random Graphs
    • The probabilistic method
    • Erdös-Rényi graphs: definition, almost sure properties, the threshold phenomenon and the emergence of the giant component.
    • Complements (chosen among): configuration model and preferential attachment graphs, routing in small-world graphs...

Exams

The examination questions will be in French and/or in English depending on the requests.
Students may write their answers in French or in English.

Part 1 and 2: Markovian models

Part 3 and 4: Randomized Algorithms & Random Structures

Archives

2016-2017: Randomized Algorithms & Random Structures

  • Lecture 1 [8.11.2016]
  • Lecture 1A [14:00-16:00] Introduction to randomized algorithms
    • Definition
    • A first example: Randomized Min-Cut
    • Exercise session 1A PDF
      1. Faster randomized Min-Cut
  • Lecture 1B [16:15-18:15] Introduction to random graphs
    • Random graphs Gn,p
    • Phase transitions & threshold function
    • Threshold function for the emergence of K4
    • Exercises session 1B PDF
      1. :!: Graph of arbitrary Girth and Chromatic number
      2. Triangles in Gn,p
      3. Branching processes in continuous time
  • Lecture 2 [15.11.2016]
  • Lecture 2A [14:00-16:00] Faster randomized algorithm for Min-Cut
    • Fast randomized Min-Cut
    • Exercice session 2A PDF
      1. Derandomization:
        1. :!: Conditional expectation method
        2. Small k-wise independent randomized variables spaces
  • Lecture 2B [16:15-18:15] Emergence of the giant connected component (1)
    • Intuition
    • Galton-Watson branching process
    • Exponential generating function of a random variable
    • Evaluating the extinction probability
    • No exercise session
  • Lecture 3 [22.11.2016]
  • Lecture 3A [14:00-16:00] Yao's principle Lecture Notes
    • Zero sum game & von Neumann's Minimax theorem
    • Application to lower bounding randomized algorithms: Yao's principle
    • An example: Hard drive energy saving
    • Exercice session 3A PDF
      1. :!: Optimal NAnd Tree evaluation (Yao's principle)
  • Lecture 3B [16:15-18:15] Emergence of the giant connected component (2)
    • Extinction probability for GW Branching processes
    • Conjugated processes: distribution of the extincted components
    • Exercises session 3B HW1
      1. Branching processes in continuous time
  • Lecture 4 [29.11.2016]
  • Lecture 4A [14:00-16:00] Streaming Algorithms
    • Introduction to streaming algorithms
    • Counting up to n using log log n bits
    • (ε,δ)-estimator
    • Exercises session 4B HW4
      1. Streaming algorithm for counting triangles
  • Lecture 4B [16:15-18:15] Emergence of the giant connected component (3)
    • Extinction probability for GW branching processes when c>1
    • Poisson law Pois(c) is the limit of Binomial law Binom(n,c/n)
    • All connected components have size O(log n) in Gn,p when p≤c/n with c<1
    • Exercises session 4B HW4
      1. :!: Occurences of small subgraphs in Gn,p
  • Lecture 5 [6.12.2016]
  • Lecture 5A [14:00-16:00] Streaming Algorithms 2
    • Evaluating F2 using O(log n+log m) bits
    • k-wise independent hash function
    • Exercises session 5A HW5
      1. :!: FPT algorithm for spotting k disjoint triangles
  • Lecture 5B [16:15-18:15] Emergence of the giant connected component (4)
    Lecture notes
    • Emergence of the giant component when c>1
    • The distribution of the connected components outside the giant component Poisson law when c>1
  • Lecture 6 [13.12.2016]
  • Lecture 6A [14:00-16:00] Testing, Checking, Auto-correcting Algorithms
    • Checking algorithms for matrix multiplication
    • Auto-correcting algorithm for integers multiplication
    • Checking algorithm for integer multiplication
    • Linearity testing and auto-correcting
  • Lecture 6B [16:15-18:15] Algorithmic approach to the Small world phenomenon
    Original article PDF
    • S. Milgram's experiment
    • J. Kleinberg's random graph model Gα and decentralized routing algorithms
    • Links are too short when α > 2
    • Links are too messy when α < 2
    • Greedy routing routes in O(log2 n) hops when α = 2

2015-16: Parts 3 & 4: Randomized Algorithms and Random Structures

Lecture 1 [25 nov. 2015]

Lecture 1A: WalkSat
  • SAT: NP-completness, exact resolution
  • A first dummy randomized algorithm
  • WalkSAT algorithm for 3-SAT
Lecture 1B: Phase transition in Random 2-SAT
  • Introduction: phase transitions in Random SAT
  • Random 2-SAT
  • Random 2-SAT are SAT almost surely when p < 1/2n
Exercises session 1A&B: PDF Solutions
  1. WalkSAT for 2-SAT
  2. Phase transition in Random 1-SAT

Lecture 2 [2 dec. 2015]

Lecture 2A: Yao principle: Application to Hard Drive energy saving
  1. The hard drive energy saving problem
  2. Best deterministic algorithm
  3. Randomized algorithms: definition and performance evaluation
  4. Yao principle and von Neumann's minimax theorem
Lecture 2B: Transition de phase dans Random 2-SAT II: the case where p ≥ c/2n with c>1
  1. Recall on the phase transition
  2. Recall on the directed graph associated to 2-SAT, formula: UNSAT ⇔ there is a x s.t. x and ¬x belong to the same strongly connected component
  3. Scheme of the proof: growth of the neighborhood from a litteral to get √n litterals, then existence of an arc
  4. Branching processes: Galton-Watson processus, definition
  5. Probabilitic toolbox
    1. Markov's inequality
    2. Chebychev's inequality
    3. Second moment method
  6. Growth and extinction of the Galton Watson process
Exercises session 2A&B: PDF Solutions
  1. Optimal randomized algorithm for the hard drive energy saving problem using Yao's principle

Lecture 3 [9 dec. 2015]

Lecture 3A: Streaming algorithms: introduction and a loglog-counter (computing F1)
  1. Introduction to Streaming algorithms
  2. Frequencies & Moments of a stream
  3. Evaluating F1: an (ε,δ)-estimator for a O(loglog n)-counter
Lecture 3B: Phase transition in Random-2SAT III (End)
  1. Recalls on Galton-Watson branching processes
  2. Random-2SAT is almost surely UNSAT for c > 1 (End)
Exercises session 3A&B: PDF Solutions
  1. F0: (ε,2/(1+ε))-estimator (to be continued in Exercise session 4) :!:
  2. Generating function for Galton-Watson processes
  3. Generating function for the total population number in Galton-Watson processes (to be continued in Exercise session 4)
  4. Galton-Watson branching process with continuous lifetime and birthrate (to be continued in Exercise session 4) :!:

Lecture 4 [12 dec. 2015] - Vidéos: A B C D

Lecture 4A: Streaming algorithms: F2 and Families of k-wise independent hash functions
  1. Evaluating F2
  2. k-wise independent Hash functions family
Lecture 4B: Galton-Watson branching process extinction (end)
  1. Generating function of a random variable
  2. Extinction probability of a Galton-Watson branching process
No new exercises session: see 3A&B

Lecture 5 [16 dec. 2015]

Lecture 5A: Interactive proofs, self-reduction, program checking and self-correction
  1. A little bit of history
  2. Program checking: multiplication, graph isomorphism
  3. Self-reduction, Average-case hardness, & Program self-correction: multiplication, permanent
Lecture 5B: Random graphs: emergence of the giant connected component
  1. Definition of G(n,p)
  2. No large connected components for p ≤ c/n with c <1
  3. Emergence of the large connected component for p ≥ c/n with c > 1
  4. Duality principle in Galton-Watson branching process:
    1. distribution of the size of the tree conditioned on extinction
    2. relation to the size of giant connected component
Exercises session 4A&B: PDF Solutions
  1. Using fingerprints to check matrix multiplication
  2. FPT algorithm for spotting k disjoint triangles
  3. Binomial laws composition
  4. Prüfer sequences to encode unrooted labelled trees

Lecture 6 [5 jan. 2016]

Lecture 6A: Interactive proofs, self-reduction, program checking and self-correction (II)
  1. A little bit of history
  2. Program checking: interactive proof for the permanent Lecture's document
  3. The «little» PCP theorem: NP ⊆ PCP(poly(n),1) Lecture's document
    1. PCP(r,q)-verifier & the PCP class
    2. Walsh-Hadamard codes
    3. Linearity testing & Fourier transforms of Boolean functions
    4. NP-completeness of QUADEQ
    5. A PCP(n2,1)-verifier for QUADEQ

== Lecture 5B: The smallworld phenomenon: phase transitions for algorithms

  1. Milgram's experiment
  2. Kleinberg's model (2000): the random augmented grid model Kα & the decentralized algorithms
  3. Phase transition for finding paths to a destination with decentralized algorithms Lecture's document
    1. Phase I: when α<2, the links are too messy and decentralized paths have polynomial lengths
    2. Phase III: when α>2, the links are too shorts and decentralized paths have polynomial lengths
    3. Phase II: when α=2, the greedy decentralized algorithms find path of length O(log2 n)

Prerequisites

  • Basic Algorithms (level L3)
  • Finite Automata. (level L3)
  • Basics of probability.

Related courses

  • 2.8 Foundations of real time systems verification
  • 2.11.1 Advanced algorithmics and complexity
  • 2.11.2 Randomness in Complexity
  • 2.15 Analysis of algorithms
  • 2.17.1 Foundations of network models
  • 2.29.1 Graph algorithms
  • 2.34.1 Using randomness in computer science

Bibliography

  • Part 1
    • FELLER W. An Introduction to Probability Theory and Its Applications, Vol. 1 and 2 Wiley
    • FOATA D., FUCHS A. Calcul des probabilités, cours et exercices corrigés Dunod
    • FOATA D., FUCHS A. Processus stochastiques Dunod
  • Part 2
    • PUTERMAN M.L. Markov Decision Processes Wiley
    • PAZ A. Introduction to probabilistic automata New York, Academic Press
  • Part 3 (Random structures)
    • BOLLOBAS B. Random Graphs Academic Press
    • ALON, N. and SPENCER J. The probabilistic method, John Wiley
    • DRAIEF, M. and MASSOULIE L. Epidemics and Rumours in Complex Networks, Cambridge University Press
  • Part 4 (Randomized algorithms)
    • MITZENMACHER Michael, UPFAL Eli. Probability And Computing : Randomized Algorithms And Probabilistic Analysis, 2005.
    • MERTENS Stephan, MOORE Cristopher. The nature of computation, Oxford University Press, 2011.
    • VAZIRANI Vijay, Algorithmes d’approximation, Springer (traduit de l’américain par Nicolas Schabanel), 2006.
    • ARORA Sanjeev, BARAK Boaz. Computational complexity, Cambridge University Press, 2010.
    • ALON Noga. The probabilistic method, John Wiley & Sons, 2000.
    • MOTWANI Rajeev, RAGHAVAN Prabhakar. Randomized Algorithms, Cambridge University Press, 1995.

Archives

[2014/2015] Randomized algorithms by N. Schabanel

  • Lecture 1 [18/11/2014] Introduction to randomized algorithm
    • Definitions and analysis

    • A first example: loglog-counters and (ε,δ)-estimators PDF
    • A simple randomized algorithm for Min-Cut PDF

  • Exercises session 1 PDF
    1. A (3/2)n-time constraint-based randomized exact algorithm for 3-SAT

    2. A faster Min-cut algorithm

  • Lecture 2 [25/11/2014] Lower bounds on randomized algorithms: Yao's principle
    • From von Neumann's Min-Max theorem to Yao's principle

    • Application to online algorithms: hard drive energy saving competitive algorithm
  • Exercises session 2 PDF
    1. Random cut for the Max Cut problem and its derandomization by the conditional expectation method

    2. Yao's principle: Optimal randomized algorithm for the evaluation of NAND-tree 

  • Lecture 3 [2/12/2014] Lower bounds on randomized algorithms: Yao's principle (2)
    • Application to online algorithms: hard drive energy saving competitive algorithm (2)

  • Exercises session 3 PDF
    1. Random cut for the Max Cut problem and its derandomization by the conditional expectation method

    2. FPT algorithms for spotting k disjoint triangles 

  • Lecture 4 [9/12/2014] Introduction to streaming algorithms Lecture Notes
    • Introduction to streaming algorithm

    • A streaming algorithm for computing the second moment F2 with a random hash function

    • Families of k-wise independent hash functions 

    • A streaming (ε,δ)-estimator for F2 with Oε,δ(log m + log n) bits of memory

  • Exercises session 4 PDF
    1. Generating n pairwise independent uniform random bits from log2(n) uniform (truly) independent random bits

    2. A streaming (c-1,1/c)-estimator with c > 1 for the number of distinct values in a stream using O(log m) bits of memory

  • Lecture 5 [16/12/2014] Lower bounds for streaming algorithms & Communication complexity
    • Deterministic streaming algorithm for detecting palindromes?

    • Introduction to communication complexity 

    • Communication complexity is a lowerbound on memory for streaming algorithms

    • Rectangles in communication complexity

    • Communication complexity of palindrome recognition, optimal deterministic streaming algorithm

    • Fingerprints: randomized streaming algorithm for palindrome recognition 

  • Exercises session 5 PDF
    1. Uniformity detection

    2. Using fingerprints to check matrix multiplication [ to return on Jan. 6, 2014 ]

  • Lecture 6 [06/01/2015] Walk-SAT & Derandomization
    • O(1.33...n)-time Walk-SAT algorithm for 3-SAT

    • The conditional expectation derandomization method for Max-Cut (Exercise 1 in HW2) 


Randomized Algorithms (Nicolas Schabanel, 2013-14)

Lecture 1: Thursday Jan 23, 8:45-11:45 Video

  1. Introduction to randomized algorithms
  2. LogLog Counters
  3. (ε,δ)-estimators
  4. Minimum Cut randomized algorithm
Exercise session 1: First randomized algorithms PDF
  1. Fast Minimum Cut randomized algorithm
  2. Dumb randomized algorithm for Max-Sat
  3. Constraint-based randomized algorithm for 3-Coloring

Lecture 2: Thursday Jan 30, 8:45-11:45 - Approximation algorithms & Randomized Rounding Video

  1. Random solution for Max-SAT
  2. Linear program relaxation for Max-Sat and its randomized rounding
  3. Mixing both algorithms yields a better one
Exercise session 2: Randomized rounding PDF
  1. Semi-definite programming for Max-Cut and cut by a random hyperplane
  2. Randomized rounding of a linear program relaxation for Set-Cover

Lecture 3: Thursday Feb 6, 8:45-11:45 - Streaming, Property testing, Self-correction Video

  1. A streaming algorithm for computing the second moment of frequencies F2 : 4-wise independent hash functions
  2. Self-correcting integer product
Exercise session 3: PDF
  1. A Fixed Parameter Tractable algorithm for finding k disjoints triangles
  2. A deterministic algorithm for uniformity detection
  3. Matrix multiplication testing

Lecture 4: Thursday Feb 13, 8:45-11:45 - Expander graphs Video

  1. Expansion: Combinatoric definition
  2. Expansion: Spectral definition
  3. Cheeger inequalities and first applications
  4. Expander constructions: Examples and Zig-Zag product
Exercise session 4: PDF
  1. Zig-zag product and explicit expander construction
  2. Graph constraints satisfaction Gap-problem: Degree uniformization step
  3. Random walks on expanders are almost sequences of independent trials

Randomized algorithms (Nicolas Schabanel, 2012-13)

Cours n°1: Mardi 30 Oct. 2012 - 16:30-19:30 Vidéo
  1. Introduction aux algorithmes randomisés
  2. Un algorithme randomisé pour Min-Cut
Séance d'exercices n°1: Solutions aléatoires et dérandomisation PDF
  1. Analyse d'une partition aléatoire pour Max-Cut
  2. Dérandomisation par la méthode de l'espérance conditionnelle
  3. Dérandomisation par la construction d'un espace probabilisé de bits uniformes 2-à-2 indépendants
  4. Généralisation à des bits uniformes k-à-k indépendants
Cours n°2: Mardi 6 Nov. 2012 - 16:00-19:00 Vidéo
  1. Fonctions booléennes, CNF et DNF
  2. L'algorithme Walk-SAT
Séance d'exercices n°2: Le principe de Yao & L'algorithme FastMinCut PDF
  1. Optimisation de la mise en veille d'un disque dur
    • Approche déterministe
    • Le principe de Yao
    • Un algorithme randomisé optimal
  2. L'algorithme de Karger-Stein (1993) pour Min-Cut
Cours n°3: Mardi 13 Nov. 2012 - 16:30-19:30 Vidéo
  • Comment débugger un programme sans rien connaître de son code ?
    1. Auto-correction d'une multiplication
    2. Test de linéarité, auto-correction de la linéarité, application au théorème PCP
Séance d'exercices n°3: Arrondi aléatoire en programmation linéaire PDF
  1. Approximation pour Max-SAT
    1. Instance aléatoire
    2. Arrondi LP
    3. Un mixte des deux
  2. Arrondi aléatoire pour Min-Set-Cover
Cours n°4: Mardi 20 Nov. 2012 - 16:30-19:30 Vidéo
  1. Fingerprint: identity testing
  2. Polynomial identity testing
  3. Pattern matching
Séance d'exercices n°4 PDF
  1. Traffic monitoring
  2. A constant-time approximation scheme (CTAS) for maximal matching size in constant degree graphs
 
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