Improved exact algorithms for mildly sparse instances of Max SAT

The previous algorithms and our deterministic polynomial space algorithm run super-polynomially faster than 2n only if m=O(n2). Our second results are deterministic exponential space algorithms for Max SAT with μ(c)=1O((clog⁡c)2/3) and for Max 3-SAT with μ(c)=1O(c1/2) that run super-polynomially faster than 2n when m=o(n5/2/log5/2⁡n) and m=o(n3/log2⁡n) respectively. Our third result is a randomized exponential space algorithm for Max SAT with μ(c)=1O(c1/2log3/2⁡c) that run super-polynomially faster than 2n when m=o(n3/log5⁡n).