A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT

Harry Buhrman; Sevag Gharibian; Zeph Landau; François Le Gall; Norbert Schuch; Suguru Tamaki

doi:10.1137/1.9781611978964.18

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT

Harry Buhrman
, Sevag Gharibian
, Zeph Landau
, François Le Gall
, Norbert Schuch
, Suguru Tamaki

Veröffentlichungen: Beitrag in Buch › Beitrag in Konferenzband › Peer Reviewed

Abstract

We present an extremely simple polynomial-space exponential-time (1 − ε)-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomial-space (1−ε)-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.

Originalsprache	Englisch
Titel	Proceedings - 2026 SIAM Symposium on Simplicity in Algorithms, SOSA 2026
Herausgeber*innen	Sepehr Assadi, Eva Rotenberg
Verlag	Society for Industrial and Applied Mathematics Publications
Seiten	247-253
Seitenumfang	7
ISBN (elektronisch)	978-1-61197-896-4
DOIs	https://doi.org/10.1137/1.9781611978964.18
Publikationsstatus	Veröffentlicht - 2026
Veranstaltung	9th SIAM Symposium on Simplicity in Algorithms, SOSA 2026 - Vancouver, Kanada Dauer: 12 Jan. 2025 → 14 Jan. 2025

Publikationsreihe

Reihe	Symposium on Simplicity in Algorithms Proceedings

Konferenz

Konferenz	9th SIAM Symposium on Simplicity in Algorithms, SOSA 2026
Land/Gebiet	Kanada
Ort	Vancouver
Zeitraum	12/01/25 → 14/01/25

Fördermittel

Part of this work was done when visiting the Simons Institute for the Theory of Computing. SG is supported by DFG grants 563388236 and 450041824, BMFTR project PhoQuant (13N16103), and project PhoQC from the State of Northrhine Westphalia. ZL is supported by the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers, Quantum Systems Accelerator, and by NSF Grant CCF 2311733. FLG is supported by JSPS KAKENHI grants JP20H05966, 24H00071 and MEXT Q-LEAP grant JPMXS0120319794. NS is supported by the Austrian Science Fund FWF (Grant DOIs 10.55776/COE1, 10.55776/P36305 and 10.55776/F71), the European Union – NextGenerationEU, and the European Union’s Horizon 2020 research and innovation programme through Grant No. 863476 (ERC-CoG SEQUAM). ST is supported by JSPS KAKENHI grants JP20H05961, JP20H05967, JP22K11909.

ÖFOS 2012

102031 Theoretische Informatik
101002 Analysis

Zugriff auf Dokument

10.1137/1.9781611978964.18

Andere Dateien und Links

1 Abgeschlossen
3 Laufend

quantA: Quantum Science Austria
Aspelmeyer, M. (Projektleiter*in), Arndt, M. (Co-Projektleiter*in), Brukner, C. (Co-Projektleiter*in), Schuch, N. (Co-Projektleiter*in), Walther, P. (Co-Projektleiter*in) & Nunnenkamp, A. (Co-Projektleiter*in)
1/10/23 → 30/09/28
Projekt: Forschungsförderung
SEQUAM: Symmetries and Entanglement in Quantum Matter
Schuch, N. (Projektleiter*in)
1/10/20 → 30/09/26
Projekt: Forschungsförderung
Beyond C: Quantum Information Systems Beyond Classical Capabilities
Walther, P. (Projektleiter*in), Brukner, C. (Co-Projektleiter*in), Briegel, H.-J. (Co-Projektleiter*in), Kirchmair, G. (Co-Projektleiter*in), Kraus, B. (Co-Projektleiter*in), Lechner, W. (Co-Projektleiter*in), Monz, T. (Co-Projektleiter*in), Weihs, G. (Co-Projektleiter*in), Roos, C. (Co-Projektleiter*in), Cirac, J. I. (Co-Projektleiter*in), Fink, J. (Co-Projektleiter*in), Paulovics, V. (Projektadministrator*in), Dakic, B. (Co-Projektleiter*in) & Schuch, N. (Co-Projektleiter*in)
1/03/19 → 31/08/27
Projekt: Forschungsförderung

Zitationsweisen

Buhrman, H., Gharibian, S., Landau, Z., Le Gall, F., Schuch, N., & Tamaki, S. (2026). A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT. in S. Assadi, & E. Rotenberg (Hrsg.), Proceedings - 2026 SIAM Symposium on Simplicity in Algorithms, SOSA 2026 (S. 247-253). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611978964.18

