Strong Triangle Conjecture
Revision as of 10:30, 15 February 2023 by Admin (talk | contribs) (Created page with "== 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)}$ == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No == Year == 2014 == Referenc...")
Target Problem
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)}$
Implies the following Hypothesis
Implied by the following Hypothesis
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.