Publications in graph and matrix algorithms


Conference publications:

  • Beyond 2-approximation for k-Center in Graphs, Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams and Nicole Wein.

    		• SODA 2025


    		[TO COME]

  • All-Hops Shortest Paths, Virginia Vassilevska Williams, Zoe Xi, Yinzhan Xu and Uri Zwick.

    		• SODA 2025


    		[TO COME]

  • Fine-Grained Optimality of Partially Dynamic Shortest Paths and More, Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu and Christopher Ye.

    		• SODA 2025


    		[TO COME]

  • More Asymmetry Yields Faster Matrix Multiplication, Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Renfei Zhou.

    		• SODA 2025


    		[TO COME]

  • Faster cycle detection in the Congested Clique, Keren Censor-Hillel, Tomer Even and Virginia Vassilevska Williams.

    		• DISC 2024


    		[TO COME]

  • Additive Spanner Lower Bounds with Optimal Inner Graph Structure, Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein and Zixuan Xu.

    		• ICALP 2024


    		[TO COME]

  • Fast Approximate Counting of Cycles, Keren Censor-Hillel, Tomer Even and Virginia Vassilevska Williams.

    		• ICALP 2024


    		[TO COME]

  • Detecting Disjoint Shortest Paths in Linear Time and More, Shyan Akmal, Virginia Vassilevska Williams and Nicole Wein.

    		• ICALP 2024


    		[TO COME]

  • Towards Optimal Output-Sensitive Clique Listing (a.k.a. Listing Cliques from Smaller Cliques), Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams and Yinzhan Xu.

    		• STOC 2024


    		[arXiv]

  • Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation, Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams and Zixuan Xu.

    		• SODA 2024


    		[arXiv]

  • Simpler and Higher Lower Bounds for Shortcut Sets, Virginia Vassilevska Williams, Yinzhan Xu and Zixuan Xu.

    		• SODA 2024


    		[arXiv]

  • New Bounds for Matrix Multiplication: from Alpha to Omega, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Renfei Zhou.

    		• SODA 2024


    		[arXiv]

  • Fast 2-Approximate All-Pairs Shortest Paths, Michael Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams and Tijn de Vos.

    		• SODA 2024


    		[arXiv]

  • Listing 6-Cycles, Ce Jin, Virginia Vassilevska Williams and Renfei Zhou.

    		• SOSA 2024


    		[arXiv]

  • Quasipolynomiality of the Smallest Missing Induced Subgraph, David Eppstein, Andrea Lincoln and Virginia Vassilevska Williams.

    		• Journal of Graph Algorithms and Applications, 2023.


    		[JGAA]

  • On Diameter Approximation in Directed Graphs, Amir Abboud, Mina Dalirrooyfard, Ray Li and Virginia Vassilevska Williams.

    		• ESA 2023


    		[arXiv]

  • Faster Detours in Undirected Graphs, Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams and Zixuan Xu.

    		• ESA 2023


    		[arXiv]

  • Approximating Min-Diameter: Standard and Bichromatic, Aaron Berger, Jenny Kaufmann and Virginia Vassilevska Williams.

    		• ESA 2023


    		[arXiv]

  • Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More, Timothy Chan, Virginia Vassilevska Williams and Yinzhan Xu.

    		• STOC 2023


    		[arxiv]

  • Improved girth approximation in weighted undirected graphs, Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams and Uri Zwick.

    		• SODA 2023


    		[SIAM pdf]

  • Induced Cycles and Paths Are Harder Than You Think, Mina Dalirooyfard and Virginia Vassilevska Williams.

    		• FOCS 2022


    		[arXiv]

  • Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles, Mina Dalirooyfard, Ce Jin, Virginia Vassilevska Williams and Nicole Wein.

    		• FOCS 2022


    		[arXiv]

  • Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures, Virginia Vassilevska Williams, Eyob Woldeghebriel and Yinzhan Xu.

    		• FOCS 2022


    		[arXiv]

  • Hardness of Token Swapping on Trees, Oswin Aichholzer, Erik Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masarova, Mikhail Rudoy, Virginia Vassilevska Williams and Nicole Wein.

    		• ESA 2022


    		[arXiv]

  • New Lower Bounds and Upper Bounds for Listing Avoidable Vertices, MingYang Deng, V. Vassilevska Williams and Ziqian Zhong.

    		• MFCS 2022


    		[MFCS pdf]

  • New additive approximations for shortest paths and cycles, MingYang Deng, Yael Kirkpatrick, Victor Rong, V. Vassilevska Williams and Ziqian Zhong.

    		• ICALP 2022


    		[ICALP pdf]

  • Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds, Surya Mathialagan, V. Vassilevska Williams and Yinzhan Xu.

    		• ICALP 2022


    		[arXiv]

  • Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV, Timothy Chan, V. Vassilevska Williams and Yinzhan Xu.

    		• STOC 2022


    		[to come]

  • Dynamic Matching Algorithms Under Vertex Updates, Hung Le, Lazar Milenkovic, Shay Solomon and V. Vassilevska Williams.

    		• ITCS 2021


    		[to come]

  • Algorithmic trade-offs for girth approximation in undirected graphs, Avi Kadria, Liam Roditty, Aaron Sidford, V. Vassilevska Williams and Uri Zwick.

    		• SODA 2022


    		[SIAM pdf]

  • Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product, Kevin Lu, V. Vassilevska Williams, Nicole Wein and Zixuan Xu.

    		• SODA 2022


    		[to come]

  • Hardness of Approximate Diameter: Now for Undirected Graphs, Mina Dalirrooyfard, Ray Li and V. Vassilevska Williams.

    		• FOCS 2021


    		[arXiv]

  • Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths, Timothy Chan, V. Vassilevska Williams, and Yinzhan Xu.

    		• ICALP 2021


    		[arXiv]

  • Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths, Yuzhou Gu, Adam Polak, V. Vassilevska Williams, and Yinzhan Xu.

    		• ICALP 2021


    		[arXiv]

  • A Refined Laser Method and Faster Matrix Multiplication, Josh Alman and V. Vassilevska Williams.

    		• SODA 2021


    		[arXiv]

  • New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners, Thiago Bergamaschi, Monika Henzinger, Max Probst Gutenberg, V. Vassilevska Williams and Nicole Wein.

    		• SODA 2021


    		[arXiv]

  • Distributed Distance Approximation, Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron and V. Vassilevska Williams.

    		• OPODIS 2020


    		[arXiv]

  • New Techniques for Proving Fine-Grained Average-Case Hardness, Mina Dalirrooyfard, Andrea Lincoln and V. Vassilevska Williams.

    		• FOCS 2020


    		[arXiv]

  • Monochromatic Triangles, Triangle Listing and APSP, V. Vassilevska Williams and Yinzhan Xu.

    		• FOCS 2020


    		[arXiv]

  • Towards Optimal Set-Disjointness and Set-Intersection Data Structures, Tsvi Kopelowitz and V. Vassilevska Williams.

    		• ICALP 2020


    		[ICALP version]

  • Conditionally optimal approximation algorithms for the girth of a directed graph, Mina Dalirrooyfard and V. Vassilevska Williams.

    		• ICALP 2020


    		[ICALP version]

  • New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs, Maximilian Probst, V. Vassilevska Williams and Nicole Wein.

    		• STOC 2020


    		[pdf]

  • OV graphs are (probably) hard instances, Josh Alman and V. Vassilevska Williams.

    		• ITCS 2020


    		[pdf]

  • Monochromatic triangles, intermediate matrix products, and convolutions, Andrea Lincoln, Adam Polak and V. Vassilevska Williams.

    		• ITCS 2020


    		[pdf]

  • Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications, V. Vassilevska Williams and Yinzhan Xu.

    		• SODA 2020


    		[pdf]

  • Equivalences between Triangle and Range Query Problems, Lech Duraj, Krzysztof Kleiner, Adam Polak and V. Vassilevska Williams.

    		• SODA 2020


    		[pdf]

  • Public-Key Cryptography in the Fine-Grained Setting, Rio LaVigne, Andrea Lincoln and V. Vassilevska Williams.

    		• CRYPTO 2019


    		[ePrint]

  • Algorithms and Hardness for Diameter in Dynamic Graphs, Bertie Ancona, Monika Henzinger, Liam Roditty, V. Vassilevska Williams and Nicole Wein.

    		• ICALP 2019


    		[pdf]

  • Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems, Mina Dalirrooyfard, V. Vassilevska Williams, Nikhil Vyas and Nicole Wein.

    		• ICALP 2019


    		[pdf]

  • Approximation Algorithms for Min-Distance Problems, Mina Dalirrooyfard, V. Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu and Yuancheng Yu.

    		• ICALP 2019


    		[pdf]

  • Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles, Mina Dalirrooyfard, Thuy-Duong Vuong and V. Vassilevska Williams.

    		• STOC 2019


    		[pdf]

  • Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication, Josh Alman and V. Vassilevska Williams.

    		• FOCS 2018


    		[pdf]

  • Towards Tight Approximation Bounds for Graph Diameter and Eccentricities, Arturs Backurs, Liam Roditty, G. Segal, V. Vassilevska Williams and Nicole Wein.

    		• STOC 2018


    		[pdf]

  • Fine-grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy, Erik Demaine, Andrea Lincoln, Quanquan Liu, Jason Lynch and V. Vassilevska Williams.

    		• ITCS 2018


    		[arXiv]

  • Further limitations of the known approaches for matrix multiplication, Josh Alman and V. Vassilevska Williams.

    		• ITCS 2018


    		[arXiv]

  • Optimal Vertex Fault Tolerant Spanners (for fixed stretch), Greg Bodwin, Michael Dinitz, Merav Parter and V. Vassilevska Williams.

    		• SODA 2018


    		[arXiv]

  • Approximating Cycles in Directed Graphs, Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov and V. Vassilevska Williams.

    		• SODA 2018


    		[arXiv]

  • Tight Hardness for Shortest Cycles and Paths in Sparse Graphs, Andrea Lincoln, V. Vassilevska Williams and Ryan Williams.

    		• SODA 2018


    		[arXiv]

  • Dynamic Parameterized Problems and Algorithms, Josh Alman, Matthias Mnich and V. Vassilevska Williams.

    		• ICALP 2017


    		[arXiv]

  • Preserving Distances in Very Faulty Graphs, Greg Bodwin, Fabrizio Grandoni, Merav Parter and V. Vassilevska Williams.

    		• ICALP 2017


    		[arXiv]

  • Metatheorems for dynamic weighted matching, Dan Stubbs and V. Vassilevska Williams.

    		• ITCS 2017


    		[ITCS version]

  • Conditional hardness for sensitivity problems, Monica Henzinger, Andrea Lincoln, Stefan Neumann and V. Vassilevska Williams.

    		• ITCS 2017


    		[arXiv]

  • Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product, Karl Bringmann, Fabrizio Grandoni, Barna Saha and V. Vassilevska Williams.

    		• FOCS 2016


    		[pdf]

  • A 7/3-Approximation for Feedback Vertex Sets in Tournaments, Matthias Mnich, V. Vassilevska Williams and Laszlo Vegh.

    		• ESA 2016


    		[pdf]

  • Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs, Amir Abboud, Josh Wang, and V. Vassilevska Williams.

    		• SODA 2016


    		[pdf]

  • Better Distance Preservers and Additive Spanners, Greg Bodwin and V. Vassilevska Williams.

    		• SODA 2016


    		[pdf]

  • Subtree isomorphism revisited, Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, V. Vassilevska Williams, Or Zamir.

    		• SODA 2016


    		[pdf]

  • If the Current Clique Algorithms are Optimal, so is Valiant's Parser, Amir Abboud, Arturs Backurs, and V. Vassilevska Williams.

    		• FOCS 2015


    		[pdf]

  • Matching triangles and basing hardness on an extremely popular conjecture, Amir Abboud, V. Vassilevska Williams and Huacheng Yu.

    		• STOC 2015


    		[pdf]

  • Very sparse additive spanners and emulators, Greg Bodwin and V. Vassilevska Williams.

    		• ITCS 2015


    		[pdf]

  • Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter, Amir Abboud, Fabrizio Grandoni and V. Vassilevska Williams.

    		• SODA 2015


    		[pdf]

  • Finding four-node subgraphs in triangle time, V. Vassilevska Williams, Josh Wang, Ryan Williams and Huacheng Yu.

    		• SODA 2015


    		[pdf]

  • Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems, Amir Abboud and V. Vassilevska Williams.

    		• FOCS 2014


    		[pdf]

  • Listing Triangles, Andreas Bjorklund, Rasmus Pagh, V. Vassilevska Williams, Uri Zwick.

    		• ICALP 2014


    		[pdf]

  • Better Approximation Algorithms for the Graph Diameter, Shiri Chechik, Dan Larkin, Liam Roditty, Grant Schoenebeck, Bob Tarjan, V. Vassilevska Williams.

    		• SODA 2014


    		[pdf]

  • Fast approximation algorithms for the diameter and radius of sparse graphs, Liam Roditty, V. Vassilevska Williams.

    		• STOC 2013


    		[pdf]

  • Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths, F. Grandoni, V. Vassilevska Williams.

    		• FOCS 2012


    		[pdf]

  • Multiplying matrices faster than Coppersmith-Winograd,
    V. Vassilevska Williams

    		• STOC 2012


    		to come

  • Subquadratic Time Approximation Algorithms for the Girth,
    Liam Roditty and V. Vassilevska Williams

    		• SODA 2012


    		[pdf]

  • Minimum Weight Cycles and Triangles: Equivalences and Algorithms,
    Liam Roditty and V. Vassilevska Williams

    		• FOCS 2011


    		arXiv version

  • Faster replacement paths, V. Vassilevska Williams.

    		• SODA 2011 [SIAM] Preliminary version: [arXiv]

  • Subcubic Equivalences Between Path, Matrix, and Triangle Problems,
    V. Vassilevska Williams and Ryan Williams.

    		• FOCS 2010 [IEEE] [pdf]
    [full version], accepted to JACM.

  • Finding, Minimizing and Counting Weighted Subgraphs, V. Vassilevska, Ryan Williams.

    		• STOC 2009 [ACM] [ps] [pdf]
    [FULL version]

  • A New Combinatorial Approach to Sparse Graph Problems, Guy Blelloch, V. Vassilevska, Ryan Williams.

    		• ICALP 2008 [Springer] [ps] [pdf]
  • Nondecreasing Paths in a Weighted Graph or: How to Optimally Read a Train Schedule,
    V. Vassilevska, invited to SODA Special Issue.

    		• SODA 2008 [ACM] [pdf]
  • All Pairs Bottleneck Paths in General Graphs in Truly Subcubic Time, V. Vassilevska, Ryan Williams, Raphael Yuster.

    		• STOC 2007 [ACM] [ps] [pdf]

  • Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems, V. Vassilevska, Ryan Williams, Raphael Yuster.

    		• ICALP 2006 [Springer] [pdf]

  • Finding a Maximum Weight Triangle in Sub-Cubic Time, With Applications, V. Vassilevska, Ryan Williams.

    		• STOC 2006 [ACM] [ps] [pdf]

  • Confronting Hardness Using A Hybrid Approach, V. Vassilevska, Ryan Williams, S. L. Maverick Woo.

    		• SODA 2006 [ACM] [pdf]

  • Explicit Inapproximability Bounds for the Shortest Superstring Problem, V. Vassilevska.
    		• MFCS 2005 [Springer] [ps]



