
Parts 3 'Randomized Algorithms' & 4 'Random Structures' by Nicolas Schabanel will start on Tuesday 8/11/2016. Each 14:0018:15 session will be divided as follows:
14:0015:30 Lecture on Randomized Algorithms
15:3016:00 Exercise Session on Randomized Algorithms
16:0016:15 Pause
16:1517:45 Lecture on Random Structures
17:4518:15 Exercise Session on Random Structure
Between each session, we will be asked to solve one of the exercises for each part at home. Every homework is graded and the grades add up to 10 points. If HW denotes the total home work grades (over 10) and EX denotes the final exam grade (over 20), then the grade for the lecture will be:
Min(20, HW + EX)
Note that HW+EX is over 30. Thus, if you get 8/10 from the home works (which is quite easy), then your final grade will be at least 8/20 for sure and every thing you do during the exam just adds up to this capital!
20172018
20162017
20152016
20122014
20112012
20102011
The default language of the teachers is French.
But the lectures may be given in English if attended by non Frenchspeaking and Englishspeaking 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:
Randomized Algorithms
Introduction and definitions
Better than deterministic: saving time and space (Mincut, AND/OR trees)
Yao's principle: optimal randomized algorithms (Harddrive consumption optimization)
Search for positive certificates: polynomial identity testing,...
Autocorrection of buggy codes: matrix multiplication
Random solution and LProunding for MaxSAT
Random walks for kSAT
Constanttime approximation scheme
Connections with greedy algorithms: conditional expectation method (MaxCut)
Random Graphs
The probabilistic method
ErdösRé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 smallworld 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.

Zero sum game & von Neumann's Minimax theorem
Application to lower bounding randomized algorithms: Yao's principle
An example: Hard drive energy saving

Optimal NAnd Tree evaluation (Yao's principle)
Lecture 5B [16:1518:15] Emergence of the giant connected component (4)
Lecture notes

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^{2} n) hops when α = 2
SAT: NPcompletness, exact resolution
A first dummy randomized algorithm
WalkSAT algorithm for 3SAT
WalkSAT for 2SAT
Phase transition in Random 1SAT
The hard drive energy saving problem
Best deterministic algorithm
Randomized algorithms: definition and performance evaluation
Yao principle and von Neumann's minimax theorem
Recall on the phase transition
Recall on the directed graph associated to 2SAT, formula: UNSAT ⇔ there is a x s.t. x and ¬x belong to the same strongly connected component
Scheme of the proof: growth of the neighborhood from a litteral to get √n litterals, then existence of an arc
Branching processes: GaltonWatson processus, definition
Probabilitic toolbox
Markov's inequality
Chebychev's inequality
Second moment method
Growth and extinction of the Galton Watson process
Optimal randomized algorithm for the hard drive energy saving problem using Yao's principle
Introduction to Streaming algorithms
Frequencies & Moments of a stream
Evaluating F_{1}: an (ε,δ)estimator for a O(loglog n)counter
Recalls on GaltonWatson branching processes
Random2SAT is almost surely UNSAT for c > 1 (End)
F _{0}: (ε,2/(1+ε))estimator (to be continued in Exercise session 4)
Generating function for GaltonWatson processes
Generating function for the total population number in GaltonWatson processes (to be continued in Exercise session 4)
GaltonWatson branching process with continuous lifetime and birthrate (to be continued in Exercise session 4)
Evaluating F2
kwise independent Hash functions family
Generating function of a random variable
Extinction probability of a GaltonWatson branching process
A little bit of history
Program checking: multiplication, graph isomorphism
Selfreduction, Averagecase hardness, & Program selfcorrection: multiplication, permanent
Definition of G(n,p)
No large connected components for p ≤ c/n with c <1
Emergence of the large connected component for p ≥ c/n with c > 1
Duality principle in GaltonWatson branching process:
distribution of the size of the tree conditioned on extinction
relation to the size of giant connected component
Using fingerprints to check matrix multiplication
FPT algorithm for spotting k disjoint triangles
Binomial laws composition
Prüfer sequences to encode unrooted labelled trees
A little bit of history


PCP(r,q)verifier & the PCP class
WalshHadamard codes
Linearity testing & Fourier transforms of Boolean functions
NPcompleteness of QUADEQ
A PCP(n^{2},1)verifier for QUADEQ
== Lecture 5B: The smallworld phenomenon: phase transitions for algorithms
Milgram's experiment
Kleinberg's model (2000): the random augmented grid model K_{α} & the decentralized algorithms
Phase transition for finding paths to a destination with decentralized algorithms Lecture's document
Phase I: when α<2, the links are too messy and decentralized paths have polynomial lengths
Phase III: when α>2, the links are too shorts and decentralized paths have polynomial lengths
Phase II: when α=2, the greedy decentralized algorithms find path of length O(log^{2} n)
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

A (3/2)^{n}time constraintbased randomized exact algorithm for 3SAT
A faster Mincut algorithm

Random cut for the Max Cut problem and its derandomization by the conditional expectation method
Yao's principle: Optimal randomized algorithm for the evaluation of NANDtree

Random cut for the Max Cut problem and its derandomization by the conditional expectation method
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 kwise independent hash functions
A streaming (ε,δ)estimator for F2 with Oε,δ(log m + log n) bits of memory

Generating n pairwise independent uniform random bits from log2(n) uniform (truly) independent random bits
A streaming (c1,1/c)estimator with c > 1 for the number of distinct values in a stream using O(log m) bits of memory

Uniformity detection
Using fingerprints to check matrix multiplication [ to return on Jan. 6, 2014 ]
Introduction to randomized algorithms
LogLog Counters
(ε,δ)estimators
Minimum Cut randomized algorithm
Fast Minimum Cut randomized algorithm
Dumb randomized algorithm for MaxSat
Constraintbased randomized algorithm for 3Coloring
Random solution for MaxSAT
Linear program relaxation for MaxSat and its randomized rounding
Mixing both algorithms yields a better one
Semidefinite programming for MaxCut and cut by a random hyperplane
Randomized rounding of a linear program relaxation for SetCover
A streaming algorithm for computing the second moment of frequencies F_{2} : 4wise independent hash functions
Selfcorrecting integer product
A Fixed Parameter Tractable algorithm for finding k disjoints triangles
A deterministic algorithm for uniformity detection
Matrix multiplication testing
Expansion: Combinatoric definition
Expansion: Spectral definition
Cheeger inequalities and first applications
Expander constructions: Examples and ZigZag product
Zigzag product and explicit expander construction
Graph constraints satisfaction Gapproblem: Degree uniformization step
Random walks on expanders are almost sequences of independent trials
Introduction aux algorithmes randomisés
Un algorithme randomisé pour MinCut
Analyse d'une partition aléatoire pour MaxCut
Dérandomisation par la méthode de l'espérance conditionnelle
Dérandomisation par la construction d'un espace probabilisé de bits uniformes 2à2 indépendants
Généralisation à des bits uniformes kàk indépendants
Fonctions booléennes, CNF et DNF
L'algorithme WalkSAT
Optimisation de la mise en veille d'un disque dur
L'algorithme de KargerStein (1993) pour MinCut
Approximation pour MaxSAT
Instance aléatoire
Arrondi LP
Un mixte des deux
Arrondi aléatoire pour MinSetCover
Fingerprint: identity testing
Polynomial identity testing
Pattern matching
Traffic monitoring
A constanttime approximation scheme (CTAS) for maximal matching size in constant degree graphs
