Publications

Under Submission:
  • Various working papers on graph, matrix and fine-grained complexity problems.


Published Articles by Year:

2024:
  • Additive Spanner Lower Bounds with Optimal Inner Graph Structure, Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein and Zixuan Xu.

    		• ICALP


    		[TO COME]

  • Fast Approximate Counting of Cycles, Keren Censor-Hillel, Tomer Even and Virginia Vassilevska Williams.

    		• ICALP


    		[TO COME]

  • Detecting Disjoint Shortest Paths in Linear Time and More, Shyan Akmal, Virginia Vassilevska Williams and Nicole Wein.

    		• ICALP


    		[TO COME]

  • Towards Optimal Output-Sensitive Clique Listing (a.k.a. Listing Cliques from Smaller Cliques), Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams and Yinzhan Xu.

    		• STOC


    		[arXiv]

  • Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation, Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams and Zixuan Xu.

    		• SODA


    		[arXiv]

  • Simpler and Higher Lower Bounds for Shortcut Sets, Virginia Vassilevska Williams, Yinzhan Xu and Zixuan Xu.

    		• SODA


    		[arXiv]

  • New Bounds for Matrix Multiplication: from Alpha to Omega, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Renfei Zhou.

    		• SODA


    		[arXiv]

  • Fast 2-Approximate All-Pairs Shortest Paths, Michael Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams and Tijn de Vos.

    		• SODA


    		[arXiv]

  • Listing 6-Cycles, Ce Jin, Virginia Vassilevska Williams and Renfei Zhou.

    		• SOSA


    		[arXiv]

2023:
  • Quasipolynomiality of the Smallest Missing Induced Subgraph, David Eppstein, Andrea Lincoln and Virginia Vassilevska Williams.

    		• Journal of Graph Algorithms and Applications.


    		[JGAA]

  • Faster Algorithms for Text-to-Pattern Hamming Distances, Timothy Chan, Ce Jin, Virginia Vassilevska Williams and Yinzhan Xu.

    		• FOCS


    		[arXiv]

  • Faster Detours in Undirected Graphs, Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams and Zixuan Xu.

    		• ESA


    		[arXiv]

  • Approximating Min-Diameter: Standard and Bichromatic, Aaron Berger, Jenny Kaufmann and Virginia Vassilevska Williams.

    		• ESA


    		[arXiv]

  • On Diameter Approximation in Directed Graphs, Amir Abboud, Mina Dalirrooyfard, Ray Li and Virginia Vassilevska Williams.

    		• ESA


    		[arXiv]

  • Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More, Timothy Chan, Virginia Vassilevska Williams and Yinzhan Xu.

    		• STOC


    		[arXiv]

  • Improved girth approximation in weighted undirected graphs, Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams and Uri Zwick.

    		• SODA


    		[SIAM pdf]

2022:
  • Induced Cycles and Paths Are Harder Than You Think, Mina Dalirooyfard and Virginia Vassilevska Williams.

    		• FOCS


    		[arXiv]

  • Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles, Mina Dalirooyfard, Ce Jin, Virginia Vassilevska Williams and Nicole Wein.

    		• FOCS


    		[arXiv]

  • Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures, Virginia Vassilevska Williams, Eyob Woldeghebriel and Yinzhan Xu.

    		• FOCS


    		[arXiv]

  • Hardness of Token Swapping on Trees, Oswin Aichholzer, Erik Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masarova, Mikhail Rudoy, Virginia Vassilevska Williams and Nicole Wein.

    		• ESA


    		[arXiv]

  • New Lower Bounds and Upper Bounds for Listing Avoidable Vertices, MingYang Deng, V. Vassilevska Williams and Ziqian Zhong.

    		• MFCS


    		[MFCS pdf]

  • Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules, Krzysztof Sornat, V. Vassilevska Williams and Yinzhan Xu.

    		• IJCAI


    		[arXiv]

  • New additive approximations for shortest paths and cycles, MingYang Deng, Yael Kirkpatrick, Victor Rong, V. Vassilevska Williams and Ziqian Zhong.

    		• ICALP


    		[ICALP pdf]

  • Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds, Surya Mathialagan, V. Vassilevska Williams and Yinzhan Xu.

    		• ICALP


    		[arXiv]

  • Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV, Timothy Chan, V. Vassilevska Williams and Yinzhan Xu.

    		• STOC


    		[arXiv]

  • Dynamic Matching Algorithms Under Vertex Updates, Hung Le, Lazar Milenkovic, Shay Solomon and V. Vassilevska Williams.

    		• ITCS


    		[itcs]

  • Algorithmic trade-offs for girth approximation in undirected graphs, Avi Kadria, Liam Roditty, Aaron Sidford, V. Vassilevska Williams and Uri Zwick.

    		• SODA


    		[SIAM pdf]

  • Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product, Kevin Lu, V. Vassilevska Williams, Nicole Wein and Zixuan Xu.

    		• SODA


    		[arXiv]

