Virginia Vassilevska Williams

Virginia Vassilevska Williams's AcademicInfluence.com Rankings

Computer Science

#667

World Rank

#688

Historical Rank

Theoretical Computer Science

#19

World Rank

#19

Historical Rank

Database

#7806

World Rank

#8119

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Why Is Virginia Vassilevska Williams Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Virginia Vassilevska Williams is a theoretical computer scientist and mathematician known for her research in computational complexity theory and algorithms. She is currently the Steven and Renee Finn Career Development Associate Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. She is notable for her breakthrough results in fast matrix multiplication, for her work on dynamic algorithms, and for helping to develop the field of fine-grained complexity.

(See a Problem?)

Virginia Vassilevska Williams's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Multiplying matrices faster than coppersmith-winograd (2012) (959)
Subcubic Equivalences between Path, Matrix and Triangle Problems (2010) (368)
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems (2014) (338)
A Refined Laser Method and Faster Matrix Multiplication (2020) (305)
Fast approximation algorithms for the diameter and radius of sparse graphs (2013) (237)
Tight Hardness Results for LCS and Other Sequence Similarity Measures (2015) (205)
Finding, minimizing, and counting weighted subgraphs (2009) (190)
ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY (2019) (167)
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs (2015) (153)
Consequences of Faster Alignment of Sequences (2014) (139)
Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk) (2015) (135)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture (2015) (112)
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made (2015) (110)
Better Approximation Algorithms for the Graph Diameter (2014) (104)
If the Current Clique Algorithms are Optimal, So is Valiant's Parser (2015) (99)
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs (2017) (84)
Listing Triangles (2014) (64)
Finding Four-Node Subgraphs in Triangle Time (2015) (64)
Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths (2012) (57)
Efficient algorithms for clique problems (2009) (56)
Fixing a Tournament (2010) (50)
Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product (2016) (49)
Towards tight approximation bounds for graph diameter and eccentricities (2018) (46)
Better Distance Preservers and Additive Spanners (2015) (45)
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication (2018) (42)
Subtree Isomorphism Revisited (2015) (42)
Finding a maximum weight triangle in n3-Δ time, with applications (2006) (41)
All-pairs bottleneck paths for general graphs in truly sub-cubic time (2007) (40)
Quadratic-Time Hardness of LCS and other Sequence Similarity Measures (2015) (40)
Multiplying matrices in O(n 2:373 ) time (2014) (38)
Confronting hardness using a hybrid approach (2006) (37)
Faster replacement paths (2010) (36)
All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time (2009) (34)
Minimum Weight Cycles and Triangles: Equivalences and Algorithms (2011) (33)
Further Limitations of the Known Approaches for Matrix Multiplication (2017) (33)
Deterministic Time-Space Tradeoffs for k-SUM (2016) (31)
Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems (2006) (30)
Finding heaviest H-subgraphs in real weighted graphs, with applications (2006) (29)
Rigging Tournament Brackets for Weaker Players (2011) (29)
Preserving Distances in Very Faulty Graphs (2017) (28)
Explicit Inapproximability Bounds for the Shortest Superstring Problem (2005) (27)
Who Can Win a Single-Elimination Tournament? (2015) (27)
Optimal Vertex Fault Tolerant Spanners (for fixed stretch) (2017) (26)
Algorithms and Hardness for Diameter in Dynamic Graphs (2018) (23)
A New Combinatorial Approach for Sparse Graph Problems (2008) (23)
Conditional Hardness for Sensitivity Problems (2017) (21)
Fixing Tournaments for Kings, Chokers, and More (2015) (21)
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications (2019) (20)
Dynamic Parameterized Problems and Algorithms (2017) (20)
Graph pattern detection: hardness for all induced patterns and faster non-induced cycles (2019) (20)
New algorithms and hardness for incremental single-source shortest paths in directed graphs (2020) (19)
Manipulating Stochastically Generated Single-Elimination Tournaments for Nearly All Players (2011) (19)
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions (2020) (19)
Faster Replacement Paths and Distance Sensitivity Oracles (2019) (18)
Subquadratic time approximation algorithms for the girth (2012) (18)
Very Sparse Additive Spanners and Emulators (2015) (18)
A 7/3-Approximation for Feedback Vertex Sets in Tournaments (2015) (18)
Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners (2016) (18)
Monochromatic Triangles, Triangle Listing and APSP (2020) (17)
New Techniques for Proving Fine-Grained Average-Case Hardness (2020) (17)
Equivalences between triangle and range query problems (2019) (15)
The structure, efficacy, and manipulation of double-elimination tournaments (2013) (15)
SETH vs Approximation (2019) (15)
Public-Key Cryptography in the Fine-Grained Setting (2019) (13)
Parameterized Complexity of Group Activity Selection (2017) (12)
Nondecreasing paths in a weighted graph or: How to optimally read a train schedule (2010) (11)
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners (2020) (11)
Hardness of Approximate Diameter: Now for Undirected Graphs (2021) (10)
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths (2021) (10)
Metatheorems for Dynamic Weighted Matching (2017) (10)
Uniquely Represented Data Structures for Computational Geometry (2008) (10)
Bribery in Balanced Knockout Tournaments (2019) (9)
Some Open Problems in Fine-Grained Complexity (2018) (8)
Fine-Grained Algorithms and Complexity (Invited Talk) (2016) (8)
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems (2019) (8)
Quantum algorithms for shortest paths problems in structured instances (2014) (7)
Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy (2017) (7)
Distributed Distance Approximation (2020) (7)
Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures (2018) (6)
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product (2021) (6)
Improved Approximation for Longest Common Subsequence over Small Alphabets (2021) (6)
Toward Tight Approximation Bounds for Graph Diameter and Eccentricities (2021) (6)
Structure and Hardness in P (Dagstuhl Seminar 16451) (2016) (6)
Approximation Algorithms for Min-Distance Problems (2019) (6)
Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles (2021) (5)
An overview of the recent progress on matrix multiplication (2012) (5)
Dynamic Matching Algorithms Under Vertex Updates (2022) (5)
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths (2021) (4)
Conditionally optimal approximation algorithms for the girth of a directed graph (2020) (4)
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV (2022) (4)
Approximating the diameter of a graph (2012) (4)
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles (2022) (4)
Hardness of Token Swapping on Trees (2021) (4)
Fine-grained Algorithms and Complexity (2018) (4)
Induced Cycles and Paths Are Harder Than You Think (2022) (4)
Triangle Detection Versus Matrix Multiplication : A Study of Truly Subcubic Reducibility ∗ (2009) (3)
Algorithmic trade-offs for girth approximation in undirected graphs (2022) (3)
Fine-Grained Hardness for Edit Distance to a Fixed Sequence (2021) (3)
OV Graphs Are (Probably) Hard Instances (2020) (3)
Towards Optimal Set-Disjointness and Set-Intersection Data Structures (2020) (2)
3SUM and Related Problems in Fine-Grained Complexity (Invited Talk) (2021) (1)
Isometric Hamming embeddings of weighted graphs (2021) (1)
Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules (2022) (1)
New Additive Approximations for Shortest Paths and Cycles (2022) (1)
Fine-Grained Complexity and Algorithms for the Schulze Voting Method (2021) (1)
Factorization and pseudofactorization of weighted graphs (2021) (1)
J ul 2 01 2 Approximating the diameter of a graph (2018) (0)
D S ] 6 J un 2 02 1 Better Distance Preservers and Additive Spanners (2021) (0)
Introduction to the Special Issue on SODA 2017 (2019) (0)
EATCS-IPEC Nerode Prize - Call for Nominations (2021) (0)
Improved girth approximation in weighted undirected graphs (2023) (0)
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure (2022) (0)
Vertex connectivity in poly-logarithmic max-flows (2021) (0)
EATCS-IPEC Nerode Prize 2019 - Call for Nominations (2019) (0)
Directed Girth (2020) (0)
RNA-Folding - From Hardness to Algorithms (2016) (0)
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds (2022) (0)
New Lower Bounds and Upper Bounds for Listing Avoidable Vertices (2022) (0)
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More (2023) (0)
Special Section on the Fifty-Fourth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013) (2016) (0)

This paper list is powered by the following services:

Other Resources About Virginia Vassilevska Williams

What Schools Are Affiliated With Virginia Vassilevska Williams?

Virginia Vassilevska Williams is affiliated with the following schools:

Virginia Vassilevska Williams's Academic­Influence.com Rankings

Why Is Virginia Vassilevska Williams Influential?

Virginia Vassilevska Williams's Published Works

Published Works

Other Resources About Virginia Vassilevska Williams

What Schools Are Affiliated With Virginia Vassilevska Williams?

Image Attributions

Virginia Vassilevska Williams's AcademicInfluence.com Rankings