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


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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – Turbo
    Nov 5, 2015 at 17:29
  • 5
    $\begingroup$ 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. $\endgroup$
    – Thomas
    Nov 5, 2015 at 17:43
  • 2
    $\begingroup$ What makes you conjecture this relationship? $\endgroup$ Nov 5, 2015 at 19:08
  • 4
    $\begingroup$ 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 $\endgroup$ Nov 5, 2015 at 19:16
  • 2
    $\begingroup$ @Arul The connection is implicit due to spectral graph theory, as one can find 3-cliques by cubing the adjacency matrix. $\endgroup$
    – Joe Bebel
    Nov 26, 2015 at 3:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.