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é)
- Maximal independent set and Luby's algorithm
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)
- Definition of the CONGEST model
- Breadth-first tree and BFS based All-pairs shoetest paths
- Minimum spanning tree, by adaption Boruvka's algorithm
- Detecting 4-cycles
- Communication complexity, set disjointness
- Lower bound for 4-cycle detection
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)
- Lower bound in D + \sqrt{n} for minimum spanning tree
- Definition of congested clique
- Lenzen's routing
Monday January 13 (T. Pierron)
- Definition of local certification
- Basic examples
- Lower bound for dumbbell graphs
- Spanning tree certification
- Planarity certification
- k-connectivity, ear decompositions
- 2-connectivity and K_4-minor-freeness certification
- Local certification of maximum bipartite matching in bipartite graphs
Friday January 17 (T. Pierron)
- Lower bound for certifying spanning trees
- Lower bound for certifying diameter = k
- Meta-theorems for MSO on paths, trees, bounded treedepth
Monday January 20 (T. Pierron)
- Local certification of H-freeness (for induced subgraphs)
Monday January 24
Friday January 27: No class (except if stated otherwise later.)
Friday January 31: Exam
Exam pdf
Useful material