<p>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.</p>

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

<p><strong>Questions:</strong></p>

<p>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?</p>

CC BY-SA 3.0
2015-11-05T17:29:38.207Z
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.
Turbo
CC BY-SA 3.0
2015-11-05T17:34:36.470Z
@Turbo Could you please provide a reference to the circuit complexity of MM?  Thank you.  :)
Michael Wehar
CC BY-SA 3.0
2015-11-05T17:43:01.853Z
@MichaelWehar I think Turbo means this paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.1090&rep=rep1&type=pdf
Thatchaphol
CC BY-SA 3.0
2015-11-05T17:43:55.033Z
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 Steinke
CC BY-SA 3.0
2015-11-05T18:47:59.920Z
@Thatchaphol Thank you!  I misunderstood.  I will adjust the question to account for the lower bound.  :)
Michael Wehar
CC BY-SA 3.0
2015-11-05T19:08:52.780Z
What makes you conjecture this relationship?
Huck Bennett
CC BY-SA 3.0
2015-11-05T19:09:03.113Z
@Thomas That's a decent point.  :)
Michael Wehar
CC BY-SA 3.0
2015-11-05T19:16:33.993Z
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 http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf
Thatchaphol
CC BY-SA 3.0
2015-11-24T01:34:05.947Z
@HuckBennett Well I work on the intersection non-emptiness problem for finite automata.  Recently, I've been working on this intersection problem for what I'm referring to as tree shaped DFA's.  The problem is as follows.  Given a list of $k$-many tree shaped DFA's, does there exist a binary string that is accepted by all $k$ of the DFA's?  It turns out that this problem is efficiently reducible to $k$-clique.  Also, if you can beat quadratic time for the case when $k=2$, then SETH is false.  And, if you can solve the general case in $n^{o(k)}$ time, then ETH is false.
Michael Wehar
CC BY-SA 3.0
2015-11-24T01:37:37.863Z
@HuckBennett But, the case when $k=3$ is strange.  We can solve it in matrix multiplication time, but it's not known if we can do better.  And, if we can solve it in subquadratic time, then SETH is false as we know from the case when $k=2$.  It seems like we should be able to show that if we can solve the $k=3$ case in quadratic time, then we also break SETH.
Michael Wehar
CC BY-SA 3.0
2015-11-24T01:38:06.030Z
@HuckBennett I'm more than willing to share a draft of the paper to anyone that might be interested.
Michael Wehar
CC BY-SA 3.0
2015-11-25T07:10:18.333Z
I'd be very interested in reading that. I can't promise that I'd be a useful feedbacker, but certainly the premise is supremely intriguing.
Joe Bebel
CC BY-SA 3.0
2015-11-25T17:32:00.320Z
@JoeBebel Cool!  Here is a link: http://www.acsu.buffalo.edu/~mwehar/documents/TreeShaped.pdf
Michael Wehar
CC BY-SA 3.0
2015-11-25T17:32:50.763Z
@JoeBebel Any feedback is appreciated.  I've already gotten some positive, negative, and constructive comments.  :)
Michael Wehar
CC BY-SA 3.0
2015-11-25T19:49:37.860Z
@MichaelWehar: Thanks for the link! Maybe that would be worth adding as an addendum to your post?
Huck Bennett
CC BY-SA 3.0
2015-11-26T03:31:58.853Z
@Arul The connection is implicit due to spectral graph theory, as one can find 3-cliques by cubing the adjacency matrix.
Joe Bebel
CC BY-SA 3.0
2015-11-26T05:37:22.440Z
Cool!  I'm glad that you were interested in taking a look.  :)
Michael Wehar
CC BY-SA 3.0
2015-11-26T05:39:58.407Z
@Arul I don't mention MM in the write-up.  I considered mentioning it, but ultimately decided to discuss the conjecture here first.  Instead, I mentioned k-clique in the write-up.  It is well known that we can reduce 3-clique to MM.  Here is a classic paper that discusses the reduction - "On the complexity of the subgraph problem" - https://eudml.org/doc/17394
Michael Wehar
CC BY-SA 3.0
2015-12-08T16:20:54.253Z
fyi here is recent work on lower bounds on matrix multiplication connecting it to Erdos sunflowers including conditions for a near $O(n^2)$ bound. [On Sunflowers and Matrix Multiplication](http://users.cms.caltech.edu/~umans/papers/ASU11-final.pdf) / Alon, Shpilka, Umans
vzn
CC BY-SA 3.0
2016-02-15T20:58:38.127Z
@MichaelWehar 'It seems like we should be able to show that if we can solve the k=3k=3 case in quadratic time, then we also break SETH.' Do you have a proof of this?
Turbo
CC BY-SA 3.0
2016-02-16T00:06:34.570Z
@Turbo Which problem are you referring to exactly?  I am unable to show that solving $3$-clique or MM in $O(n^2 \log(n))$ time breaks SETH.
Michael Wehar
CC BY-SA 3.0
2016-02-16T00:06:49.313Z
@Turbo However, I can show that if we can solve the intersection problem for 3 tree shaped automata over alphabet $[3]$ in subcubic time, then we break SETH.
Michael Wehar
CC BY-SA 4.0
2019-11-15T00:45:52.857Z
@MichaelWehar Does solving $K$-SAT faster than $2^n$ at all $K$ imply $SETH$ is false?
Turbo
CC BY-SA 4.0
2019-11-16T10:06:00.290Z
@T.... Hi there!  Thank you very much for the comment.  I actually haven't thought about this in a while.  One version of SETH says the following: there does not exist $\varepsilon > 0$ such that for all $K$, $K$-SAT is solvable in $O(2^{(1 - \varepsilon) n})$ time.  As a result, if we can solve each $K$-SAT problem sufficiently faster than $2^n$ time, then SETH is false.  It might be known that we can solve each $K$-SAT problem faster than $2^n$ time, but I don't think that these known algorithms run fast enough to make SETH false.
Michael Wehar
<np-hardness><sat><matrices><clique><fine-grained>
Does solving matrix multiplication in quadratic time imply that SETH is false?
Michael Wehar
# Does solving matrix multiplication in quadratic time imply that SETH is false?

(Asked by: username_0 on 2015-11-05)

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?

**Tags:** np-hardness, sat, matrices, clique, fine-grained

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 Could you please provide a reference to the circuit complexity of MM?  Thank you.  :)  
> **username_2**: @MichaelWehar I think username_1 means this paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.1090&rep=rep1&type=pdf  
> **username_3**: 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.  
> **username_0**: @username_2 Thank you!  I misunderstood.  I will adjust the question to account for the lower bound.  :)  
> **username_4**: What makes you conjecture this relationship?  
> **username_0**: @Thomas That's a decent point.  :)  
> **username_2**: 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 http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf  
> **username_0**: @HuckBennett Well I work on the intersection non-emptiness problem for finite automata.  Recently, I've been working on this intersection problem for what I'm referring to as tree shaped DFA's.  The problem is as follows.  Given a list of $k$-many tree shaped DFA's, does there exist a binary string that is accepted by all $k$ of the DFA's?  It turns out that this problem is efficiently reducible to $k$-clique.  Also, if you can beat quadratic time for the case when $k=2$, then SETH is false.  And, if you can solve the general case in $n^{o(k)}$ time, then ETH is false.  
> **username_0**: @HuckBennett But, the case when $k=3$ is strange.  We can solve it in matrix multiplication time, but it's not known if we can do better.  And, if we can solve it in subquadratic time, then SETH is false as we know from the case when $k=2$.  It seems like we should be able to show that if we can solve the $k=3$ case in quadratic time, then we also break SETH.  
> **username_0**: @HuckBennett I'm more than willing to share a draft of the paper to anyone that might be interested.  
> **username_5**: I'd be very interested in reading that. I can't promise that I'd be a useful feedbacker, but certainly the premise is supremely intriguing.  
> **username_0**: @JoeBebel Cool!  Here is a link: http://www.acsu.buffalo.edu/~mwehar/documents/TreeShaped.pdf  
> **username_0**: @JoeBebel Any feedback is appreciated.  I've already gotten some positive, negative, and constructive comments.  :)  
> **username_4**: @MichaelWehar: Thanks for the link! Maybe that would be worth adding as an addendum to your post?  
> **username_5**: @Arul The connection is implicit due to spectral graph theory, as one can find 3-cliques by cubing the adjacency matrix.  
> **username_0**: Cool!  I'm glad that you were interested in taking a look.  :)  
> **username_0**: @Arul I don't mention MM in the write-up.  I considered mentioning it, but ultimately decided to discuss the conjecture here first.  Instead, I mentioned k-clique in the write-up.  It is well known that we can reduce 3-clique to MM.  Here is a classic paper that discusses the reduction - "On the complexity of the subgraph problem" - https://eudml.org/doc/17394  
> **username_6**: fyi here is recent work on lower bounds on matrix multiplication connecting it to Erdos sunflowers including conditions for a near $O(n^2)$ bound. [On Sunflowers and Matrix Multiplication](http://users.cms.caltech.edu/~umans/papers/ASU11-final.pdf) / Alon, Shpilka, Umans  
> **username_1**: @MichaelWehar 'It seems like we should be able to show that if we can solve the k=3k=3 case in quadratic time, then we also break SETH.' Do you have a proof of this?  
> **username_0**: @username_1 Which problem are you referring to exactly?  I am unable to show that solving $3$-clique or MM in $O(n^2 \log(n))$ time breaks SETH.  
> **username_0**: @username_1 However, I can show that if we can solve the intersection problem for 3 tree shaped automata over alphabet $[3]$ in subcubic time, then we break SETH.  
> **username_1**: @MichaelWehar Does solving $K$-SAT faster than $2^n$ at all $K$ imply $SETH$ is false?  
> **username_0**: @T.... Hi there!  Thank you very much for the comment.  I actually haven't thought about this in a while.  One version of SETH says the following: there does not exist $\varepsilon > 0$ such that for all $K$, $K$-SAT is solvable in $O(2^{(1 - \varepsilon) n})$ time.  As a result, if we can solve each $K$-SAT problem sufficiently faster than $2^n$ time, then SETH is false.  It might be known that we can solve each $K$-SAT problem faster than $2^n$ time, but I don't think that these known algorithms run fast enough to make SETH false.  

---

## 0 answers

