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

I am on the faculty job market.

About Me

I am a postdoc in theoretical computer science at DIMACS working with Sepehr Assadi, Aaron Bernstein, and Martin Farach-Colton.

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 do 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
[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
[arXiv] [invited to minisymposium at CANADAM 2021]

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]

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]