Publications in graph and matrix algorithms


Conference publications:

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

    		• ITCS 2016


    		[to come]

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

    		• ITCS 2016


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

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