Service

I will be on the PC for SODA 2023.
I was on the PC for 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.

My sister-in-law Melissa is a topologist.

Nicole Wein

nicole.wein at rutgers dot edu
she/her

I will be on the job market this year.

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.

My Research

I do reseach 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

Online List Labeling: Breaking the log²n Barrier
with Michael A. Bender, Alexander Conway, Martín Farach-Colton, Hanna Komlós, and William Kuszmaul
[arXiv]

Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
with Mina Dalirooyfard, Ce Jin, and Virginia Vassilevska Williams
[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
[arXiv] [invited to minisymposium at CANADAM 2021]

2022

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] [video]

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] [video]

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

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] [video] [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]