Publications in graph and matrix algorithms


Conference publications:

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

  • FOCS 2018


    [to come]

  • 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


    [to come]

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

  • ITCS 2018


    [to come]

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

  • SODA 2018


    [to come]

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

  • SODA 2018


    [to come]

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

  • SODA 2018


    [to come]

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

  • ICALP 2017


    [to come]

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

  • ICALP 2017


    [to come]

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

  • ITCS 2017


    [to come]

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

  • ITCS 2017


    [to come]

  • 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]