Service

I am co-organizing the June 2023 DIMACS workshop Modern Techniques in Graph Algorithms.

PC Member: ESA 2023, SODA 2023, ITCS 2022

I was the organizer of Algorithms Office Hours at MIT, whose goal is to improve communication between theory and applications of algorithms.

I have been a subreviewer for many conferences and journals.

Other

3 Pieces of Reassurance for Early-Stage PhD Students (in TCS)

One of my favorite ways to do research is supercollaboration.

I do ballet and tap dancing.

My brother Alex is also a theoretical computer scientist.

My sister Natasha is an artist x2.

My sister-in-law Melissa is a topologist.

My sister-in-law Maya is a designer.

Nicole Wein

nicole.wein at rutgers dot edu
she/her

About Me

Starting in January 2024 I will be an assistant professor at the University of Michigan. I will be in the Theory of Computation Lab within the Computer Science and Engineering Division of the EECS Department.

During Fall 2024 I will be a Research Fellow at the Simons Institute.

Currently I am a postdoc at DIMACS working with Sepehr Assadi, Aaron Bernstein, Martin Farach-Colton, and Jie Gao.

I did my PhD at MIT advised by Virginia Vassilevska Williams.

I have a Masters in Computer Science from Stanford and a B.S. in Computer Science/Math from Harvey Mudd College where Ran Libeskind-Hadas sparked my interest in algorithms. During undergrad I did an REU at Oregon State University with Glencora Borradaile.

A number other mentors have supported my career including Michael Bender, Moses Charikar, Erik Demaine, Monika Henzinger, Piotr Indyk, Anna Lubiw, Tim Roughgarden, Shay Solomon, and Hsin-Hao Su.

During the DIMACS REU 2022 I mentored undergraduate student Sam Hiken.

My Research

I am a theoretical computer scientist doing research on 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. I am more broadly interested in algorithmic problems that are combinatorial in nature.

Some questions that guide my research:

How can algorithms cope with changing data?
What information can algorithms extract from a graph in only (say) linear time?
Can we understand the structure of shortest paths in graphs, especially directed graphs?

Publications

Preprints

A Local-to-Global Theorem for Congested Shortest Paths
with Shyan Akmal
[arXiv]

2023

Closing the Gap Between Directed Hopsets and Shortcut Sets
with Aaron Bernstein
SODA
[arXiv]

2022

Online List Labeling: Breaking the log²n Barrier
with Michael A. Bender, Alexander Conway, Martín Farach-Colton, Hanna Komlós, and William Kuszmaul
FOCS, Invited to the special issue of SICOMP, Invited to HALG
[arXiv] [TCS+ talk]

Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
with Mina Dalirooyfard, Ce Jin, and Virginia Vassilevska Williams
FOCS
[arXiv]

Hardness of Token Swapping on Trees
with Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, and Virginia Vassilevska Williams
ESA, Invited minisymposium at CANADAM
[arXiv]

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost
with Aaron Berger, William Kuszmaul, Adam Polak, and Jonathan Tidor
ICALP
[arXiv]

Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product
with Kevin Lu, Virginia Vassilevska Williams, and Zixuan Xu
SODA
[arXiv]

2021

Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial
with Adir Morgan and Shay Solomon
DISC
[arXiv] [talk]

Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
with Mina Dalirrooyfard
STOC
[arXiv]
See also concurrent work by Ray Li

New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
with Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, and Virginia Vassilevska Williams
SODA
[arXiv]

2020

Lower Bounds for Dynamic Distributed Task Allocation
with Hsin-Hao Su
ICALP, BDA
[arXiv] [talk]

New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
with Maximilian Probst Gutenberg and Virginia Vassilevska Williams
STOC
[arXiv] [talk]

2019

Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
with Mina Dalirrooyfard, Virginia Vassilevska Williams, and Nikhil Vyas
ICALP
[arXiv]

Approximation Algorithms for Min-Distance Problems
with Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Yinzhan Xu, and Yuancheng Yu
ICALP
[arXiv]

Algorithms and Hardness for Diameter in Dynamic Graphs
with Bertie Ancona, Monika Henzinger, Liam Roditty, and Virginia Vassilevska Williams
ICALP
[arXiv]

2018

Improved Dynamic Graph Coloring
with Shay Solomon
ESA, TALG
[arXiv] [mentioned in blog post]

Finding Cliques in Social Networks: A New Distribution-Free Model
with Jacob Fox, Tim Roughgarden, C. Seshadhri, and Fan Wei
ICALP, SICOMP
[arXiv] [talk] [focus of chapter 28 of Beyond the Worst-Case Analysis of Algorithms]

Fully Dynamic MIS in Uniformly Sparse Graphs
with Krzysztof Onak, Baruch Schieber, and Shay Solomon
ICALP, TALG
[arXiv]

Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
with Arturs Backurs, Liam Roditty, Gilad Segal, and Virginia Vassilevska Williams
STOC, SICOMP
[arXiv]