Nicole Wein

According to our database, Nicole Wein authored at least 31 papers between 2018 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Beyond 2-Approximation for <i>k</i>-Center in Graphs.

Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

2024

Edge-Minimum Walk of Modular Length in Polynomial Time.

Antoine Amarilli, Benoît Groz, Nicole Wein

CoRR, 2024

Improved Hardness-of-Approximation for Token Swapping.

Sam Hiken, Nicole Wein

CoRR, 2024

Low Sensitivity Hopsets.

Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng, Jie Gao, Nicole Wein

CoRR, 2024

Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights?

Aaron Bernstein, Greg Bodwin, Nicole Wein

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Additive Spanner Lower Bounds with Optimal Inner Graph Structure.

Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Detecting Disjoint Shortest Paths in Linear Time and More.

Shyan Akmal, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Closing the Gap Between Directed Hopsets and Shortcut Sets.

Aaron Bernstein, Nicole Wein

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

A Local-To-Global Theorem for Congested Shortest Paths.

Shyan Akmal, Nicole Wein

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Dynamic Graph Algorithms (Dagstuhl Seminar 22461).

Aaron Bernstein, Shiri Chechik, Sebastian Forster, Tsvi Kopelowitz, Yasamin Nazari, Nicole Wein

Dagstuhl Reports, November, 2022

Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product.

Kevin Lu, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost.

Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, Nicole Wein

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles.

Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Online List Labeling: Breaking the log²n Barrier.

Michael A. Bender, Alex Conway, Martin Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Hardness of Token Swapping on Trees.

Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Algorithms and Hardness for Approximating the Diameter of a Graph.

Nicole Wein

PhD thesis, 2021

Toward Tight Approximation Bounds for Graph Diameter and Eccentricities.

Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein

SIAM J. Comput., 2021

Simple Combinatorial Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs.

Adir Morgan, Shay Solomon, Nicole Wein

CoRR, 2021

Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial.

Adir Morgan, Shay Solomon, Nicole Wein

Proceedings of the 35th International Symposium on Distributed Computing, 2021

Tight conditional lower bounds for approximating diameter in directed graphs.

Mina Dalirrooyfard, Nicole Wein

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners.

Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

Improved Dynamic Graph Coloring.

Shay Solomon, Nicole Wein

ACM Trans. Algorithms, 2020

Fully Dynamic MIS in Uniformly Sparse Graphs.

Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein

ACM Trans. Algorithms, 2020

Finding Cliques in Social Networks: A New Distribution-Free Model.

Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, Nicole Wein

SIAM J. Comput., 2020

Algorithms and Lower Bounds for the Worker-Task Assignment Problem.

Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, Nicole Wein

CoRR, 2020

New algorithms and hardness for incremental single-source shortest paths in directed graphs.

Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Lower Bounds for Dynamic Distributed Task Allocation.

Hsin-Hao Su, Nicole Wein

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems.

Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Approximation Algorithms for Min-Distance Problems.

Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, Yuancheng Yu

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Algorithms and Hardness for Diameter in Dynamic Graphs.

Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Towards tight approximation bounds for graph diameter and eccentricities.

Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018