3 citations · 3 across the 6 of their papers we have counts for
12 papers
Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time
Jakob Nogler, Agnès Totschnig, Virginia Vassilevska Williams
In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two trends in…
When Shall We Meet Again? Tight Algorithms for Diameter and Radius under the Meet Distance
Yael Kirkpatrick, John Kuszmaul, Merey Temirzinova +1
Finding an optimal meeting point for a collection of agents on a directed graph is a classical problem studied in the context of network analysis, operations research and computati…
The Limits of Black-Box Reductions for All-Pairs Triangle Detection
Nathan Sheffield, Virginia Vassilevska Williams, Zoe Xi
For any tripartite relation , the -Triangle problem asks, given an edge-weighted graph, whether it contains a triangle whose weights form a triple in $R…
The Cost of Changing Edges for Diameter Computation and More
Sam Hiken, Yael Kirkpatrick, Jakob Nogler +1
The sensitivity setting is a restricted setting for dynamic algorithms, particularly practical for scenarios where extensive preprocessing is feasible but responses to real-time mo…
Preprocessed 3SUM for Unknown Universes with Subquadratic Space
Yael Kirkpatrick, John Kuszmaul, Surya Mathialagan +1
We consider the classic 3SUM problem: given sets of integers , determine whether there is a tuple satisfying . The 3SUM…
Improved Additive Approximation Algorithms for APSP
Ce Jin, Yael Kirkpatrick, Michał Stawarz +1
The All-Pairs Shortest Paths (APSP) is a foundational problem in theoretical computer science. Approximating APSP in undirected unweighted graphs has been studied for many years, b…
Shortest Paths in Multimode Graphs
Yael Kirkpatrick, Virginia Vassilevska Williams
In this work we study shortest path problems in multimode graphs, a generalization of the min-distance measure introduced by Abboud, Vassilevska W. and Wang in [SODA'16]. A multimo…
All-Pairs Shortest Paths with Few Weights per Node
Amir Abboud, Nick Fischer, Ce Jin +2
We study the central All-Pairs Shortest Paths (APSP) problem under the restriction that there are at most distinct weights on the outgoing edges from every node. For this…
Beyond 2-approximation for k-Center in Graphs
Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams +1
We consider the classical -Center problem in undirected graphs. The problem is known to have a polynomial-time 2-approximation. There are even -approximations r…
All-Hops Shortest Paths
Virginia Vassilevska Williams, Zoe Xi, Yinzhan Xu +1
Let be a weighted directed graph without negative cycles. For two vertices , we let be the minimum, according to the weight function , of…
Detecting Disjoint Shortest Paths in Linear Time and More
Shyan Akmal, Virginia Vassilevska Williams, Nicole Wein
In the -Disjoint Shortest Paths (-DSP) problem, we are given a weighted graph on nodes and edges with specified source vertices , and target vert…
Additive Spanner Lower Bounds with Optimal Inner Graph Structure
Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams +2
We construct -node graphs on which any -size spanner has additive error at least , improving on the previous best lower bound of [Bodwin-Hoppenw…