Virginia Vassilevska Williams
- A Refined Laser Method and Faster Matrix Multiplication
2020/10/12 by Josh Alman, Virginia Vassilevska Williams · 1 voice · 8 citations
#cs.DS #cs.CC #math.CO
- More Asymmetry Yields Faster Matrix Multiplication
2024/04/25 by Josh Alman, Ran Duan, Alman, Josh +9 · 30 citations
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Matrix Theory and Algorithms #Parallel Computing and Optimization Techniques
- Popular conjectures imply strong lower bounds for dynamic problems
2014/02/01 by Amir Abboud, Abboud, Amir, Virginia Vassilevska Williams +1 · 8 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
- Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
2019/10/10 by Virginia Vassilevska Williams, Williams, Virginia Vassilevska, Yinzhan Xu +1 · 4 citations
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
- Preserving Distances in Very Faulty Graphs
2017/03/30 by Greg Bodwin, Fabrizio Grandoni, Bodwin, Greg +5 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems
- Quadratic-Time Hardness of LCS and other Sequence Similarity Measures
2015/01/28 by Amir Abboud, Abboud, Amir, Artūrs Bačkurs +3 · 1 citation
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences
- Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
2018/08/26 by Artūrs Bačkurs, Backurs, Arturs, Liam Roditty +7 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Graph Theory and Algorithms
- Fast 2-Approximate All-Pairs Shortest Paths
2023/07/18 by Michal Dory, Sebastian Förster, Dory, Michal +9 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Optimization and Search Problems
- Hardness for Triangle Problems under Even More Believable Hypotheses:\n Reductions from Real APSP, Real 3SUM, and OV
2022/03/15 by Timothy M. Chan, Chan, Timothy M., Virginia Vassilevska Williams +3 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #semigroups and automata theory #Logic, programming, and type systems
- Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
2022/04/06 by Ce Jin, Dalirrooyfard, Mina, Jin, Ce +4 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
- Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
2023/03/25 by Timothy M. Chan, Virginia Vassilevska Williams, Chan, Timothy M. +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory
- Simpler and Higher Lower Bounds for Shortcut Sets
2023/10/18 by Virginia Vassilevska Williams, Yinzhan Xu, Williams, Virginia Vassilevska +3 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Optimization and Search Problems
- Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules
2022/12/29 by Krzysztof Sornat, Sornat, Krzysztof, Virginia Vassilevska Williams +3 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #68Q17 #68T42 (Secondary) #68W05 (Primary) #91B12 #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Game Theory and Voting Systems #I.2.11 #Logic, Reasoning, and Knowledge #Multiagent Systems (cs.MA)