49 citations · 193 across the 39 of their papers we have counts for
5 papers · 1 filter
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
Virginia Vassilevska Williams, Yinzhan Xu
The goal of this paper is to get truly subcubic algorithms for Min-Plus product for less structured inputs than what was previously known, and to apply them to versions of All-Pair…
Equivalences between triangle and range query problems
Lech Duraj, Krzysztof Kleiner, Adam Polak +1
We define a natural class of range query problems, and prove that all problems within this class have the same time complexity (up to polylogarithmic factors). The equivalence is v…
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas +1
Some of the most fundamental and well-studied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a "center" node ca…
Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles
Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams
We consider the pattern detection problem in graphs: given a constant size pattern graph and a host graph , determine whether contains a subgraph isomorphic to . Our…
Approximation Algorithms for Min-Distance Problems
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas +3
We study fundamental graph parameters such as the Diameter and Radius in directed graphs, when distances are measured using a somewhat unorthodox but natural measure: the distance…