# Does solving matrix multiplication in quadratic time imply that SETH is false?

I have a little conjecture that if you could perform matrix multiplication (or solve 3-clique) in $O(n^2 \log(n))$ time, then you could solve CNF-SAT in $O(2^{(1-\epsilon)n})$ time.

In other words, more efficient algorithms for matrix multiplication would imply more efficient algorithms for SAT refuting the strong exponential time hypothesis (SETH).

Questions:

Has anyone ever thought about connecting the hardness of matrix multiplication to SETH? Secondly, does anyone think that there is or isn't a relationship? Why or why not?

• I think it is already known circuit complexity of MM is $\Omega(n^2\log n)$ and so I think these epsilon type conjectures are invalid when it comes to MM problem. – T.... Nov 5 '15 at 17:29
• It would be strange to me if we can refute SETH with a $O(n^2)$-time MM algorithm, but not with $O(n^{2.4})$, which we already have. – Thomas Nov 5 '15 at 17:43
• What makes you conjecture this relationship? – Huck Bennett Nov 5 '15 at 19:08
• Just some related connection between matrix multiplication exponent $\omega$ and SETH. If you have an (unexpected) efficient communication protocol for 3-party disjointness, then you can solve CNF SAT in time $O(2^{(\omega/3+o(1))n})$. See Thm. 4.1 in people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf – Thatchaphol Nov 5 '15 at 19:16
• @Arul The connection is implicit due to spectral graph theory, as one can find 3-cliques by cubing the adjacency matrix. – Joe Bebel Nov 26 '15 at 3:31