3 problems

The Triangle Detection problem asks whether an $n$-node graph contains a triangle. A strongly subcubic combinatorial algorithm is a combinatorial algorithm whose running time is…

Combinatorial triangle-detection conjecture. There is no $O(n^{3-\eps})$-time combinatorial algorithm for finding a triangle in an undirected graph.

Combinatorial triangle-detection conjecture. There is no $O(n^{3-\eps})$-time combinatorial algorithm for finding a triangle in an undirected graph.