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.
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.
I am on the faculty job market.
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.
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:
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 log2n 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]