4 papers
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…
Graphs With the Same Edge Count in Each Neighborhood
Nathan S. Sheffield, Zoe Xi
In a recent paper, Caro, Lauri, Mifsud, Yuster, and Zarb ask which parameters and admit the existence of an -regular graph such that the neighborhood of each vertex indu…
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…
All-Hops Shortest Paths
Virginia Vassilevska Williams, Zoe Xi, Yinzhan Xu +1
Let be a weighted directed graph without negative cycles. For two vertices , we let be the minimum, according to the weight function , of…