SU\G(𝔸)/K·U

Author Description

Login to generate an author description

Ask a Question About This Mathematician

All published works (162)

Action Title Date Authors
+ PDF Ask
More Asymmetry Yields Faster Matrix Multiplication 2025-01-01 Josh Alman Ran Duan Virginia Vassilevska Williams Yinzhan Xu Zixuan Xu Renfei Zhou
+
Fine-Grained Optimality of Partially Dynamic Shortest Paths and More 2025-01-01 Barna Saha Virginia Vassilevska Williams Yinzhan Xu Christopher Ye
+ PDF Ask
Hardness of Approximate Diameter: Now for Undirected Graphs 2024-11-15 Mina Dalirrooyfard Ray Li Virginia Vassilevska Williams
+ PDF Ask
Listing 6-Cycles in Sparse Graphs 2024-11-11 Virginia Vassilevska Williams Alek Westover
+ PDF Ask
Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence 2024-11-10 Jakob Nogler Adam Polak Barna Saha Virginia Vassilevska Williams Yinzhan Xu Christopher Ye
+ PDF Ask
All-Hops Shortest Paths 2024-10-31 Virginia Vassilevska Williams Zoe Xi Yinzhan Xu Uri Zwick
+ PDF Ask
Fast Approximate Counting of Cycles 2024-09-28 Keren Censor-Hillel Tomer Even Virginia Vassilevska Williams
+ PDF Ask
Faster Cycle Detection in the Congested Clique 2024-08-27 Keren Censor-Hillel Tomer Even Virginia Vassilevska Williams
+ PDF Ask
Fine-Grained Optimality of Partially Dynamic Shortest Paths and More 2024-07-12 Barna Saha Virginia Vassilevska Williams Yinzhan Xu Christopher Ye
+ PDF Ask
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques 2024-06-10 Mina Dalirrooyfard Surya Mathialagan Virginia Vassilevska Williams Yinzhan Xu
+ PDF Ask
Additive Spanner Lower Bounds with Optimal Inner Graph Structure 2024-04-28 Greg Bodwin Gary Hoppenworth Virginia Vassilevska Williams Nicole Wein Zixuan Xu
+ PDF Ask
More Asymmetry Yields Faster Matrix Multiplication 2024-04-25 Josh Alman Ran Duan Virginia Vassilevska Williams Yinzhan Xu Zixuan Xu Renfei Zhou
+ PDF Ask
Detecting Disjoint Shortest Paths in Linear Time and More 2024-04-24 Shyan Akmal Virginia Vassilevska Williams Nicole Wein
+ PDF Ask
New Bounds for Matrix Multiplication: from Alpha to Omega 2024-01-01 Virginia Vassilevska Williams Yinzhan Xu Zixuan Xu Renfei Zhou
+ PDF Ask
Simpler and Higher Lower Bounds for Shortcut Sets 2024-01-01 Virginia Vassilevska Williams Yinzhan Xu Zixuan Xu
+ PDF Ask
Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation 2024-01-01 Alina Harbuzova Ce Jin Virginia Vassilevska Williams Zixuan Xu
+ PDF Ask
Fast 2-Approximate All-Pairs Shortest Paths 2024-01-01 Michal Dory Sebastian Förster Yael Kirkpatrick Yasamin Nazari Virginia Vassilevska Williams Tijn de Vos
+
Listing 6-Cycles 2024-01-01 Ce Jin Virginia Vassilevska Williams Renfei Zhou
+ PDF Ask
Faster Algorithms for Text-to-Pattern Hamming Distances 2023-11-06 Timothy M. Chan Ce Jin Virginia Vassilevska Williams Yinzhan Xu
+ PDF Ask
Quasipolynomiality of the Smallest Missing Induced Subgraph 2023-07-01 David Eppstein Andrea Lincoln Virginia Vassilevska Williams
+ PDF Ask
Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More 2023-05-16 Timothy M. Chan Virginia Vassilevska Williams Yinzhan Xu
+ PDF Ask
Factorization and pseudofactorization of weighted graphs 2023-05-08 Kristin Sheridan Joseph Berleant Mark Bathe Anne Condon Virginia Vassilevska Williams
+ PDF Ask
Isometric Hamming embeddings of weighted graphs 2023-02-17 Joseph Berleant Kristin Sheridan Anne Condon Virginia Vassilevska Williams Mark Bathe
+ PDF Ask
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More 2023-01-01 Timothy M. Chan Virginia Vassilevska Williams Yinzhan Xu
+ PDF Ask
Quasipolynomiality of the Smallest Missing Induced Subgraph 2023-01-01 David Eppstein Andrea Lincoln Virginia Vassilevska Williams
+ PDF Ask
Faster Detours in Undirected Graphs 2023-01-01 Shyan Akmal Virginia Vassilevska Williams Ryan Williams Zixuan Xu
+ PDF Ask
New Bounds for Matrix Multiplication: from Alpha to Omega 2023-01-01 Virginia Vassilevska Williams Yinzhan Xu Zixuan Xu Renfei Zhou
+ PDF Ask
Fast 2-Approximate All-Pairs Shortest Paths 2023-01-01 Michal Dory Sebastian Förster Yael Kirkpatrick Yasamin Nazari Virginia Vassilevska Williams Tijn de Vos
+ PDF Ask
Listing Cliques from Smaller Cliques 2023-01-01 Mina Dalirrooyfard Surya Mathialagan Virginia Vassilevska Williams Yinzhan Xu
+ PDF Ask
Approximating Min-Diameter: Standard and Bichromatic 2023-01-01 Aaron J. Berger Jenny Kaufmann Virginia Vassilevska Williams
+ PDF Ask
Simpler and Higher Lower Bounds for Shortcut Sets 2023-01-01 Virginia Vassilevska Williams Yinzhan Xu Zixuan Xu
+ PDF Ask
Faster Algorithms for Text-to-Pattern Hamming Distances 2023-01-01 Timothy M. Chan Ce Jin Virginia Vassilevska Williams Yinzhan Xu
+ PDF Ask
Listing 6-Cycles 2023-01-01 Ce Jin Virginia Vassilevska Williams Renfei Zhou
+ PDF Ask
Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation 2023-01-01 Alina Harbuzova Ce Jin Virginia Vassilevska Williams Zixuan Xu
+ PDF Ask
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles 2022-10-01 Mina Dalirrooyfard Ce Jin Virginia Vassilevska Williams Nicole Wein
+ PDF Ask
Induced Cycles and Paths Are Harder Than You Think 2022-10-01 Mina Dalirrooyfard Virginia Vassilevska Williams
+ PDF Ask
Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules 2022-07-01 Krzysztof Sornat Virginia Vassilevska Williams Yinzhan Xu
+ PDF Ask
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV 2022-06-09 Timothy M. Chan Virginia Vassilevska Williams Yinzhan Xu
+ PDF Ask
Hardness of Approximate Diameter: Now for Undirected Graphs 2022-02-01 Mina Dalirrooyfard Ray Li Virginia Vassilevska Williams
+ PDF Ask
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product 2022-01-01 Kevin W. Lu Virginia Vassilevska Williams Nicole Wein Zixuan Xu
+ PDF Ask
Approximation Algorithms and Hardness for $n$-Pairs Shortest Paths and All-Nodes Shortest Cycles 2022-01-01 Mina Dalirooyfard Ce Jin Virginia Vassilevska Williams Nicole Wein
+ PDF Ask
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds 2022-01-01 Surya Mathialagan Virginia Vassilevska Williams Yinzhan Xu
+ PDF Ask
Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV 2022-01-01 Timothy M. Chan Virginia Vassilevska Williams Yinzhan Xu
+ PDF Ask
Induced Cycles and Paths Are Harder Than You Think 2022-01-01 Mina Dalirrooyfard Virginia Vassilevska Williams
+ PDF Ask
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures 2022-01-01 Virginia Vassilevska Williams Eyob Woldeghebriel Yinzhan Xu
+ PDF Ask
Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules 2022-01-01 Krzysztof Sornat Virginia Vassilevska Williams Yinzhan Xu
+ PDF Ask
Factorization and pseudofactorization of weighted graphs 2021-12-13 Kristin Sheridan Joseph Berleant Mark Bathe Anne Condon Virginia Vassilevska Williams
+ PDF Ask
Isometric Hamming embeddings of weighted graphs 2021-12-13 Joseph Berleant Kristin Sheridan Anne Condon Virginia Vassilevska Williams Mark Bathe
+ PDF Ask
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication 2021-11-22 Josh Alman Virginia Vassilevska Williams
+ PDF Ask
Better Distance Preservers and Additive Spanners 2021-10-05 Greg Bodwin Virginia Vassilevska Williams

