Publications in graph and matrix algorithms


Conference publications:

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

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