Faculty Recruiting Support CICS

Theory Seminar - "Giving Almost Tight Lower Bounds for Distributed Verification Problems Using Communication Complexity"

07 Dec
Tuesday, 12/07/2021 4:00pm to 5:00pm
Computer Science Building, Room 140
Theory Seminar
Speaker: Jacob Urisman (UMass-Amherst)

Abstract: We study the verification problem in distributed networks, stated as follows. Let H be a subgraph of a network G where each vertex of G knows which edges incident on it are in H. We would like to verify whether H has some properties, e.g., if it is a tree or if it is connected (every node knows at the end of the process whether H has the specified property or not). We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication. In this talk, I will briefly explain the paper by Sarma et. al. on distributed verification and the almost tight lower bounds on the running time of distributed verification algorithms for fundamental problems such as, spanning connected subgraph that they found.

The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.