Computer Science/Discrete Mathematics Seminar II

In this talk, I will elaborate on the main technical component of our PCP—the construction of routing protocols on high-dimensional expanders (HDX) that can withstand a constant fraction of edge corruptions. We consider the following routing problem on a graph G: given a permutation π on the vertices of G, design communication protocols (using the edges of G) to enable message transmission from each vertex u to π(u). The set of protocols must satisfy two key properties: 1) fault-tolerance: even if a constant fraction of the edges of G behave adversarially, only a constant fraction of the message transmissions fail, and 2) efficiency: every vertex performs only polylog(n) computation across all the protocols.

This problem is closely related to the almost-everywhere reliable transmission problem introduced by Dwork, Peleg, Pippenger, and Upfal (1986), who were motivated by applications to distributed computing on sparse networks. Drawing inspiration from this literature, we design protocols that use the dense well-connected subgraphs in an HDX (with degree polylog(n)) to perform error correction during message transmission, thereby achieving fault-tolerant routing. I will also discuss an upcoming work in which we construct constant-degree graphs that support fault-tolerant routing protocols, resolving the main open question posed by Dwork et al. As a consequence, we obtain networks of constant degree, supporting Byzantine agreement protocols, fault-tolerant distributed computing, and secure multiparty computation. Prior to our work, the constructions of such networks had logarithmic degree.