Distributed algorithms for networks (2024-2025)
General information
- This is the webpage for the 2024-2025 iteration of the course
Distributed algorithms of networks (C14), taught in the
Master 2 program
of ENS Lyon.
- Last year's webpage is here.
- This year the lecturers are:
Stephan Thomassé,
Laurent Feuilloley, and
Théo Pierron.
(Nicolas Bousquet participated in the design of the course but is
not teaching this year.)
- The time slots are the follwing: Monday 15:45-17:45 and
Friday 10:15-12:15.
- The final grade will be a weighted average of the grade for
scribe notes and the grade for final exam.
Tentative program
Monday November 18 (S. Thomassé)
- Definition of coloring/spanning trees.
- Definition of the LOCAL
model (identifiers, rounds etc.).
- Lower bound for 2-coloring.
- 3-coloring: brute-force algorithms, and Cole-Vishkin.
- Graph notions:
Chromatic number,
high-chromatic triangle-free graphs via Mycielski. High-girth
high chromatic number, Erdos theorem (no proof). Shift graph. Ramsey
number. Line graph. log Chi(G) <= Chi(L(G))
Friday November 22 (S. Thomassé)
- Chi(L(G))<= log Chi(G) + log log Chi(G)
- Discussion about graph intersection, graph homomorphism
- 3-coloring via Linial color sets
- Log* Lower bound for 3-coloring
- k-cover-free families
Monday November 25 (S. Thomassé)
- Using k-cover-free families for Delta^2 coloring
- Down to Delta colors with additive group coloring
- Coloring directed trees
- log n lower bound for coloring undirected trees + proof of
Erdos construction
- Coloring undirected trees via rake-and-compress
Friday November 29 (S. Thomassé)
- Randomized algorithms: Monte-Carlo, Las vegas
- Sinkless orientation and O(\log n) deterministic algorithm.
- Randomized coloring: 2Delta colors, then (1+eps)Delta, and
finally Delta+1, in O(log n)
- Coloring with (1+eps)Delta colors in O(sqrt{log n})
Monday December 2 (S. Thomassé)
- More randomized algorithms
Friday December 6 (L. Feuilloley)
- Discussion about symmetry breaking. Definition of SLOCAL.
- Definition
of (low diameter) network decomposition, and polylog n decomposition
algorithm theorem, without proof.
- Theorem and proof for
SLOCAL(polylog n) in LOCAL(polylog n).
- Theorem and proof of
derenadomization in polylog regime.
Monday December 9 (L. Feuilloley)
- Centralized algorithm for polylog network
decomposition.
- Lower bound via chromatic number.
- Algorithm for ruling
sets.
- Definition of a weak decomposition, and theorem weak to strong
(not proved).
- Algorithm sketch for polylog weak decomposition.
Friday December 13 (T. Pierron)
- Introduction to the CONGEST model
Monday December 16: CANCELLED
Friday December 20 (L. Feuilloley)
- Discussion about complexity gaps and derandomization.
- Discussion
about the knowledge of n, and "lying" to the algorithm.
- Theorem and
proof for exponential dereandomization.
- Theorem and proof for the
gap between O(log^*n) and o(log n).
Monday January 6 (L. Feuilloley)
- Lower bound for sinkless orientation. (Supported LOCAL model,
round elimination, bipartite encoding).
Friday January 10 (T. Pierron)
Monday January 13 (T. Pierron)
Friday January 17 (T. Pierron)
Monday January 20 (T. Pierron)
Monday January 24
Friday January 27: No class (except if stated otherwise later.)
Friday January 31: Exam
Useful material