9 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:…
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…