Nicole Wein, DIMACS

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.

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar