3 citations · 3 across the 6 of their papers we have counts for
11 papers · 1 filter
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…