<p>This paper [1] claims that for matrices with entries in <span class="math-container">$O(1)$</span>, one can approximately multiply them in time <span class="math-container">$O(n^2 \log 1/\delta)$</span> to within error delta in the Frobenius norm (Theorem 1 in that paper). This specifically allows us to take square of an adjacency matrix <em>exactly</em> in <span class="math-container">$O(n^2 \log n)$</span> by taking polynomially small <span class="math-container">$\delta$</span> and using that the entries have to be integers (specifically, set <span class="math-container">$\delta$</span> so as to make all entries be within 0.1 of the correct answer, then round).</p>
<p>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 <em>very</em> 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.</p>
<p>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)?</p>
<p>[1] <a href="https://arxiv.org/abs/1408.4230v2" rel="nofollow noreferrer">https://arxiv.org/abs/1408.4230v2</a></p>

CC BY-SA 4.0
2020-12-06T14:55:45.740Z
ECCC is not a peer-reviewed publication. It is just a paper repository similar to the arXiv.
Emil Jeřábek
CC BY-SA 4.0
2020-12-06T15:38:21.043Z
I was not aware of that. Thank you for pointing out!
user2316602
<ds.algorithms><graph-algorithms><matrix-product>
Triangle counting using approximate matrix multiplication -- suspicious paper
user2316602
# Triangle counting using approximate matrix multiplication -- suspicious paper

(Asked by: username_0 on 2020-12-06)

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)?

[1] <https://arxiv.org/abs/1408.4230v2>

**Tags:** ds.algorithms, graph-algorithms, matrix-product
> **Comments:**
> **username_1**: ECCC is not a peer-reviewed publication. It is just a paper repository similar to the arXiv.  
> **username_0**: I was not aware of that. Thank you for pointing out!  

---

## 0 answers

