Explore a 23-minute IEEE conference talk on deterministic distributed expander decomposition routing and its applications in distributed derandomization. Delve into the computation model, distributed expander decompositions, and routing algorithms presented by researchers from ETH Zurich and Toyota Technological Institute at Chicago. Learn about the novel deterministic approach to previously randomized algorithms, the distributed balanced sparse cut algorithm, and the recursive solution for expander routing problems. Gain insights into the research direction's ultimate goals and open questions in this field of distributed computing and graph theory.
Deterministic Distributed Expander Decomposition Routing with Applications in Distributed Derandomization
Overview
Syllabus
Intro
Computation model
Further applications of distributed expander decompositions
Deterministic distributed expander decompositions and routing All previous distributed algorithms for expander decompositions and routing are randomized.
Distributed expander decomposition algorithm
Review of the sequential recursive
Distributed balanced sparse cut algorithm
Distributed expander routing algorithm The simultaneous embeddings of high-conductance graphs to ... also allow us to solve the expander routing problem recursively
Open questions The ultimate goal of this research direction
Taught by
IEEE FOCS: Foundations of Computer Science
