49 citations · 193 across the 39 of their papers we have counts for
7 papers · 1 filter
Approximating Min-Diameter: Standard and Bichromatic
Aaron Berger, Jenny Kaufmann, Virginia Vassilevska Williams
The min-diameter of a directed graph is a measure of the largest distance between nodes. It is equal to the maximum min-distance across all pairs ,…
On Diameter Approximation in Directed Graphs
Amir Abboud, Mina Dalirrooyfard, Ray Li +1
Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in fine-grained complexity. In undirected graphs, the Strong Exponential Time…
Faster Detours in Undirected Graphs
Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams +1
The -Detour problem is a basic path-finding problem: given a graph on vertices, with specified nodes and , and a positive integer , the goal is to determine if…
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams +1
We study finding and listing -cliques in a graph, for constant , a fundamental problem of both theoretical and practical importance. Our main contribution is a new outp…
Fast 2-Approximate All-Pairs Shortest Paths
Michal Dory, Sebastian Forster, Yael Kirkpatrick +3
In this paper, we revisit the classic approximate All-Pairs Shortest Paths (APSP) problem in undirected graphs. For unweighted graphs, we provide an algorithm for -approximate A…
New Bounds for Matrix Multiplication: from Alpha to Omega
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu +1
The main contribution of this paper is a new improved variant of the laser method for designing matrix multiplication algorithms. Building upon the recent techniques of [Duan, Wu,…