Some optimal inapproximability results
Abstract
We prove optimal, up to an arbitrary ε > 0, inapproximability results for Max-E k -Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Maxk XOR problems are NP-hard for k ≥ 2.
“We remark that these problems belong to the complexity class NP-hard for k ≥ 2 [14].”
From Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems (2024) · cites this paper as [14]
It is NP-hard to achieve an approximation ratio of r* ≥ 16/17 ≈ 0.9412 for Max-Cut on all graphs.
“It has been shown that it is NP-hard to achieve an approximation ratio of r ∗ ≥ 16 / 17 ≈ 0 . 9412 for Max-Cut on all graphs (Håstad, 2001).”
From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Håstad, 2001
No classical polynomial-time approximation algorithm can guarantee to find a solution within 2^k/(2^k + ε) of the optimum for Max k-SAT, for any fixed ε > 0.
“Max k-SAT is N P -hard for k ≥ 2, and no classical polynomialtime approximation algorithm can guarantee to find a solution that is within 2 k -foot_0 2 k + ϵ of the optimum [28] (for any arbitrary but fixed ϵ > 0); note that the decision version of 2-SAT can be solved classically polynomially.”
From High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices (2023) · cites this paper as [28]
Cites
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · see citing works
A threshold of ln n for approximating set cover
Feige, U. (1998) · Journal of the ACM · doi:10.1145/285055.285059 · Cited by 3,092 · see citing works
Approximation algorithms for combinatorial problems
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80044-9 · Cited by 2,223 · see citing works
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653 · see citing works
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,449 · see citing works
Clique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369 · see citing works
Self-citationProbabilistic checking of proofs
Arora, S., & Safra, M. (1998) · Journal of the ACM · doi:10.1145/273865.273901 · Cited by 1,158 · see citing works
Raz, R. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539795280895 · Cited by 720 · see citing works
Algebraic methods for interactive proof systems
Lund, C., Fortnow, L., Karloff, H. J., & Nisan, N. (1992) · Journal of the ACM · doi:10.1145/146585.146605 · Cited by 715 · see citing works
Self-testing/correcting with applications to numerical problems
Blum, M., Luby, M., & Rubinfeld, R. (1993) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(93)90044-w · Cited by 712 · see citing works
Adi Shamir, Z. (1992) · Journal of the ACM · doi:10.1145/146585.146609 · Cited by 676 · see citing works
Checking computations in polylogarithmic time
Babai, L., Fortnow, L., Levin, L. A., & Szegedy, M. (1991) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/103418.103428 · Cited by 627 · see citing works
Interactive proofs and the hardness of approximating cliques
Feige, U., Goldwasser, S., Lovász, L., Safra, M., & Szegedy, M. (1996) · Journal of the ACM · doi:10.1145/226643.226652 · Cited by 525 · see citing works
Multi-prover interactive proofs: how to remove intractability
Ben-Or, M., Goldwasser, S., Kilian, J., & Widgerson, A. (1988) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/62212.62223 · Cited by 471 · see citing works
Non-deterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (1991) · Computational Complexity · doi:10.1007/bf01200056 · Cited by 460 · see citing works
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
Bellare, M., Goldreich, O., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796302531 · Cited by 454 · see citing works
A linear-time approximation algorithm for the weighted vertex cover problem
Bar-Yehuda, R., & Even, S. (1981) · Journal of Algorithms · doi:10.1016/0196-6774(81)90020-1 · Cited by 435 · see citing works
Zero Knowledge and the Chromatic Number
Feige, U., & Kilian, J. (1998) · Journal of Computer and System Sciences · doi:10.1006/jcss.1998.1587 · Cited by 334 · see citing works
Efficient probabilistically checkable proofs and applications to approximations
Bellare, M., Goldwasser, S., Lund, C., et al. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167174 · Cited by 317 · see citing works
Efficient bounds for the stable set, vertex cover and set packing problems
Hochbaum, D. S. (1983) · Discrete Applied Mathematics · doi:10.1016/0166-218x(83)90080-x · Cited by 274 · see citing works
The complexity and approximability of finding maximum feasible subsystems of linear relations
Amaldi, E., & Kann, V. (1995) · Theoretical Computer Science · doi:10.1016/0304-3975(94)00254-g · Cited by 199 · see citing works
Gadgets, Approximation, and Linear Programming
Trevisan, L., Sorkin, G. B., Sudan, M., & Williamson, D. P. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539797328847 · Cited by 195 · see citing works
On the power of multi-prover interactive protocols
Fortnow, L., Rompel, J., & Sipser, M. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90251-8 · Cited by 185 · see citing works
Linearity testing in characteristic two
Mihir Bellare, Y., Coppersmith, D., Håstad, J., Kiwi, M. A., & Sudan, M. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556674 · Cited by 172 · see citing works
Self-citationImproved non-approximability results
Bellare, M., & Sudan, M. (1994) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/195058.195129 · Cited by 162 · see citing works
Approximability of maximum splitting of k-sets and some other Apx-complete problems
Kann, V., Lagergren, J., & Panconesi, A. (1996) · Information Processing Letters · doi:10.1016/0020-0190(96)00046-4 · Cited by 40 · see citing works
A new way to use semidefinite programming with applications to linear equations mod p
Andersson, G., Engebretsen, L. F., & Håstad, J. (1999) · Cited by 16 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 1,726 · see citing works
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827 · see citing works
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019) · Algorithms · doi:10.3390/a12020034 · Cited by 772 · see citing works
Noise-induced barren plateaus in variational quantum algorithms
Wang, S., Fontana, E., Cerezo, M., Sharma, K., Sone, A., Cincio, L., & Coles, P. J. (2021) · Nature Communications · doi:10.1038/s41467-021-27045-6 · Cited by 773 · see citing works
Zhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2020) · Physical Review X · doi:10.1103/physrevx.10.021067 · Cited by 913 · see citing works
Training Variational Quantum Algorithms Is NP-Hard
Bittel, L., & Kliesch, M. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.120502 · Cited by 398 · see citing works
Warm-starting quantum optimization
Egger, D. J., Mareček, J., & Woerner, S. (2021) · Quantum · doi:10.22331/q-2021-06-17-479 · Cited by 269 · see citing works
Challenges and opportunities in quantum optimization
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., et al. (2024) · Nature Reviews Physics · doi:10.1038/s42254-024-00770-9 · Cited by 201 · see citing works
Reachability Deficits in Quantum Approximate Optimization
Akshay, V., Philathong, H., Morales, M. E. S., & Biamonte, J. D. (2020) · Physical Review Letters · doi:10.1103/physrevlett.124.090504 · Cited by 151 · see citing works
Towards large-scale quantum optimization solvers with few qubits
Sciorilli, M., Borges, L., Patti, T. L., García-Martín, D., Camilo, G., Anandkumar, A., & Aolita, L. (2025) · Nature Communications · doi:10.1038/s41467-024-55346-z · Cited by 47 · see citing works
Dalyac, C., Henriet, L., Jeandel, E., Lechner, W., Perdrix, S., Porcheron, M., & Veshchezerova, M. (2021) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-021-00100-3 · Cited by 46 · see citing works
Classical algorithms and quantum limitations for maximum cut on high-girth graphs
Barak, B., & Marwaha, K. (2021) · arXiv · doi:10.48550/arxiv.2106.05900 · Cited by 19
High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
Pelofske, E., Bärtschi, A., Golden, J., & Eidenbenz, S. (2023) · 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00064 · Cited by 15 · see citing works
Network-Free Inference of Knockout Effects in Yeast
Peleg, T., Yosef, N., Ruppin, E., & Sharan, R. (2010) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000635 · Cited by 14 · see citing works
Müller, T., Singh, A., Wilhelm, F. K., & Bode, T. (2024) · arXiv · doi:10.48550/arxiv.2411.19388 · Cited by 5 · see citing works
- Authors
- Håstad, J.
- Affiliations
- KTH Royal Institute of Technology (SE)
- Corresponding author
- Håstad, Johan
- ORCID
- Håstad, Johan
- Venue
- Journal of the ACM
- Published
- 2001-07
- Volume
- 48
- Issue
- 4
- Pages
- 798-859
- ISSN
- 0004-5411
- 1557-735X
- OpenAlex
- W1564025554
- Cited by
- 1,902
- References
- 28
- Citations by year
- 2026: 26 · 2025: 50 · 2024: 41 · 2023: 31 · 2022: 79 · 2021: 68 · 2020: 64 · 2019: 60 · 2018: 56 · 2017: 60 · 2016: 73 · 2015: 74 · 2014: 81 · 2013: 93 · 2012: 95
- FWCI
- 34.59
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM Symposium on Theory of Computing (STOC) (publishedVersion)
- Journal of the ACM (publishedVersion)
- Electronic colloquium on computational complexity
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
- Physical Sciences › Computer Science › Computer Networks and Communications › Constraint Satisfaction and Optimization
- Keywords
- hardness of approximation, MaxCut, vertex cover, approximation lower bounds, overdetermined systems
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
