This paper [1] claims that for matrices with entries in $O(1)$, one can approximately multiply them in time $O(n^2 \log 1/\delta)$ to within error delta in the Frobenius norm (Theorem 1 in that paper). This specifically allows us to take square of an adjacency matrix exactly in $O(n^2 \log n)$ by taking polynomially small $\delta$ and using that the entries have to be integers (specifically, set $\delta$ so as to make all entries be within 0.1 of the correct answer, then round).
This would, for example, allow me to count triangles in this time complexity (square adjacency matrix then add all off-diagonal entries at positions where the adjacency list has ones). That seems very suspicious. The paper has been published in ECCC, which suggests it might be correct. The paper only has one citation which for such major result also seems little suspicious.
Does anyone know more about this? Is there a mistake in the paper? Is there a mistake in my reasoning (I don't think there is)? Or does it actually give a significant speedup for triangle counting (unlikely)?
