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

2017-2018

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

2016-2017

• Serge Haddad (lectures)
• XXX (exercices)
• Nicolas Schabanel (lectures and exercises)

2015-2016

• Serge Haddad (lectures)
• Emile Contal (exercices)
• Nicolas Schabanel (lectures and exercises)

2012-2014

• Serge Haddad (lectures)
• Emile Contal (exercices)
• Anne Bouillard (lectures and exercises)
• Nicolas Schabanel (lectures and exercises)

2011-2012

• Serge Haddad (lectures)
• Rohit Chadha (lectures)
• Malika Izabachene (exercises)

2010-2011

• Serge Haddad (lectures)
• Rohit Chadha (lectures)
• Céline Chevalier (exercises)

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.

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.

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...

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.

Handout

Page of the practical sessions

• 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 G_n,p
  • Phase transitions & threshold function
  • Threshold function for the emergence of K₄
  • Exercises session 1B PDF
    1. Graph of arbitrary Girth and Chromatic number
    2. Triangles in G_n,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 G_n,p when p≤c/n with c<1
  • Exercises session 4B HW4
    1. Occurences of small subgraphs in G_n,p

• Lecture 5 [6.12.2016]

• Lecture 5A [14:00-16:00] Streaming Algorithms 2
  • Evaluating F₂ 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(log² n) hops when α = 2

• SAT: NP-completness, exact resolution
• A first dummy randomized algorithm
• WalkSAT algorithm for 3-SAT

• Introduction: phase transitions in Random SAT
• Random 2-SAT
• Random 2-SAT are SAT almost surely when p < 1/2n

1. WalkSAT for 2-SAT
2. Phase transition in Random 1-SAT

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

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

1. Optimal randomized algorithm for the hard drive energy saving problem using Yao's principle

1. Introduction to Streaming algorithms
2. Frequencies & Moments of a stream
3. Evaluating F₁: an (ε,δ)-estimator for a O(loglog n)-counter

1. Recalls on Galton-Watson branching processes
2. Random-2SAT is almost surely UNSAT for c > 1 (End)

1. F₀: (ε,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)

1. Evaluating F2
2. k-wise independent Hash functions family

1. Generating function of a random variable
2. Extinction probability of a Galton-Watson branching process

1. A little bit of history
2. Program checking: multiplication, graph isomorphism
3. Self-reduction, Average-case hardness, & Program self-correction: multiplication, permanent

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

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

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(n²,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(log² n)

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

• 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

• 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.

• 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)ⁿ-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) 


1. Introduction to randomized algorithms
2. LogLog Counters
3. (ε,δ)-estimators
4. Minimum Cut randomized algorithm

1. Fast Minimum Cut randomized algorithm
2. Dumb randomized algorithm for Max-Sat
3. Constraint-based randomized algorithm for 3-Coloring

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

1. Semi-definite programming for Max-Cut and cut by a random hyperplane
2. Randomized rounding of a linear program relaxation for Set-Cover

1. A streaming algorithm for computing the second moment of frequencies F₂ : 4-wise independent hash functions
2. Self-correcting integer product

1. A Fixed Parameter Tractable algorithm for finding k disjoints triangles
2. A deterministic algorithm for uniformity detection
3. Matrix multiplication testing

1. Expansion: Combinatoric definition
2. Expansion: Spectral definition
3. Cheeger inequalities and first applications
4. Expander constructions: Examples and Zig-Zag product

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

1. Introduction aux algorithmes randomisés
2. Un algorithme randomisé pour Min-Cut

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

1. Fonctions booléennes, CNF et DNF
2. L'algorithme Walk-SAT

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

• 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

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

1. Fingerprint: identity testing
2. Polynomial identity testing
3. Pattern matching

1. Traffic monitoring
2. A constant-time approximation scheme (CTAS) for maximal matching size in constant degree graphs