Triangle detection in the \(\mathsf {CLIQUE}\)  model. The approach of [1]} inherently lists all triangles. A natural question is whether the decision problem of triangle detection is easier than listing, for which the answer turns out to be affirmative. Censor-Hillel, Kaski, Korhonen, Lenzen, Paz, and Suomela [2]} show how to perform matrix multiplication over a ring in the \(\mathsf {CLIQUE}\)  model within \(O(n^{0.158})\)  rounds. More precisely, the complexity is \(O(n^{1-2/\omega })\)  rounds, where \(\omega \)  is the matrix multiplication exponent, currently known to be bounded by \(2.3728596\)  due to Alman and Vassilevska-Williams [3]}. Ring matrix multiplication directly carries over to triangle detection with the same complexity.
The main approach of [2]} is to simulate matrix multiplication algorithms for parallel settings in the \(\mathsf {CLIQUE}\)  model. This includes the so-called parallel 3D matrix multiplication, as well as bilinear Strassen-like algorithms.
