Virginia Vassilevska Williams

activity

20242026

collaborators

6 papers

cs.DS2026

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 $A, B, C$ , determine whether there is a tuple $(a, b, c) \in A \times B \times C$ satisfying $a + b + c = 0$ . The 3SUM…

cs.DS2025

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…

cs.DS2025

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…

cs.DS2025

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 $d$ distinct weights on the outgoing edges from every node. For $d = n$ this…

cs.DS2025

Beyond 2-approximation for k-Center in Graphs

Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams +1

We consider the classical $k$ -Center problem in undirected graphs. The problem is known to have a polynomial-time 2-approximation. There are even $(2 + ε)$ -approximations r…

cs.DS2024

All-Hops Shortest Paths

Virginia Vassilevska Williams, Zoe Xi, Yinzhan Xu +1

Let $G = (V, E, w)$ be a weighted directed graph without negative cycles. For two vertices $s, t \in V$ , we let $d_{\leq h} (s, t)$ be the minimum, according to the weight function $w$ , of…