2021:
  • Hardness of Approximate Diameter: Now for Undirected Graphs, Mina Dalirrooyfard, Ray Li and V. Vassilevska Williams.

    		• FOCS


    		[arXiv]

  • Fine-Grained Complexity and Algorithms for the Schulze Voting Method, Krzystof Sornat, V. Vassilevska Williams, and Yinzhan Xu.

    		• EC


    		[arXiv]

  • Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths, Timothy Chan, V. Vassilevska Williams, and Yinzhan Xu.

    		• ICALP


    		[arXiv]

  • Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths, Yuzhou Gu, Adam Polak, V. Vassilevska Williams, and Yinzhan Xu.

    		• ICALP


    		[arXiv]

  • Improved Approximation for Longest Common Subsequence over Small Alphabets, Shyan Akmal and V. Vassilevska Williams.

    		• ICALP


    		[arXiv]

  • Fine-Grained Hardness for Edit Distance to a Fixed Sequence, Amir Abboud and V. Vassilevska Williams.

    		• ICALP


    		[ICALP version]

  • A Refined Laser Method and Faster Matrix Multiplication, Josh Alman and V. Vassilevska Williams.

    		• SODA


    		[arXiv]

  • New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners, Thiago Bergamaschi, Monika Henzinger, Max Probst Gutenberg, V. Vassilevska Williams and Nicole Wein.

    		• SODA


    		[arXiv]

2020:
  • Distributed Distance Approximation, Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron and V. Vassilevska Williams.

    		• OPODIS


    		[arXiv]

  • New Techniques for Proving Fine-Grained Average-Case Hardness, Mina Dalirrooyfard, Andrea Lincoln and V. Vassilevska Williams.

    		• FOCS


    		[arXiv]

  • Monochromatic Triangles, Triangle Listing and APSP, V. Vassilevska Williams and Yinzhan Xu.

    		• FOCS


    		[arXiv]

  • Towards Optimal Set-Disjointness and Set-Intersection Data Structures, Tsvi Kopelowitz and V. Vassilevska Williams.

    		• ICALP


    		[ICALP version]

  • Conditionally optimal approximation algorithms for the girth of a directed graph, Mina Dalirrooyfard and V. Vassilevska Williams.

    		• ICALP


    		[ICALP version]

  • New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs, Maximilian Probst, V. Vassilevska Williams and Nicole Wein.

    		• STOC


    		[pdf]

  • OV graphs are (probably) hard instances, Josh Alman and V. Vassilevska Williams.

    		• ITCS


    		[pdf]

  • Monochromatic triangles, intermediate matrix products, and convolutions, Andrea Lincoln, Adam Polak and V. Vassilevska Williams.

    		• ITCS


    		[pdf]

  • Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications, V. Vassilevska Williams and Yinzhan Xu.

    		• SODA


    		[pdf]

  • Equivalences between Triangle and Range Query Problems, Lech Duraj, Krzysztof Kleiner, Adam Polak and V. Vassilevska Williams.

    		• SODA


    		[pdf]

2019:
  • Bribery in Balanced Knockout Tournaments, Christine Konicki and V. Vassilevska Williams.

    		• AAMAS


    		[AAMAS version]

  • Public-Key Cryptography in the Fine-Grained Setting, Rio LaVigne, Andrea Lincoln and V. Vassilevska Williams.

    		• CRYPTO


    		[ePrint]

  • Algorithms and Hardness for Diameter in Dynamic Graphs, Bertie Ancona, Monika Henzinger, Liam Roditty, V. Vassilevska Williams and Nicole Wein.

    		• ICALP


    		[pdf]

  • Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems, Mina Dalirrooyfard, V. Vassilevska Williams, Nikhil Vyas and Nicole Wein.

    		• ICALP


    		[pdf]

  • Approximation Algorithms for Min-Distance Problems, Mina Dalirrooyfard, V. Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu and Yuancheng Yu.

    		• ICALP


    		[pdf]

  • Graph Pattern Detection: Hardness for all Induced Patterns and Faster Non-induced Cycles, Mina Dalirrooyfard, Thuy-Duong Vuong and V. Vassilevska Williams.

    		• STOC


    		[pdf]

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

    		• FOCS


    		[pdf]

  • Towards Tight Approximation Bounds for Graph Diameter and Eccentricities, Arturs Backurs, Liam Roditty, G. Segal, V. Vassilevska Williams and Nicole Wein.

    		• STOC


    		[pdf]

  • Further Limitations of the Known Approaches for Matrix Multiplication, Josh Alman and V. Vassilevska Williams.

    		• ITCS


    		[arXiv]

  • 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


    		[arXiv]

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

    		• SODA


    		[arXiv]

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

    		• SODA


    		[arXiv]

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

    		• SODA


    		[arXiv]

  • Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures, Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, Yuancheng Yu.

    		• SWAT


    		[SWAT version]

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

    		• ICALP


    		[arXiv]

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

    		• ICALP


    		[arXiv]

  • Parameterized Complexity of Group Activity Selection, Haden Lee and V. Vassilevska Williams.

    		• AAMAS


    		[AAMAS version]

  • Complexity of the Stable Invitations Problem, Haden Lee and V. Vassilevska Williams.

    		• AAAI


    		[AAAI version]

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

    		• ITCS


    		[ITCS version]

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

    		• ITCS


    		[arXiv]

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