Journal publications:

  • Subcubic Equivalences Between Path, Matrix, and Triangle Problems,
    V. Vassilevska Williams and Ryan Williams.

    		• Journal of the ACM, accepted in 2013 with minor revisions [preliminary version]

  • Finding, Minimizing and Counting Weighted Subgraphs, V. Vassilevska, Ryan Williams.

    		• SIAM J. Computing, 2013 [preliminary version]

  • Nondecreasing Paths in a Weighted Graph or: How to Optimally Read a Train Schedule, V. Vassilevska.

    		• ACM Transactions on Algorithms 2010
    SODA'08 Special Issue     		[TALG]

  • All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time, V. Vassilevska, Ryan Williams, Raphael Yuster.

    		• Theory of Computing 2009 [ToC]

  • Efficient Algorithms for Clique Problems, V. Vassilevska.

    		• Information Processing Letters 2009 [IPL] [ps] [pdf]
  • Finding Heaviest H-Subgraphs in Real Weighted Graphs, with Applications, V. Vassilevska, Ryan Williams, Raphael Yuster.

    		• ACM Transactions on Algorithms 2010 [ACM] [ps] [pdf]


Technical reports:

  • Finding Heaviest H-Subgraphs in Real Weighted Graphs, with Applications, V. Vassilevska, Ryan Williams, Raphael Yuster.

    		• arXiv Tech ReportarXiv
  • Confronting Hardness Using a Hybrid Approach, V. Vassilevska, Ryan Williams, Shan Leung Maverick Woo, Carnegie Mellon University Technical Report CMU-CS-05-125.

    		• Tech Report [pdf] [ps]