7 papers
EgoCITE: Context-Augmented Indexing and Time-Aware Retrieval for Long-Horizon Egocentric Memory
Le Zhang, Hao Chen, Ke Sun +2
Long-horizon egocentric memory transforms continuous first-person video and audio into a searchable record of past experiences. We demonstrate two bottlenecks in existing systems:…
Improved Approximation of Min-Distances in Near-Linear Time
Yael Kirkpatrick
We study the problem of approximating the diameter of directed graphs under the min-distance measure, defined as . Unlike standard shortest-pa…
New Diameter Approximations via Distance Oracle Techniques
Yael Kirkpatrick, Liam Roditty, Richard Qi +1
Computing the diameter of a graph is a problem of great interest both in general algorithms research and specifically within fine-grained complexity, where it is a cornerstone hard…
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…