We next go back to the 4-Cycle problem.
A direct corollary of our theorem is that the All-Edge version has a super-linear lower bound, finally extending the \(m^{3/2}\)  lower bound for triangle enumeration from Pătraşcu's seminal paper [1]} to a hardness result for 4-cycle enumeration.Pătraşcu's lower bound is presented as a lower bound for the listing problem, rather than enumeration, where we are required to list \(m\)  triangles (and the lower bound is \(m^{4/3-o(1)}\) ). Our lower bound also extends to this version, but the exponent is smaller.
If \(\omega =2\)  the lower bound is \(m^{5/4-o(1)}\) , and with the current \(\omega \)  it is \(\Omega (m^{1.1927})\) .
