Abstract
We give improved deterministic algorithms solving MAX-SAT on instances with cn clauses, achieving running time 2^{n-\Omega(n/c)} with a polynomial-space algorithm, and running time 2^{n-\Omega(n/\sqrt{c}} with an exponential-space algorithm.