Abstract: There are many graph problems of the following form: Given a graph G, construct a graph H that preserves some information about G, while optimizing some property of H. Some examples include spanners, distance preservers, reachability preservers, shortcut sets, and hopsets. I will focus on two of these:
- A spanner is a subgraph H of G that approximately preserves distances while being as sparse as possible.
- A shortcut set is a (small) set of edges that when added to a directed graph G produces a graph H which preserves the reachability structure of G while reducing the diameter as much as possible.
I will talk about lower bound constructions for these two structures.
Based on joint work with Kevin Lu, Virginia Vassilevska Williams, and Zixuan Xu.
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.