Fault Tolerant Routing Protocols on High-Dimensional Expanders

Explore a computer science seminar presentation that delves into the construction of routing protocols on high-dimensional expanders (HDX) capable of handling constant fraction edge corruptions. Learn about a routing problem where communication protocols must enable message transmission between vertices while maintaining fault tolerance and computational efficiency. Discover how dense well-connected subgraphs in HDX are utilized for error correction during message transmission, and understand the breakthrough development of constant-degree graphs supporting fault-tolerant routing protocols. Examine the implications for Byzantine agreement protocols, fault-tolerant distributed computing, and secure multiparty computation, marking a significant advancement from previous logarithmic degree constructions. The presentation addresses the almost-everywhere reliable transmission problem introduced by Dwork, Peleg, Pippenger, and Upfal, demonstrating its relevance to distributed computing on sparse networks.