Boolean Matrix Multiplication conjecture for combinatorial triangle detection

The Triangle Detection problem asks whether an nn-node graph contains a triangle. A strongly subcubic combinatorial algorithm is a combinatorial algorithm whose running time is O(n3ε)O(n^{3-\varepsilon}) for some constant ε>0\varepsilon>0. Boolean Matrix Multiplication conjecture. There is no strongly subcubic combinatorial Triangle Detection algorithm, equivalently no such algorithm for Boolean Matrix Multiplication, in general nn-node graphs. This conjecture is a central fine-grained hardness assumption: the best known combinatorial methods for triangle detection are only mildly subcubic, and a strongly subcubic combinatorial algorithm would refute the conjecture. The parser marks this conjecture as disproved, based on the stated reduction relating the general-graph barrier to the BMM conjecture.

Sources & referencesView supporting material

Primary source

Amir Abboud, Ron Safier and Nathan Wallheimer, “Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs”, arXiv:2602.23196 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.