Virginia Vassilevska Williams
Publication record assembled from the DBLP archive of ranked conferences.
Papers indexed
101
Venues
14
Active years
2010–2026
Best venue rank
A*
Where they publish
Papers
101 indexed papers, newest first.
| Year | Venue | Title | Authors |
|---|---|---|---|
| 2026 | ESA | Improved Approximation Algorithms for n-Pairs Shortest Paths. | Avi Kadria, Liam Roditty, Virginia Vassilevska Williams |
| 2026 | ESA | Tighter Bounds for Weighted and Unweighted Shortest Cycle Approximation. | Avi Kadria, Liam Roditty, Virginia Vassilevska Williams |
| 2026 | ICALP | Witness-Sensitive Detection of Induced Diamonds. | Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams, Nathan Wallheimer |
| 2026 | ICALP | Preprocessed 3SUM for Unknown Universes with Subquadratic Space. | Yael Kirkpatrick, John Kuszmaul, Surya Mathialagan, Virginia Vassilevska Williams |
| 2026 | ICALP | New Diameter Approximations via Distance Oracle Techniques. | Yael Kirkpatrick, Liam Roditty, Richard Qi, Virginia Vassilevska Williams |
| 2026 | ICALP | Undirected Replacement Paths: Dual Fault Reduces to Single Source. | Jakob Nogler, Virginia Vassilevska Williams |
| 2026 | SODA | Improved Additive Approximation Algorithms for APSP. | Ce Jin, Yael Kirkpatrick, Michal Stawarz, Virginia Vassilevska Williams |
| 2025 | MFCS | Shortest Paths in Multimode Graphs. | Yael Kirkpatrick, Virginia Vassilevska Williams |
| 2025 | PODS | A Fine-Grained Approach to Algorithms and Complexity. | Virginia Vassilevska Williams |
| 2025 | SODA | Beyond 2-Approximation for | Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams, Nicole Wein |
| 2025 | SODA | More Asymmetry Yields Faster Matrix Multiplication. | Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou |
| 2025 | SODA | Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More. | Mina Dalirrooyfard, Andrea Lincoln, Barna Saha, Virginia Vassilevska Williams |
| 2025 | SODA | Fine-Grained Optimality of Partially Dynamic Shortest Paths and More. | Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, Christopher Ye |
| 2025 | SODA | All-Hops Shortest Paths. | Virginia Vassilevska Williams, Zoe Xi, Yinzhan Xu, Uri Zwick |
| 2025 | STOC | All-Pairs Shortest Paths with Few Weights per Node. | Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi |
| 2025 | STOC | Output-Sensitive Approximate Counting via a Measure-Bounded Hyperedge Oracle, or: How Asymmetry Helps Estimate k-Clique Counts Faster. | Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams |
| 2025 | STOC | Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence. | Jakob Nogler, Adam Polak, Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, Christopher Ye |
| 2024 | ICALP | Detecting Disjoint Shortest Paths in Linear Time and More. | Shyan Akmal, Virginia Vassilevska Williams, Nicole Wein |
| 2024 | ICALP | Additive Spanner Lower Bounds with Optimal Inner Graph Structure. | Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu |
| 2024 | ICALP | Fast Approximate Counting of Cycles. | Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams |
| 2024 | SODA | Fast 2-Approximate All-Pairs Shortest Paths. | Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams, Tijn de Vos |
| 2024 | SODA | Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation. | Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams, Zixuan Xu |
| 2024 | SODA | Simpler and Higher Lower Bounds for Shortcut Sets. | Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu |
| 2024 | SODA | New Bounds for Matrix Multiplication: from Alpha to Omega. | Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou |
| 2024 | STOC | Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques. | Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu |
| 2023 | ESA | On Diameter Approximation in Directed Graphs. | Amir Abboud, Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams |
| 2023 | ESA | Faster Detours in Undirected Graphs. | Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, Zixuan Xu |
| 2023 | ESA | Approximating Min-Diameter: Standard and Bichromatic. | Aaron Berger, Jenny Kaufmann, Virginia Vassilevska Williams |
| 2023 | FOCS | Faster Algorithms for Text-to-Pattern Hamming Distances. | Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, Yinzhan Xu |
| 2023 | SODA | Improved girth approximation in weighted undirected graphs. | Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick |
| 2023 | STOC | Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More. | Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu |
| 2022 | ESA | Hardness of Token Swapping on Trees. | Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masrov, Mikhail Rudoy, Virginia Vassilevska Williams, Nicole Wein |
| 2022 | FOCS | Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles. | Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams, Nicole Wein |
| 2022 | FOCS | Induced Cycles and Paths Are Harder Than You Think. | Mina Dalirrooyfard, Virginia Vassilevska Williams |
| 2022 | FOCS | Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure. | Virginia Vassilevska Williams, Eyob Woldeghebriel, Yinzhan Xu |
| 2022 | ICALP | New Additive Approximations for Shortest Paths and Cycles. | Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska Williams, Ziqian Zhong |
| 2022 | ICALP | Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds. | Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu |
| 2022 | IJCAI | Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules. | Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu |
| 2022 | MFCS | New Lower Bounds and Upper Bounds for Listing Avoidable Vertices. | Mingyang Deng, Virginia Vassilevska Williams, Ziqian Zhong |
| 2022 | SODA | Algorithmic trade-offs for girth approximation in undirected graphs. | Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick |
| 2022 | SODA | Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product. | Kevin Lu, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu |
| 2022 | STOC | Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV. | Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu |
| 2021 | FOCS | Hardness of Approximate Diameter: Now for Undirected Graphs. | Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams |
| 2021 | ICALP | Fine-Grained Hardness for Edit Distance to a Fixed Sequence. | Amir Abboud, Virginia Vassilevska Williams |
| 2021 | ICALP | Improved Approximation for Longest Common Subsequence over Small Alphabets. | Shyan Akmal, Virginia Vassilevska Williams |
| 2021 | ICALP | Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. | Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu |
| 2021 | ICALP | Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths. | Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, Yinzhan Xu |
| 2021 | SODA | A Refined Laser Method and Faster Matrix Multiplication. | Josh Alman, Virginia Vassilevska Williams |
| 2021 | SODA | New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners. | Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein |
| 2020 | FOCS | New Techniques for Proving Fine-Grained Average-Case Hardness. | Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams |
| 2020 | FOCS | Monochromatic Triangles, Triangle Listing and APSP. | Virginia Vassilevska Williams, Yinzhan Xu |
| 2020 | ICALP | Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph. | Mina Dalirrooyfard, Virginia Vassilevska Williams |
| 2020 | ICALP | Towards Optimal Set-Disjointness and Set-Intersection Data Structures. | Tsvi Kopelowitz, Virginia Vassilevska Williams |
| 2020 | OPODIS | Distributed Distance Approximation. | Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron, Virginia Vassilevska Williams |
| 2020 | SODA | Equivalences between triangle and range query problems. | Lech Duraj, Krzysztof Kleiner, Adam Polak, Virginia Vassilevska Williams |
| 2020 | SODA | Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications. | Virginia Vassilevska Williams, Yinzhan Xu |
| 2020 | STOC | New algorithms and hardness for incremental single-source shortest paths in directed graphs. | Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein |
| 2019 | CRYPTO | Public-Key Cryptography in the Fine-Grained Setting. | Rio LaVigne, Andrea Lincoln, Virginia Vassilevska Williams |
| 2019 | ICALP | Algorithms and Hardness for Diameter in Dynamic Graphs. | Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, Nicole Wein |
| 2019 | ICALP | Approximation Algorithms for Min-Distance Problems. | Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, Yuancheng Yu |
| 2019 | ICALP | Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems. | Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein |
| 2019 | ISSAC | Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. | Virginia Vassilevska Williams |
| 2019 | STOC | Graph pattern detection: hardness for all induced patterns and faster non-induced cycles. | Mina Dalirrooyfard, Thuy-Duong Vuong, Virginia Vassilevska Williams |
| 2018 | FOCS | Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. | Josh Alman, Virginia Vassilevska Williams |
| 2018 | ICDT | Fine-grained Algorithms and Complexity. | Virginia Vassilevska Williams |
| 2018 | SODA | Optimal Vertex Fault Tolerant Spanners (for fixed stretch). | Greg Bodwin, Michael Dinitz, Merav Parter, Virginia Vassilevska Williams |
| 2018 | SODA | Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. | Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams |
| 2018 | SODA | Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners. | Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, Virginia Vassilevska Williams |
| 2018 | STOC | Towards tight approximation bounds for graph diameter and eccentricities. | Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein |
| 2017 | AAAI | Complexity of the Stable Invitations Problem. | Hooyeon Lee, Virginia Vassilevska Williams |
| 2017 | ICALP | Dynamic Parameterized Problems and Algorithms. | Josh Alman, Matthias Mnich, Virginia Vassilevska Williams |
| 2017 | ICALP | Preserving Distances in Very Faulty Graphs. | Greg Bodwin, Fabrizio Grandoni, Merav Parter, Virginia Vassilevska Williams |
| 2016 | AAAI | Who Can Win a Single-Elimination Tournament? | Michael P. Kim, Warut Suksompong, Virginia Vassilevska Williams |
| 2016 | ESA | A 7/3-Approximation for Feedback Vertex Sets in Tournaments. | Matthias Mnich, Virginia Vassilevska Williams, Lszl A. Vgh |
| 2016 | FOCS | Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. | Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams |
| 2016 | ICALP | Deterministic Time-Space Trade-Offs for k-SUM. | Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams |
| 2016 | MFCS | RNA-Folding - From Hardness to Algorithms. | Virginia Vassilevska Williams |
| 2016 | SODA | Subtree Isomorphism Revisited. | Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir |
| 2016 | SODA | Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. | Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang |
| 2016 | SODA | Better Distance Preservers and Additive Spanners. | Greg Bodwin, Virginia Vassilevska Williams |
| 2016 | STOC | Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. | Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams |
| 2016 | STACS | Fine-Grained Algorithms and Complexity (Invited Talk). | Virginia Vassilevska Williams |
| 2015 | FOCS | Tight Hardness Results for LCS and Other Sequence Similarity Measures. | Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams |
| 2015 | FOCS | If the Current Clique Algorithms are Optimal, So is Valiant's Parser. | Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams |
| 2015 | IJCAI | Fixing Tournaments for Kings, Chokers, and More. | Michael P. Kim, Virginia Vassilevska Williams |
| 2015 | SODA | Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter. | Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams |
| 2015 | SODA | Finding Four-Node Subgraphs in Triangle Time. | Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, Huacheng Yu |
| 2015 | STOC | Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. | Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu |
| 2014 | FOCS | Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. | Amir Abboud, Virginia Vassilevska Williams |
| 2014 | ICALP | Consequences of Faster Alignment of Sequences. | Amir Abboud, Virginia Vassilevska Williams, Oren Weimann |
| 2014 | ICALP | Listing Triangles. | Andreas Bjrklund, Rasmus Pagh, Virginia Vassilevska Williams, Uri Zwick |
| 2014 | SODA | Better Approximation Algorithms for the Graph Diameter. | Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, Virginia Vassilevska Williams |
| 2013 | STOC | Fast approximation algorithms for the diameter and radius of sparse graphs. | Liam Roditty, Virginia Vassilevska Williams |
| 2012 | FOCS | Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths. | Fabrizio Grandoni, Virginia Vassilevska Williams |
| 2012 | SODA | Subquadratic time approximation algorithms for the girth. | Liam Roditty, Virginia Vassilevska Williams |
| 2012 | STOC | Multiplying matrices faster than coppersmith-winograd. | Virginia Vassilevska Williams |
| 2011 | FOCS | Minimum Weight Cycles and Triangles: Equivalences and Algorithms. | Liam Roditty, Virginia Vassilevska Williams |
| 2011 | IJCAI | Rigging Tournament Brackets for Weaker Players. | Isabelle Stanton, Virginia Vassilevska Williams |
| 2011 | SODA | Faster Replacement Paths. | Virginia Vassilevska Williams |
| 2010 | AAAI | Fixing a Tournament. | Virginia Vassilevska Williams |
| 2010 | FOCS | Subcubic Equivalences between Path, Matrix and Triangle Problems. | Virginia Vassilevska Williams, Ryan Williams |