Common Coauthors

Coauthor Papers Together
Yinzhan Xu 34
Mina Dalirrooyfard 23
Nicole Wein 21
Andrea Lincoln 18
Amir Abboud 14
Josh Alman 14
Zixuan Xu 12
Artūrs Bačkurs 11
Liam Roditty 11
Greg Bodwin 10
Ryan Williams 8
Ce Jin 7
Barna Saha 7
Timothy M. Chan 7
Monika Henzinger 7
Fabrizio Grandoni 6
Joseph Berleant 6
Kristin Sheridan 6
Thomas Dueholm Hansen 6
Renfei Zhou 6
Adam Polak 6
Maximilian Probst Gutenberg 6
Erik D. Demaine 6
Anne Condon 6
Mark Bathe 6
Keren Censor-Hillel 5
Matthias Mnich 5
Thuy Duong Vuong 4
Yuancheng Yu 4
Bertie Ancona 4
Karl Bringmann 4
Merav Parter 4
Shyan Akmal 4
Jayson Lynch 4
Krzysztof Sornat 3
Aaron Sidford 3
Yuzhou Gu 3
Ray Li 3
Christopher Ye 3
Stefan Neumann 3
Roei Tov 3
Surya Mathialagan 3
Nikhil Vyas 3
Gilad Segal 3
Or Zamir 3
Jakub Pachocki 3
Joshua R. Wang 3
Yuval Efron 3
Oswin Aichholzer 2
Alina Harbuzova 2

