VW
Virginia Vassilevska Williams
cs.DScs.CCcs.DMmath.COcs.GTcs.AIcs.DCcs.LGcs.MAGraph embeddings
On Valency
published · living versionsW_s7c8pz9c·v1 · currentpublished
Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
with Josh Alman
1 version
Preprints & journals
93 papers in the corpus · 2010–2026When Shall We $k$ Meet Again? Tight Algorithms for Diameter and Radius under the Meet Distance2609.22569v1 · Yael Kirkpatrick, John Kuszmaul, Merey Temirzinova et al.2026 · 0 citationsarXiv
More Asymmetry Yields Faster Matrix Multiplication2404.16349v3 · Josh Alman, Ran Duan, Virginia Vassilevska Williams et al.2024 · 35 citationsarXiv
The Limits of Black-Box Reductions for All-Pairs Triangle Detection2608.19092v1 · Nathan Sheffield, Virginia Vassilevska Williams, Zoe Xi2026 · 0 citationsarXiv
Improving the matrix multiplication exponent with modern optimization and AlphaEvolve2608.16884v1 · Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii et al.2026 · 0 citationsarXiv
The Cost of Changing Edges for Diameter Computation and More2608.12628v1 · Sam Hiken, Yael Kirkpatrick, Jakob Nogler et al.2026 · 0 citationsarXiv
Tighter bounds for weighted and unweighted shortest cycle approximation2607.00938v3 · Avi Kadria, Liam Roditty, Virginia Vassilevska Williams2026 · 0 citationsarXiv
Improved Approximation Algorithms for n-Pairs Shortest Paths2607.02443v3 · Avi Kadria, Liam Roditty, Virginia Vassilevska Williams2026 · 0 citationsarXiv
Witness-Sensitive Detection of Induced Diamonds2605.09006v1 · Keren Censor-Hillel, Tomer Even, Virginia Vasillevska Williams et al.2026 · 0 citationsarXiv
Undirected Replacement Paths: Dual Fault Reduces to Single Source2605.02114v1 · Jakob Nogler, Virginia Vassilevska Williams2026 · 0 citationsarXiv
New Diameter Approximations via Distance Oracle Techniques2604.27142v1 · Yael Kirkpatrick, Liam Roditty, Richard Qi et al.2026 · 0 citationsarXiv
Factorization and pseudofactorization of weighted graphs.37213330 · Sheridan, Kristin, Berleant, Joseph, Bathe, Mark et al.2026 · 2 citationsDiscrete applied mathematics (Amsterdam, Netherlands : 1988). 2023;337:81-105
Isometric Hamming embeddings of weighted graphs.37982050 · Berleant, Joseph, Sheridan, Kristin, Condon, Anne et al.2026 · 3 citationsDiscrete applied mathematics (Amsterdam, Netherlands : 1988). 2023;332:119-128
Preprocessed 3SUM for Unknown Universes with Subquadratic Space2602.11363v1 · Yael Kirkpatrick, John Kuszmaul, Surya Mathialagan et al.2026 · 0 citationsarXiv
Improved Additive Approximation Algorithms for APSP2511.04775v1 · Ce Jin, Yael Kirkpatrick, Micha\l Stawarz et al.2025 · 0 citationsarXiv
Improved girth approximation in weighted undirected graphs2507.13869v1 · Avi Kadria, Liam Roditty, Aaron Sidford et al.2025 · 0 citationsarXiv
All-Pairs Shortest Paths with Few Weights per Node2506.20017v1 · Amir Abboud, Nick Fischer, Ce Jin et al.2025 · 1 citationarXiv
Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence2411.06502v3 · Jakob Nogler, Adam Polak, Barna Saha et al.2024 · 1 citationarXiv
Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More2503.21951v1 · Mina Dalirrooyfard, Andrea Lincoln, Barna Saha et al.2025 · 0 citationsarXiv
Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster2503.21655v1 · Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams2025 · 0 citationsarXiv
Beyond 2-approximation for k-Center in Graphs2503.09468v1 · Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams et al.2025 · 3 citationsarXiv
Faster Algorithms for Text-to-Pattern Hamming Distances2310.13174v3 · Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams et al.2023 · 3 citationsarXiv
Listing 6-Cycles in Sparse Graphs2411.07499v2 · Virginia Vassilevska Williams, Alek Westover2024 · 0 citationsarXiv
All-Hops Shortest Paths2410.23617v1 · Virginia Vassilevska Williams, Zoe Xi, Yinzhan Xu et al.2024 · 0 citationsarXiv
Fast Approximate Counting of Cycles2409.19292v1 · Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams2024 · 0 citationsarXiv
A Refined Laser Method and Faster Matrix Multiplication2010.05846v2 · Josh Alman, Virginia Vassilevska Williams2020 · 50 citationsTheoretiCS, Volume 3 (September 4, 2024) theoretics:11261
Faster Cycle Detection in the Congested Clique2408.15132v1 · Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams2024 · 0 citationsarXiv
Fine-Grained Optimality of Partially Dynamic Shortest Paths and More2407.09651v1 · Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu et al.2024 · 0 citationsarXiv
Detecting Disjoint Shortest Paths in Linear Time and More2404.15916v2 · Shyan Akmal, Virginia Vassilevska Williams, Nicole Wein2024 · 0 citationsarXiv
Additive Spanner Lower Bounds with Optimal Inner Graph Structure2404.18337v1 · Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams et al.2024 · 0 citationsarXiv
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques2307.15871v2 · Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams et al.2023 · 3 citationsarXiv
New Bounds for Matrix Multiplication: from Alpha to Omega2307.07970v2 · Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu et al.2023 · 89 citationsarXiv
Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation2310.20473v1 · Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams et al.2023 · 0 citationsarXiv
Fast 2-Approximate All-Pairs Shortest Paths2307.09258v2 · Michal Dory, Sebastian Forster, Yael Kirkpatrick et al.2023 · 0 citationsarXiv
Listing 6-Cycles2310.14575v1 · Ce Jin, Virginia Vassilevska Williams, Renfei Zhou2023 · 0 citationsarXiv
Simpler and Higher Lower Bounds for Shortcut Sets2310.12051v1 · Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu2023 · 2 citationsarXiv
Quasipolynomiality of the Smallest Missing Induced Subgraph2306.11185v2 · David Eppstein, Andrea Lincoln, Virginia Vassilevska Williams2023 · 0 citationsJ. Graph Algorithms & Applications 27 (5): 329-339, 2023
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product2110.15809v2 · Kevin Lu, Virginia Vassilevska Williams, Nicole Wein et al.2021 · 7 citationsarXiv
Approximating Min-Diameter: Standard and Bichromatic2308.08674v1 · Aaron Berger, Jenny Kaufmann, Virginia Vassilevska Williams2023 · 0 citationsarXiv
On Diameter Approximation in Directed Graphs2307.07583v1 · Amir Abboud, Mina Dalirrooyfard, Ray Li et al.2023 · 0 citationsarXiv
Faster Detours in Undirected Graphs2307.01781v1 · Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams et al.2023 · 1 citationarXiv
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More2303.14572v1 · Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu2023 · 5 citationsarXiv
Who Can Win a Single-Elimination Tournament?1511.08416v2 · Michael P. Kim, Warut Suksompong, Virginia Vassilevska Williams2015 · 29 citationsSIAM Journal on Discrete Mathematics, 31(3):1751-1764 (2017)
Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules2212.14173v1 · Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu2022 · 8 citationsarXiv
Approximation Algorithms and Hardness for $n$-Pairs Shortest Paths and All-Nodes Shortest Cycles2204.03076v2 · Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams et al.2022 · 4 citationsarXiv
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures2209.07016v1 · Virginia Vassilevska Williams, Eyob Woldeghebriel, Yinzhan Xu2022 · 0 citationsarXiv
Induced Cycles and Paths Are Harder Than You Think2209.01873v1 · Mina Dalirrooyfard, Virginia Vassilevska Williams2022 · 6 citationsarXiv
Hardness of Token Swapping on Trees2103.06707v2 · Oswin Aichholzer, Erik D. Demaine, Matias Korman et al.2021 · 4 citationsarXiv
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds2204.10932v1 · Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu2022 · 2 citationsarXiv
Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV2203.08356v2 · Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu2022 · 3 citationsarXiv
Isometric Hamming embeddings of weighted graphs2112.06994v2 · Joseph Berleant, Kristin Sheridan, Anne Condon et al.2021 · 3 citationsarXiv
Career total: 208 works. 93 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.