Virginia Vassilevska Williams

According to our database1, Virginia Vassilevska Williams authored at least 86 papers between 2005 and 2020.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Faster Replacement Paths and Distance Sensitivity Oracles.
ACM Trans. Algorithms, 2020

New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs.
CoRR, 2020

Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Equivalences between triangle and range query problems.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Monochromatic Triangles, Intermediate Matrix Products, and Convolutions.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

OV Graphs Are (Probably) Hard Instances.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019
Introduction to the Special Issue on SODA 2017.
ACM Trans. Algorithms, 2019

SETH vs Approximation.
SIGACT News, 2019

Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.
SIAM J. Comput., 2019

Public-Key Cryptography in the Fine-Grained Setting.
IACR Cryptology ePrint Archive, 2019

EATCS-IPEC Nerode Prize 2019 - Call for Nominations.
Bulletin of the EATCS, 2019

Graph pattern detection: hardness for all induced patterns and faster non-induced cycles.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication.
Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, 2019

Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Approximation Algorithms for Min-Distance Problems.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Algorithms and Hardness for Diameter in Dynamic Graphs.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Bribery in Balanced Knockout Tournaments.
Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019

2018
Subtree Isomorphism Revisited.
ACM Trans. Algorithms, 2018

Some Open Problems in Fine-Grained Complexity.
SIGACT News, 2018

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture.
SIAM J. Comput., 2018

If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser.
SIAM J. Comput., 2018

Subcubic Equivalences Between Path, Matrix, and Triangle Problems.
J. ACM, 2018

Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures.
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Towards tight approximation bounds for graph diameter and eccentricities.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Tight Hardness for Shortest Cycles and Paths in Sparse Graphs.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Optimal Vertex Fault Tolerant Spanners (for fixed stretch).
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Further Limitations of the Known Approaches for Matrix Multiplication.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Fine-grained Algorithms and Complexity.
Proceedings of the 21st International Conference on Database Theory, 2018

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
Who Can Win a Single-Elimination Tournament?
SIAM J. Discrete Math., 2017

Metatheorems for Dynamic Weighted Matching.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Conditional Hardness for Sensitivity Problems.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Preserving Distances in Very Faulty Graphs.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Dynamic Parameterized Problems and Algorithms.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Parameterized Complexity of Group Activity Selection.
Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, 2017

Complexity of the Stable Invitations Problem.
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016
Knockout Tournaments.
Proceedings of the Handbook of Computational Social Choice, 2016

Special Section on the Fifty-Fourth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013).
SIAM J. Comput., 2016

Structure and Hardness in P (Dagstuhl Seminar 16451).
Dagstuhl Reports, 2016

Deterministic Time-Space Tradeoffs for k-SUM.
CoRR, 2016

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Fine-Grained Algorithms and Complexity (Invited Talk).
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Better Distance Preservers and Additive Spanners.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

RNA-Folding - From Hardness to Algorithms.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Deterministic Time-Space Trade-Offs for k-SUM.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

A 7/3-Approximation for Feedback Vertex Sets in Tournaments.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter.
CoRR, 2015

Quadratic-Time Hardness of LCS and other Sequence Similarity Measures.
CoRR, 2015

Finding Four-Node Subgraphs in Triangle Time.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk).
Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

Very Sparse Additive Spanners and Emulators.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Fixing Tournaments for Kings, Chokers, and More.
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Tight Hardness Results for LCS and Other Sequence Similarity Measures.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Quantum algorithms for shortest paths problems in structured instances.
CoRR, 2014

Better Approximation Algorithms for the Graph Diameter.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Listing Triangles.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Consequences of Faster Alignment of Sequences.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Finding, Minimizing, and Counting Weighted Subgraphs.
SIAM J. Comput., 2013

Fast approximation algorithms for the diameter and radius of sparse graphs.
Proceedings of the Symposium on Theory of Computing Conference, 2013

2012
Approximating the diameter of a graph
CoRR, 2012

Multiplying matrices faster than coppersmith-winograd.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Subquadratic time approximation algorithms for the girth.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Manipulating Stochastically Generated Single-Elimination Tournaments for Nearly All Players.
Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

Faster Replacement Paths.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Rigging Tournament Brackets for Weaker Players.
Proceedings of the IJCAI 2011, 2011

Minimum Weight Cycles and Triangles: Equivalences and Algorithms.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
Nondecreasing paths in a weighted graph or: How to optimally read a train schedule.
ACM Trans. Algorithms, 2010

Finding heaviest H-subgraphs in real weighted graphs, with applications.
ACM Trans. Algorithms, 2010

Fixing a Tournament.
Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010

2009
All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time.
Theory of Computing, 2009

Efficient algorithms for clique problems.
Inf. Process. Lett., 2009

2008
Uniquely Represented Data Structures for Computational Geometry.
Proceedings of the Algorithm Theory, 2008

A New Combinatorial Approach for Sparse Graph Problems.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007
All-pairs bottleneck paths for general graphs in truly sub-cubic time.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006
Finding heaviest H-subgraphs in real weighted graphs, with applications
CoRR, 2006

Finding a maximum weight triangle in n3-Delta time, with applications.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Confronting hardness using a hybrid approach.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005
Explicit Inapproximability Bounds for the Shortest Superstring Problem.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005


  Loading...