Virginia Vassilevska Williams

ORCID

Publication Activity (10 Years)

Years Active: 2004-2023
Publications (10 Years): 165

Top Venues

Publications

Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, Zixuan Xu
Faster Detours in Undirected Graphs. ESA (2023)
David Eppstein, Andrea Lincoln, Virginia Vassilevska Williams
Quasipolynomiality of the Smallest Missing Induced Subgraph. J. Graph Algorithms Appl. 27 (5) (2023)
Aaron Berger, Jenny Kaufmann, Virginia Vassilevska Williams
Approximating Min-Diameter: Standard and Bichromatic. CoRR (2023)
Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick
Improved girth approximation in weighted undirected graphs. SODA (2023)
Shyan Akmal, Virginia Vassilevska Williams, R. Ryan Williams, Zixuan Xu
Faster Detours in Undirected Graphs. CoRR (2023)
Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter. ACM Trans. Algorithms 19 (1) (2023)
David Eppstein, Andrea Lincoln, Virginia Vassilevska Williams
Quasipolynomiality of the Smallest Missing Induced Subgraph. CoRR (2023)
Ce Jin, Virginia Vassilevska Williams, Renfei Zhou
Listing 6-Cycles. CoRR (2023)
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More. CoRR (2023)
Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams, Zixuan Xu
Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation. CoRR (2023)
Joseph Berleant, Kristin Sheridan, Anne Condon, Virginia Vassilevska Williams, Mark Bathe
Isometric Hamming embeddings of weighted graphs. Discret. Appl. Math. 332 (2023)
Kristin Sheridan, Joseph Berleant, Mark Bathe, Anne Condon, Virginia Vassilevska Williams
Factorization and pseudofactorization of weighted graphs. Discret. Appl. Math. 337 (2023)
Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, Yinzhan Xu
Faster Algorithms for Text-to-Pattern Hamming Distances. FOCS (2023)
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu
Simpler and Higher Lower Bounds for Shortcut Sets. CoRR (2023)
Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams, Tijn de Vos
Fast 2-Approximate All-Pairs Shortest Paths. CoRR (2023)
Josh Alman, Virginia Vassilevska Williams
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. SIAM J. Comput. 52 (6) (2023)
Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu
Listing Cliques from Smaller Cliques. CoRR (2023)
Aaron Berger, Jenny Kaufmann, Virginia Vassilevska Williams
Approximating Min-Diameter: Standard and Bichromatic. ESA (2023)
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou
New Bounds for Matrix Multiplication: from Alpha to Omega. CoRR (2023)
Amir Abboud, Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams
On Diameter Approximation in Directed Graphs. ESA (2023)
Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, Yinzhan Xu
Faster Algorithms for Text-to-Pattern Hamming Distances. CoRR (2023)
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More. STOC (2023)
Amir Abboud, Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams
On Diameter Approximation in Directed Graphs. CoRR (2023)
Hung Le, Lazar Milenkovic, Shay Solomon, Virginia Vassilevska Williams
Dynamic Matching Algorithms Under Vertex Updates. ITCS (2022)
Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams, Nicole Wein
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles. CoRR (2022)
Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu
Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules. CoRR (2022)
Virginia Vassilevska Williams, Eyob Woldeghebriel, Yinzhan Xu
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure. FOCS (2022)
Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska Williams, Ziqian Zhong
New Additive Approximations for Shortest Paths and Cycles. ICALP (2022)
Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams
Hardness of Approximate Diameter: Now for Undirected Graphs. FOCS (2022)
Mina Dalirrooyfard, Virginia Vassilevska Williams
Induced Cycles and Paths Are Harder Than You Think. FOCS (2022)
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV. CoRR (2022)
Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds. CoRR (2022)
Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds. ICALP (2022)
Virginia Vassilevska Williams, Eyob Woldeghebriel, Yinzhan Xu
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures. CoRR (2022)
Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams, Nicole Wein
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles. FOCS (2022)
Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick
Algorithmic trade-offs for girth approximation in undirected graphs. SODA (2022)
Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, Nicole Wein
Hardness of Token Swapping on Trees. ESA (2022)
Mingyang Deng, Virginia Vassilevska Williams, Ziqian Zhong
New Lower Bounds and Upper Bounds for Listing Avoidable Vertices. MFCS (2022)
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV. STOC (2022)
Mina Dalirrooyfard, Virginia Vassilevska Williams
Induced Cycles and Paths Are Harder Than You Think. CoRR (2022)
Kevin Lu, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product. SODA (2022)
Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu
Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules. IJCAI (2022)
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. CoRR (2021)
Shyan Akmal, Virginia Vassilevska Williams
Improved Approximation for Longest Common Subsequence over Small Alphabets. ICALP (2021)
Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu
Fine-Grained Complexity and Algorithms for the Schulze Voting Method. EC (2021)
Amir Abboud, Virginia Vassilevska Williams
Fine-Grained Hardness for Edit Distance to a Fixed Sequence. ICALP (2021)
Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein
Toward Tight Approximation Bounds for Graph Diameter and Eccentricities. SIAM J. Comput. 50 (4) (2021)
Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners. SODA (2021)
Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams
Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles. SIAM J. Comput. 50 (5) (2021)
Virginia Vassilevska Williams
EATCS-IPEC Nerode Prize - Call for Nominations. Bull. EATCS 133 (2021)
Kristin Sheridan, Joseph Berleant, Mark Bathe, Anne Condon, Virginia Vassilevska Williams
Factorization and pseudofactorization of weighted graphs. CoRR (2021)
Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu
Fine-Grained Complexity and Algorithms for the Schulze Voting Method. CoRR (2021)
Oswin Aichholzer, Erik D. Demaine, Matias Korman, Jayson Lynch, Anna Lubiw, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, Nicole Wein
Hardness of Token Swapping on Trees. CoRR (2021)
Shyan Akmal, Virginia Vassilevska Williams
Improved Approximation for Longest Common Subsequence over Small Alphabets. CoRR (2021)
Kevin Lu, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product. CoRR (2021)
Greg Bodwin, Virginia Vassilevska Williams
Better Distance Preservers and Additive Spanners. ACM Trans. Algorithms 17 (4) (2021)
Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, Yinzhan Xu
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths. ICALP (2021)
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. ICALP (2021)
Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, Yinzhan Xu
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths. CoRR (2021)
Virginia Vassilevska Williams
3SUM and Related Problems in Fine-Grained Complexity (Invited Talk). SoCG (2021)
Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams
Hardness of Approximate Diameter: Now for Undirected Graphs. FOCS (2021)
Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams
Hardness of Approximate Diameter: Now for Undirected Graphs. CoRR (2021)
Joseph Berleant, Kristin Sheridan, Anne Condon, Virginia Vassilevska Williams, Mark Bathe
Isometric Hamming embeddings of weighted graphs. CoRR (2021)
Josh Alman, Virginia Vassilevska Williams
A Refined Laser Method and Faster Matrix Multiplication. SODA (2021)
Mina Dalirrooyfard, Virginia Vassilevska Williams
Conditionally optimal approximation algorithms for the girth of a directed graph. CoRR (2020)
Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions. CoRR (2020)
Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners. CoRR (2020)
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs. CoRR (2020)
Josh Alman, Matthias Mnich, Virginia Vassilevska Williams
Dynamic Parameterized Problems and Algorithms. ACM Trans. Algorithms 16 (4) (2020)
Josh Alman, Virginia Vassilevska Williams
A Refined Laser Method and Faster Matrix Multiplication. CoRR (2020)
Josh Alman, Virginia Vassilevska Williams
OV Graphs Are (Probably) Hard Instances. ITCS (2020)
Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron, Virginia Vassilevska Williams
Distributed Distance Approximation. OPODIS (2020)
Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron, Virginia Vassilevska Williams
Distributed Distance Approximation. CoRR (2020)
Fabrizio Grandoni, Virginia Vassilevska Williams
Faster Replacement Paths and Distance Sensitivity Oracles. ACM Trans. Algorithms 16 (1) (2020)
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
New Techniques for Proving Fine-Grained Average-Case Hardness. FOCS (2020)
Virginia Vassilevska Williams, Yinzhan Xu
Monochromatic Triangles, Triangle Listing and APSP. FOCS (2020)
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
New Techniques for Proving Fine-Grained Average-Case Hardness. CoRR (2020)
Virginia Vassilevska Williams, Yinzhan Xu
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications. SODA (2020)
Virginia Vassilevska Williams, Yinzhan Xu
Monochromatic Triangles, Triangle Listing and APSP. CoRR (2020)
Lech Duraj, Krzysztof Kleiner, Adam Polak, Virginia Vassilevska Williams
Equivalences between triangle and range query problems. SODA (2020)
Mina Dalirrooyfard, Virginia Vassilevska Williams
Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph. ICALP (2020)
Tsvi Kopelowitz, Virginia Vassilevska Williams
Towards Optimal Set-Disjointness and Set-Intersection Data Structures. ICALP (2020)
Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions. ITCS (2020)
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
New algorithms and hardness for incremental single-source shortest paths in directed graphs. STOC (2020)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, Yuancheng Yu
Approximation Algorithms for Min-Distance Problems. ICALP (2019)
Jianer Chen, Hans L. Bodlaender, Virginia Vassilevska Williams
EATCS-IPEC Nerode Prize 2019 - Call for Nominations. Bull. EATCS 127 (2019)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems. CoRR (2019)
Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, Nicole Wein
Algorithms and Hardness for Diameter in Dynamic Graphs. ICALP (2019)
Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams
Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles. CoRR (2019)
Lech Duraj, Krzysztof Kleiner, Adam Polak, Virginia Vassilevska Williams
Equivalences between triangle and range query problems. CoRR (2019)
Christine Konicki, Virginia Vassilevska Williams
Bribery in Balanced Knockout Tournaments. AAMAS (2019)
Virginia Vassilevska Williams
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. ISSAC (2019)
Rio LaVigne, Andrea Lincoln, Virginia Vassilevska Williams
Public-Key Cryptography in the Fine-Grained Setting. IACR Cryptol. ePrint Arch. 2019 (2019)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, Yuancheng Yu
Approximation Algorithms for Min-Distance Problems. CoRR (2019)
Dániel Marx, Virginia Vassilevska Williams, Neal E. Young
Introduction to the Special Issue on SODA 2017. ACM Trans. Algorithms 15 (2) (2019)
Virginia Vassilevska Williams, Yinzhan Xu
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications. CoRR (2019)
Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams
Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product. SIAM J. Comput. 48 (2) (2019)
Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams
Graph pattern detection: hardness for all induced patterns and faster non-induced cycles. STOC (2019)
Aviad Rubinstein, Virginia Vassilevska Williams
SETH vs Approximation. SIGACT News 50 (4) (2019)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems. ICALP (2019)

Virginia Vassilevska Williams.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Virginia Vassilevska Williams