Finding the largest triangle in a graph in expected quadratic time

Finding the largest triangle in an n-nodes edge-weighted graph belongs to a set of problems all equivalent under subcubic reductions. Namely, a truly subcubic algorithm for any one of them would imply that they are all subcubic. A recent strong conjecture states that none of them can be solved in less than Θ(n3) time, but this negative result does not rule out the possibility of algorithms with average, rather than worst-case, subcubic running time. Indeed, in this work we describe the first truly-subcubic average complexity procedure for this problem for graphs whose edge lengths are uniformly distributed in [0,1]. Our procedure finds the largest triangle in average quadratic time, which is the best possible complexity of any algorithm for this problem. We also give empirical evidence that the quadratic average complexity holds for many other random distributions of the edge lengths. A notable exception is when the lengths are distances between random points in Euclidean space, for which the algorithm takes average cubic time.