Publications Under Submission: Various working papers on graph problems. Published Articles by Year: 2017: Complexity of the Stable Invitations Problem, Haden Lee and V. Vassilevska Williams. AAAI [to come] Metatheorems for dynamic weighted matching, Daniel Stubbs and V. Vassilevska Williams. ITCS [to come] Conditional hardness for sensitivity problems, Monika Henzinger, Andrea Lincoln, Stefan Neumann and V. Vassilevska Williams. ITCS [to come] 2016: 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 [pdf] A 7/3-Approximation for Feedback Vertex Sets in Tournaments, Matthias Mnich, V. Vassilevska Williams and Laszlo Vegh. ESA [pdf] Deterministic Time-Space Tradeoffs for k-SUM, Andrea Lincoln, V. Vassilevska Williams, Josh R. Wang and Ryan Williams. ICALP [pdf] Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made, Amir Abboud, Thomas D. Hansen, V. Vassilevska Williams and Ryan Williams. STOC [pdf] Who Can Win a Single-Elimination Tournament?, Michael P. Kim, Warut Suksompong and V. Vassilevska Williams. AAAI [pdf] Subtree Isomorphism Revisited, Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, V. Vassilevska Williams, Or Zamir. SODA [pdf] Better Distance Preservers and Additive Spanners, Greg Bodwin and V. Vassilevska Williams. SODA [pdf] Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs, Amir Abboud, Josh Wang, V. Vassilevska Williams. SODA [pdf] 2015: Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis, V. Vassilevska Williams. IPEC/ALGO Invited Paper [pdf] Tight Hardness Results for LCS and other Sequence Similarity Measures, Amir Abboud, Arturs Backurs, V. Vassilevska Williams. FOCS [pdf] If the Current Clique Algorithms are Optimal, so is Valiant's Parser, Amir Abboud, Arturs Backurs, V. Vassilevska Williams. FOCS [pdf] Fixing tournaments for kings, chokers and more, Michael P. Kim and V. Vassilevska Williams. IJCAI [pdf] Matching triangles and basing hardness on an extremely popular conjecture, Amir Abboud, V. Vassilevska Williams and Huacheng Yu. STOC [pdf] Very sparse additive spanners and emulators, Greg Bodwin and V. Vassilevska Williams. ITCS [pdf] Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter, Amir Abboud, Fabrizio Grandoni and V. Vassilevska Williams. SODA [pdf] Finding four-node subgraphs in triangle time, V. Vassilevska Williams, Josh Wang, Ryan Williams and Huacheng Yu. SODA [pdf] 2014: Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems, Amir Abboud and V. Vassilevska Williams. FOCS [pdf] 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]