Boolean Matrix Multiplication conjecture for combinatorial triangle detection
Boolean Matrix Multiplication conjecture for combinatorial triangle detection
The Triangle Detection problem asks whether an -node graph contains a triangle. A strongly subcubic combinatorial algorithm is a combinatorial algorithm whose running time is for some constant . Boolean Matrix Multiplication conjecture. There is no strongly subcubic combinatorial Triangle Detection algorithm, equivalently no such algorithm for Boolean Matrix Multiplication, in general -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.