(she/her/hers)
DIMACS, Rutgers University
theoretical computer science, graph algorithms, fine-grained complexity, dynamic algorithms
Nicole Wein is a Simons Postdoctoral Leader at DIMACS, Rutgers University working with Sepehr Assadi, Aaron Bernstein, and Martin Farach-Colton. She graduated with her PhD in 2021 from MIT, where she was advised by Virginia Vassilevska Williams. She also has a Masters in Computer Science from Stanford University and a B.S. in Computer Science/Math from Harvey Mudd College. Her research interests include graph algorithms and lower bounds including in the areas of distance-estimation algorithms, dynamic algorithms, parameterized algorithms, distributed algorithms, online algorithms, data structures, and fine-grained complexity.
Distance-Approximation and Shortcutting in Directed Graphs
Graphs model a wide variety of real-world structures such as transportation networks, biological networks, social networks, and the Internet. Because the size and complexity of graphs has outpaced the development of algorithms, there is a need for new algorithms that meet the demands of modern datasets. In my research as a theoretical computer scientist, I study graph algorithms and lower bounds especially in the context of modern datasets.
I will focus on the classical problems of single-source reachability and single-source shortest paths in directed graphs. In a number of settings tailored towards large datasets, including parallel algorithms, distributed algorithms, dynamic algorithms, and streaming algorithms, computation is generally faster if the graph has small diameter. Thus, it is often useful for an algorithm to have a preprocessing step that adds a small set of auxiliary edges to the graph with the purpose of decreasing its diameter. This motivates the definition of a shortcut set: a set of auxiliary edges that when added to a directed graph minimizes its diameter without changing the reachability structure of the graph (i.e. a vertex u can reach a vertex v in the new graph if and only if it could in the original graph). Then, to solve the single-source reachability problem, one can first compute a shortcut set and then run a single-source reachability algorithm on the resulting graph. For the above settings where computation is faster for graphs of smaller diameter, this yields a faster algorithm; moreover the correct answer is obtained since the shortcut set does not change the reachability structure of the graph.
Thus, it is natural to ask for the existentially best possible shortcut set one can achieve i.e. the best possible trade-off between number of edges added and resulting diameter. The same question can be asked for a hopset, an structure analogous to a shortcut set except concerning (approximate) distances instead of reachability. In recent work, we prove both upper and lower bounds on the construction of shortcut sets and hopsets.