@inproceedings{3e26bb24d1074ee09efc5be2449b9a50,

title = "A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT",

abstract = "We present an extremely simple polynomial-space exponential-time (1 − ε)-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomial-space (1−ε)-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 = "Harry Buhrman and Sevag Gharibian and Zeph Landau and \{Le Gall\}, Fran{\c c}ois and Norbert Schuch and Suguru Tamaki",

note = "Publisher Copyright: Copyright {\textcopyright} 2026 by SIAM.; 9th SIAM Symposium on Simplicity in Algorithms, SOSA 2026 ; Conference date: 12-01-2025 Through 14-01-2025",

year = "2026",

doi = "10.1137/1.9781611978964.18",

language = "English",

series = "Symposium on Simplicity in Algorithms Proceedings",

publisher = "Society for Industrial and Applied Mathematics Publications",

pages = "247--253",

editor = "Sepehr Assadi and Eva Rotenberg",

booktitle = "Proceedings - 2026 SIAM Symposium on Simplicity in Algorithms, SOSA 2026",

}

Buhrman, H, Gharibian, S, Landau, Z, Le Gall, F, Schuch, N & Tamaki, S 2026, A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT. in S Assadi & E Rotenberg (Hrsg.), Proceedings - 2026 SIAM Symposium on Simplicity in Algorithms, SOSA 2026. Society for Industrial and Applied Mathematics Publications, Symposium on Simplicity in Algorithms Proceedings, S. 247-253, 9th SIAM Symposium on Simplicity in Algorithms, SOSA 2026, Vancouver, Kanada, 12/01/25. https://doi.org/10.1137/1.9781611978964.18

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT. / Buhrman, Harry; Gharibian, Sevag; Landau, Zeph et al.
Proceedings - 2026 SIAM Symposium on Simplicity in Algorithms, SOSA 2026. Hrsg. / Sepehr Assadi; Eva Rotenberg. Society for Industrial and Applied Mathematics Publications, 2026. S. 247-253 (Symposium on Simplicity in Algorithms Proceedings).

Veröffentlichungen: Beitrag in Buch › Beitrag in Konferenzband › Peer Reviewed

TY - GEN

T1 - A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT

AU - Buhrman, Harry

AU - Gharibian, Sevag

AU - Landau, Zeph

AU - Le Gall, François

AU - Schuch, Norbert

AU - Tamaki, Suguru

PY - 2026

Y1 - 2026

N2 - We present an extremely simple polynomial-space exponential-time (1 − ε)-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomial-space (1−ε)-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.

AB - We present an extremely simple polynomial-space exponential-time (1 − ε)-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomial-space (1−ε)-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.

UR - https://www.scopus.com/pages/publications/105033362416

UR - https://arxiv.org/abs/2510.18164

U2 - 10.1137/1.9781611978964.18

DO - 10.1137/1.9781611978964.18

M3 - Contribution to proceedings

AN - SCOPUS:105033362416

T3 - Symposium on Simplicity in Algorithms Proceedings

SP - 247

EP - 253

BT - Proceedings - 2026 SIAM Symposium on Simplicity in Algorithms, SOSA 2026

A2 - Assadi, Sepehr

A2 - Rotenberg, Eva

PB - Society for Industrial and Applied Mathematics Publications

T2 - 9th SIAM Symposium on Simplicity in Algorithms, SOSA 2026

Y2 - 12 January 2025 through 14 January 2025

ER -

Buhrman H, Gharibian S, Landau Z, Le Gall F, Schuch N, Tamaki S. A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT. in Assadi S, Rotenberg E, Hrsg., Proceedings - 2026 SIAM Symposium on Simplicity in Algorithms, SOSA 2026. Society for Industrial and Applied Mathematics Publications. 2026. S. 247-253. (Symposium on Simplicity in Algorithms Proceedings). doi: 10.1137/1.9781611978964.18

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT

Abstract

Publikationsreihe

Konferenz

Fördermittel

ÖFOS 2012

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Projekte

quantA: Quantum Science Austria

SEQUAM: Symmetries and Entanglement in Quantum Matter

Beyond C: Quantum Information Systems Beyond Classical Capabilities

Zitationsweisen