Commonly Cited References

Action Title Date Authors # of times referenced
+ PDF Ask
Multiplying matrices faster than coppersmith-winograd 2012-05-19 Virginia Vassilevska Williams 36
+ PDF Ask
Powers of tensors and fast matrix multiplication 2014-07-01 François Le Gall 29
+ PDF Ask
All pairs shortest paths using bridging sets and rectangular matrix multiplication 2002-05-01 Uri Zwick 20
+ PDF Ask
Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor 2018-01-01 François Le Gall Florent Urrutia 20
+ PDF Ask
Faster all-pairs shortest paths via circuit complexity 2014-05-31 Ryan Williams 20
+ PDF Ask
Finding and counting given length cycles 1997-03-01 Noga Alon Raphael Yuster Uri Zwick 17
+ PDF Ask
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems 2014-10-01 Amir Abboud Virginia Vassilevska Williams 15
+
Matrix multiplication via arithmetic progressions 1990-03-01 Don Coppersmith S. Winograd 14
+ PDF Ask
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs 2018-01-01 Andrea Lincoln Virginia Vassilevska Williams Ryan Williams 12
+ PDF Ask
Algebraic complexity theory and matrix multiplication 2014-07-01 François Le Gall 10
+ PDF Ask
A Refined Laser Method and Faster Matrix Multiplication 2021-01-01 Josh Alman Virginia Vassilevska Williams 10
+ PDF Ask
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture 2015-06-03 Monika Henzinger Sebastian Krinninger Danupon Nanongkai Thatchaphol Saranurak 8
+
New bounds for approximating extremal distances in undirected graphs 2016-01-10 Massimo Cairo Roberto Grossi Roméo Rizzi 7
+ PDF Ask
Faster Algorithms for Rectangular Matrix Multiplication 2012-10-01 François Le Gall 7
+ PDF Ask
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) 2015-06-03 Artūrs Bačkurs Piotr Indyk 7
+ PDF Ask
Faster All-Pairs Shortest Paths via Circuit Complexity 2018-01-01 Ryan Williams 7
+ PDF Ask
Additive Spanners: A Simple Construction 2014-01-01 Mathias Bæk Tejs Knudsen 7
+ PDF Ask
Towards tight approximation bounds for graph diameter and eccentricities 2018-06-20 Artūrs Bačkurs Liam Roditty Gilad Segal Virginia Vassilevska Williams Nicole Wein 6
+ PDF Ask
Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization 2016-01-01 Monika Henzinger Sebastian Krinninger Danupon Nanongkai 6
+ PDF Ask
Graph pattern detection: hardness for all induced patterns and faster non-induced cycles 2019-06-20 Mina Dalirrooyfard Thuy Duong Vuong Virginia Vassilevska Williams 6
+ PDF Ask
Higher Lower Bounds from the 3SUM Conjecture 2015-12-21 Tsvi Kopelowitz Seth Pettie Ely Porat 6
+ PDF Ask
More consequences of falsifying SETH and the orthogonal vectors conjecture 2018-06-20 Amir Abboud Karl Bringmann Holger Dell Jesper Nederlof 6
+ PDF Ask
Very Sparse Additive Spanners and Emulators 2015-01-11 Gregory Bodwin Virginia Vassilevska Williams 5
+ PDF Ask
Finding heaviest <i>H</i> -subgraphs in real weighted graphs, with applications 2010-06-01 Virginia Vassilevska Ryan Williams Raphael Yuster 5
+
Cycles of even length in graphs 1974-04-01 J. A. Bondy Miklós Simonovits 5
+ PDF Ask
A group-theoretic approach to fast matrix multiplication 2004-03-01 Henry Cohn Chris Umans 5
+ PDF Ask
If the Current Clique Algorithms are Optimal, So is Valiant's Parser 2015-10-01 Amir Abboud Artūrs Bačkurs Virginia Vassilevska Williams 5
+ PDF Ask
Losing Weight by Gaining Edges 2014-01-01 Amir Abboud Kevin Lewi Ryan Williams 5
+ PDF Ask
Fast context-free grammar parsing requires fast boolean matrix multiplication 2002-01-01 Lillian Lee 5
+ PDF Ask
Clustered Integer 3SUM via Additive Combinatorics 2015-06-03 Timothy M. Chan Moshe Lewenstein 5
+ PDF Ask
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser 2018-01-01 Amir Abboud Artūrs Bačkurs Virginia Vassilevska Williams 5
+ PDF Ask
Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails 2014-10-01 Karl Bringmann 5
+ PDF Ask
An Improved Combinatorial Algorithm for Boolean Matrix Multiplication 2015-01-01 Huacheng Yu 5
+ PDF Ask
Efficient algorithms for clique problems 2008-11-08 Virginia Vassilevska 5
+ PDF Ask
On Problems Equivalent to (min,+)-Convolution 2019-01-08 Marek Cygan Marcin Mucha Karol Węgrzycki Michał Włodarczyk 4
+ PDF Ask
The 4/3 Additive Spanner Exponent Is Tight 2017-08-31 Amir Abboud Greg Bodwin 4
+ PDF Ask
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping 2015-10-01 Karl Bringmann Marvin Künnemann 4
+ PDF Ask
Homomorphisms are a good basis for counting small subgraphs 2017-06-15 Radu Curticapean Holger Dell Dániel Marx 4
+ PDF Ask
Equivalences between triangle and range query problems 2019-12-23 Lech Duraj Krzysztof Kleiner Adam Polak Virginia Vassilevska Williams 4
+
Counting and Detecting Small Subgraphs via Equations 2013-01-01 Mirosław Kowaluk Andrzej Lingas Eva-Marta Lundell 4
+ PDF Ask
Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max 2019-06-20 Karl Bringmann Marvin Künnemann Karol Węgrzycki 4
+ PDF Ask
Threesomes, Degenerates, and Love Triangles 2018-04-24 Allan Grønlund Seth Pettie 4
+ PDF Ask
On Problems as Hard as CNF-SAT 2016-05-24 Marek Cygan Holger Dell Daniel Lokshtanov Dániel Marx Jesper Nederlof Yoshio Okamoto Ramamohan Paturi Saket Saurabh Magnus Wahlström 4
+ PDF Ask
Decremental strongly-connected components and single-source reachability in near-linear time 2019-06-20 Aaron Bernstein Maximilian Probst Gutenberg Christian Wulff‐Nilsen 4
+
A Linear Recognition Algorithm for Cographs 1985-11-01 Derek G. Corneil Yehoshua Perl Laura K. Stewart 4
+ PDF Ask
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping 2015-02-03 Karl Bringmann Marvin Künnemann 4
+ PDF Ask
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions. 2020-01-01 Andrea Lincoln Adam Polak Virginia Vassilevska Williams 4
+ PDF Ask
Which groups are amenable to proving exponent two for matrix multiplication? 2017-01-01 Jonah Blasiak Thomas M. Church Henry Cohn Joshua A. Grochow Chris Umans 3
+
The chromatic number of random graphs 1988-03-01 B Bollobás 3
+
Über eine Eigenschaft der ebenen Komplexe 1937-12-01 Klaus W. Wagner 3