# Strong Triangle Conjecture

Jump to navigation
Jump to search

## 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.