---
_id: '61922'
abstract:
- lang: eng
  text: "We present an extremely simple polynomial-space exponential-time\r\n$(1-\\varepsilon)$-approximation
    algorithm for MAX-k-SAT that is (slightly)\r\nfaster than the previous known polynomial-space
    $(1-\\varepsilon)$-approximation\r\nalgorithms by Hirsch (Discrete Applied Mathematics,
    2003) and Escoffier,\r\nPaschos and Tourniaire (Theoretical Computer Science,
    2014). Our algorithm\r\nrepeatedly samples an assignment uniformly at random until
    finding an\r\nassignment that satisfies a large enough fraction of clauses. Surprisingly,
    we\r\ncan show the efficiency of this simpler approach by proving that in any\r\ninstance
    of MAX-k-SAT (or more generally any instance of MAXCSP), an\r\nexponential number
    of assignments satisfy a fraction of clauses close to the\r\noptimal value."
author:
- first_name: Harry
  full_name: Buhrman, Harry
  last_name: Buhrman
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Zeph
  full_name: Landau, Zeph
  last_name: Landau
- first_name: François Le
  full_name: Gall, François Le
  last_name: Gall
- first_name: Norbert
  full_name: Schuch, Norbert
  last_name: Schuch
- first_name: Suguru
  full_name: Tamaki, Suguru
  last_name: Tamaki
citation:
  ama: 'Buhrman H, Gharibian S, Landau Z, Gall FL, Schuch N, Tamaki S. A Simpler Exponential-Time
    Approximation Algorithm for MAX-k-SAT. In: <i>SIAM Symposium on Simplicity in
    Algorithms (SOSA)</i>. ; :247-253.'
  apa: Buhrman, H., Gharibian, S., Landau, Z., Gall, F. L., Schuch, N., &#38; Tamaki,
    S. (n.d.). A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT. <i>SIAM
    Symposium on Simplicity in Algorithms (SOSA)</i>, 247–253.
  bibtex: '@inproceedings{Buhrman_Gharibian_Landau_Gall_Schuch_Tamaki, title={A Simpler
    Exponential-Time Approximation Algorithm for MAX-k-SAT}, booktitle={SIAM Symposium
    on Simplicity in Algorithms (SOSA)}, author={Buhrman, Harry and Gharibian, Sevag
    and Landau, Zeph and Gall, François Le and Schuch, Norbert and Tamaki, Suguru},
    pages={247–253} }'
  chicago: Buhrman, Harry, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert
    Schuch, and Suguru Tamaki. “A Simpler Exponential-Time Approximation Algorithm
    for MAX-k-SAT.” In <i>SIAM Symposium on Simplicity in Algorithms (SOSA)</i>, 247–53,
    n.d.
  ieee: H. Buhrman, S. Gharibian, Z. Landau, F. L. Gall, N. Schuch, and S. Tamaki,
    “A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT,” in <i>SIAM
    Symposium on Simplicity in Algorithms (SOSA)</i>, pp. 247–253.
  mla: Buhrman, Harry, et al. “A Simpler Exponential-Time Approximation Algorithm
    for MAX-k-SAT.” <i>SIAM Symposium on Simplicity in Algorithms (SOSA)</i>, pp.
    247–53.
  short: 'H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, in:
    SIAM Symposium on Simplicity in Algorithms (SOSA), n.d., pp. 247–253.'
date_created: 2025-10-22T09:33:22Z
date_updated: 2026-04-20T13:53:03Z
department:
- _id: '7'
- _id: '623'
external_id:
  arxiv:
  - '2510.18164'
language:
- iso: eng
page: 247-253
publication: SIAM Symposium on Simplicity in Algorithms (SOSA)
publication_status: inpress
status: public
title: A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
type: conference
user_id: '71541'
year: '2026'
...