|
2017-2018
2016-2017
2015-2016
2012-2014
2011-2012
2010-2011
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:
Random Graphs
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.
-
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:15-18: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(log2 n) hops when α = 2
SAT: NP-completness, exact resolution
A first dummy randomized algorithm
WalkSAT algorithm for 3-SAT
WalkSAT for 2-SAT
Phase transition in Random 1-SAT
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 2-SAT, 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: Galton-Watson 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 F1: an (ε,δ)-estimator for a O(loglog n)-counter
Recalls on Galton-Watson branching processes
Random-2SAT is almost surely UNSAT for c > 1 (End)
F 0: (ε,2/(1+ε))-estimator (to be continued in Exercise session 4) 
Generating function for Galton-Watson processes
Generating function for the total population number in Galton-Watson processes (to be continued in Exercise session 4)
Galton-Watson branching process with continuous lifetime and birthrate (to be continued in Exercise session 4) 
Evaluating F2
k-wise independent Hash functions family
Generating function of a random variable
Extinction probability of a Galton-Watson branching process
A little bit of history
Program checking: multiplication, graph isomorphism
Self-reduction, Average-case hardness, & Program self-correction: 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 Galton-Watson 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
Walsh-Hadamard codes
Linearity testing & Fourier transforms of Boolean functions
NP-completeness of QUADEQ
A PCP(n2,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(log2 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 constraint-based randomized exact algorithm for 3-SAT
A faster Min-cut 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 NAND-tree
-
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 k-wise 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 (c-1,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 Max-Sat
Constraint-based randomized algorithm for 3-Coloring
Random solution for Max-SAT
Linear program relaxation for Max-Sat and its randomized rounding
Mixing both algorithms yields a better one
Semi-definite programming for Max-Cut and cut by a random hyperplane
Randomized rounding of a linear program relaxation for Set-Cover
A streaming algorithm for computing the second moment of frequencies F2 : 4-wise independent hash functions
Self-correcting 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 Zig-Zag product
Zig-zag product and explicit expander construction
Graph constraints satisfaction Gap-problem: Degree uniformization step
Random walks on expanders are almost sequences of independent trials
Introduction aux algorithmes randomisés
Un algorithme randomisé pour Min-Cut
Analyse d'une partition aléatoire pour Max-Cut
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 Walk-SAT
Optimisation de la mise en veille d'un disque dur
L'algorithme de Karger-Stein (1993) pour Min-Cut
Approximation pour Max-SAT
Instance aléatoire
Arrondi LP
Un mixte des deux
Arrondi aléatoire pour Min-Set-Cover
Fingerprint: identity testing
Polynomial identity testing
Pattern matching
Traffic monitoring
A constant-time approximation scheme (CTAS) for maximal matching size in constant degree graphs
|