Lower Bounds for Shortcut Sets and Additive Spanners

Start Date: October 20, 2021
Event Start Time: 11:00 AM
Event End Time: 12:00 PM
Seminar Series: Theoretical Computer Science Seminar
Presenter(s): Nicole Wein - DIMACS
Event Location: Online Event
Event Additional Info: <p>Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
Presentation Type: Stand Alone Presentation
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.

Events