Zoe Xi

activity

20242026

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2026

The Limits of Black-Box Reductions for All-Pairs Triangle Detection

Nathan Sheffield, Virginia Vassilevska Williams, Zoe Xi

For any tripartite relation $R \subseteq Z^{3}$ , the $R$ -Triangle problem asks, given an edge-weighted graph, whether it contains a triangle whose weights form a triple in $R…

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.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…