Publications

Under Submission:
  • Various working papers on graph problems.


Published Articles by Year:

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

  • ICALP


    [pdf]

  • Consequences of faster sequence alignment, Amir Abboud, V. Vassilevska Williams, Oren Weimann.

  • ICALP


    [pdf]

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

  • SODA


    [pdf]

2013:
  • The Structure, Efficacy and Manipulation of Double-Elimination Tournaments ,
    Isabelle Stanton and V. Vassilevska Williams.

  • Journal of Quantitative Analysis in Sports, accepted. [to come]

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

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

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

  • SIAM J. Computing [preliminary version]

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

  • STOC


    [pdf]

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

  • FOCS


    [pdf]

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

  • STOC


    to come

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

  • SODA


    [pdf]

2011:
  • Manipulating Stochastically Generated Single-Elimination Tournaments for Nearly All Players,
    Isabelle Stanton and V. Vassilevska Williams

  • WINE


    [pdf]

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

  • FOCS


    arXiv version

  • Manipulating single-elimination tournaments in the Braverman-Mossel model,
    Isabelle Stanton and V. Vassilevska Williams.

  • IJCAI Workshop on Social Choice and AI


    to come

  • Rigging tournament brackets for weaker players,
    Isabelle Stanton and V. Vassilevska Williams.

  • IJCAI (technical program)
    Preliminary version in Computational Social Science and the Wisdom of Crowds (NIPS 2010).

    [pdf]

  • Faster replacement paths, V. Vassilevska Williams.

  • SODA [SIAM] Preliminary version: [arXiv]

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

  • FOCS [IEEE] [pdf]
    [full version]

  • Fixing a tournament, V. Vassilevska Williams.

  • AAAI [AAAI] [ps] [pdf]

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

  • ACM Transactions on Algorithms
    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 [ToC]

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

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

2008:
  • Efficient Algorithms for Clique Problems, V. Vassilevska.

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

  • ACM Transactions on Algorithms [ACM] [ps] [pdf]
  • A New Combinatorial Approach to Sparse Graph Problems, Guy Blelloch, V. Vassilevska, Ryan Williams.

  • ICALP [Springer] [ps] [pdf]
  • Uniquely Represented Data Structures for Computational Geometry, Guy Blelloch, Daniel Golovin, V. Vassilevska.

  • SWAT [Springer] [ps] [pdf]
  • Uniquely Represented Data Structures for Computational Geometry, Guy Blelloch, Daniel Golovin, V. Vassilevska, Carnegie Mellon University Technical Report CMU-CS-08-115.

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

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

  • STOC [ACM] [ps] [pdf]

  • A Two Player Game to Combat WebSpam, Michelle Goodstein, V. Vassilevska, Carnegie Mellon University Technical Report CMU-CS-07-134.

  • Tech Report [pdf]

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

  • ICALP [Springer] [pdf]

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

  • STOC [ACM] [ps] [pdf]

  • Finding Heaviest H-Subgraphs in Real Weighted Graphs, with Applications, V. Vassilevska, Ryan Williams, Raphael Yuster, arXiv Technical Report: http://www.citebase.org/abstract?id=oai:arXiv.org:cs/0609009.

  • arXiv Tech Report
  • Confronting Hardness Using A Hybrid Approach, V. Vassilevska, Ryan Williams, S. L. Maverick Woo.
  • SODA [ACM] [pdf]

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

  • 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]
  • Finding Nonoverlapping Dense Blocks of a Sparse Matrix, Ali Pinar, V. Vassilevska, the special issue of ETNA on Combinatorial Scientific Computing, 2005.
  • Electronic Transactions on Numerical Analysis [ETNA]