Strong Triangle Conjecture

Target Problem

Triangle Detection

Description

Any Algorithm requires $\min(n^{w-o(1)}, m^{2w/(w+1)-o(1)})$ time in expectation to detect whether an $n$ node $m$ edge graph contains a triangle. Moreover, any combinatorial algorithm requires $m^{3/2-o(1)}$

Computation Model

Word-Ram on $\log(n)$ bit words

Proven?

No

Year

2014

References/Citation

A. Abboud and V. V. Williams, "Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems," 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 2014, pp. 434-443, doi: 10.1109/FOCS.2014.53.