14
$\begingroup$

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?

$\endgroup$
  • 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 '15 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 '15 at 17:43
  • 2
    $\begingroup$ What makes you conjecture this relationship? $\endgroup$ – Huck Bennett Nov 5 '15 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$ – Thatchaphol Nov 5 '15 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 '15 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.