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

Preprint · Nathan Sheffield, Virginia Vassilevska Williams, Zoe Xi

- Archive id: arxiv:2608.19092
- Published: 2026-08-19
- arXiv: https://arxiv.org/abs/2608.19092
- Source URL: https://arxiv.org/abs/2608.19092
- PDF: https://arxiv.org/pdf/2608.19092
- Provenance: arxiv

## Abstract

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$. The All-Edge $R$-Triangle problem asks to determine for every edge whether it is contained in such a triangle. It is known that $R$-Triangle and All-Edge $R$-Triangle are subcubically fine-grained equivalent for every $R$ \[Vassilevska W.-Williams'10\]. However, while it is conjectured that these problems are tightly equivalent, this reduction only shows that if $R$-Triangle has an $O(n^{3-ε})$-time algorithm for some $ε\>0$, then All-Edge $R$-Triangle has an $O(n^{3-ε/3})$-time algorithm. This paper provides a strong unconditional barrier to a tight equivalence: the reduction of \[Vassilevska W.-Williams'10\] is optimal for black-box reductions that work for arbitrary $R$. We give further results about black-box reductions between a variety of $R$-triangle problems. Our positive results yield new reductions between several classes of triangle and matrix problems --- for instance, we demonstrate that an $O(n^{2.53})$-time algorithm for computing equality or dominance product would imply an improvement on known algorithms for computing boolean $(\\min, +)$-product, giving the first conditional lower bound for dominance and equality product. Our negative results can be thought of as barriers against natural fine-grained proof techniques. Besides the result that a tighter equivalence between $R$-Triangle and All-Edge $R$-Triangle is not possible, we also show that no appropriately "black-box" reductions are capable of demonstrating a subcubic equivalence between triangle counting and binary integer matrix multiplication, or a tight equivalence between boolean matrix multiplication and listing $n^2$ triangles, and more, despite the fact that all of these equivalences are conjectured to hold.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.