@inproceedings{61922,
  abstract     = {{We present an extremely simple polynomial-space exponential-time
$(1-\varepsilon)$-approximation algorithm for MAX-k-SAT that is (slightly)
faster than the previous known polynomial-space $(1-\varepsilon)$-approximation
algorithms by Hirsch (Discrete Applied Mathematics, 2003) and Escoffier,
Paschos and Tourniaire (Theoretical Computer Science, 2014). Our algorithm
repeatedly samples an assignment uniformly at random until finding an
assignment that satisfies a large enough fraction of clauses. Surprisingly, we
can show the efficiency of this simpler approach by proving that in any
instance of MAX-k-SAT (or more generally any instance of MAXCSP), an
exponential number of assignments satisfy a fraction of clauses close to the
optimal value.}},
  author       = {{Buhrman, Harry and Gharibian, Sevag and Landau, Zeph and Gall, François Le and Schuch, Norbert and Tamaki, Suguru}},
  booktitle    = {{SIAM Symposium on Simplicity in Algorithms (SOSA)}},
  pages        = {{247--253}},
  title        = {{{A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT}}},
  year         = {{2026}},
}