# Is MAX-SAT SETH (like) hard?

If we make a random assignment to the variables in $k$-sat ($m$ clauses), we are going to satisfy $(1-2^{-k})m$ clauses in expectation. In general satisfying fewer clauses is considered easy.

There are newer algorithms for 3-sat that satisfy $(1-1/8+\epsilon)m$ clauses in $O(2^{8\epsilon m})$ time. I'm wondering if it's believed that this sort of result is tight in spirit of SETH?

In other words, does it seem reasonable to believe, say, that for any $\delta>0$ there exists $k$ so satisfying $(1-2^{-k}+\epsilon)m$ clauses in $k$-sat takes $\Omega((2-\delta)^{2^k\epsilon m})$ time?

• You quantified over $\delta$ but didn't make any further reference to it. $\;$
– user6973
Mar 4, 2015 at 2:23
• Probably he means: for every $\delta > 0$ there is a k such that max k sat $(1-1/2^k + \varepsilon)$-approximation needs at least $(2-\delta)^{2^k \varepsilon m}$ time. (Don't think this is true...) Mar 4, 2015 at 4:16
• Sorry about that. Ryan is of course correct. Mar 4, 2015 at 13:04