Some optimal inapproximability results

By J. Håstad. 2001

1,973 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Meta-attention for ViT-backed Continual Learning (2022, background): “However, the binary mask cannot be directly optimized along with the new task classifier when back-propagation, for it belongs to the non-differential categorical distribution, leading to the NP-hard problem [12].”
Non-monotone submodular maximization under matroid and knapsack constraints (2009, background): “This problem appears in many important optimization problems including cuts in graphs [19, 41, 26], rank function of matroids [12, 16], set covering problems [13], plant location problems [9, 10, 11, 2], and certain satisﬁability problems [25, 14], and maximum entropy sampling [32, 33].”
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz (2017, methodology): “Approximability: No efficient 1 + e classical approximation algorithm unless P = NP [53].”
Complexity theoretic limitations on learning halfspaces (2015, background): “Hastad’s celebrated result [43] asserts that if P 6= NP, then for every η > 0, it is hard to distinguish K-XOR instances with value ≥ 1− η from instances with with value ≤ 1 2 + η.”
Training Variational Quantum Algorithms Is NP-Hard. (2021, unknown): “941 [20].”
Authenticating Pervasive Devices with Human Protocols (2005, background): “The LPN problem is known to be NP-Hard [2], and is hard even within an approximation ratio of two [14].”
On the difficulty of approximately maximizing agreements (2000, background): “The following theorem, due to H˚astad [13], shows that approximating the optimal solution to MAX-E2-SAT is hard.”
The Algorithm Design Manual (2020, background): “Hastad [Has97] proved there does not exist a better than 1.”
Discrete Graph Hashing (2014, background): “In specific, since the Max-Cut problem is a special case of problem (4) when ρ = 0 and r = 1, there exists no polynomial-time algorithm which can achieve the global optimum, or even an approximate solution with its objective value beyond 16/17 of the global maximum unless P = NP [11].”
Online Submodular Maximization with Preemption (2015, background): “On the hardness side, a (12/13+ ε)-approximation algorithm will imply P = NP [36].”
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (2012, unknown): “USM captures many well studied problems such as Max-Cut, Max-DiCut [15], [20], [22], [25], [27], [36], variants of Max-SAT, and maximum facility location [1], [7], [8].”
Verifying computations without reexecuting them (2015, background): “In fact, the acclaimed PCP theorem [1, 2], together with reﬁnements [27], implies that a veriﬁer only has to check three randomly chosen bits in a suitably encoded proof!”