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

Nathan Sheffield, Virginia Vassilevska Williams, Zoe Xi

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