Linear degree extractors and the inapproximability of max clique and chromatic number

By David Zuckerman. Symposium on the Theory of Computing, 2006

1,076 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

View Paper: https://www.semanticscholar.org/paper/f76354814dd0e1c9696396154e927a624649f2f7

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

Citations in the corpus

Multiwinner Voting with Fairness Constraints (2017, background): “The proof relies on an inapproximability result for independent set [Zuckerman, 2006].”
Ranking with Fairness Constraints (2017, methodology): “…If there was a procedure to solve the constrained ranking feasibility problem for c , then one could approximate in polynomial time the cardinality of the maximum independent set in a graph with an approximation ratio of | V | 1 − 1 / ( c +1) , which is not possible unless P = NP [Has96, Zuc07].”
Exactly Computing the Local Lipschitz Constant of ReLU Networks (2020, background): “Classically, it has been shown that MIS is NP-hard to optimize, but also is one of the hardest problems to approximate and does not admit a deterministic polynomial time algorithm to solve the O ( n 1 − ) -gap problem (Zuckerman, 2007).”
The Design of Approximation Algorithms (2011, background): “4 on the hardness of approximating the maximum clique problem is due to H̊astad [158], with a strengthening due to Zuckerman [296].”
Most Tensor Problems Are NP-Hard (2009, background): “It is also known that α(G) is NP-hard to approximate13 [Håstad 1999; Zuckerman 2006] (see also the survey [De Klerk 2008]).”
Set Partitioning via Inclusion-Exclusion (2009, background): “The approximability of the chromatic number is very well studied; the best known polynomial time algorithm guarantees only an approximation ratio of O(n log−3 n log log(2) n) [25], and χ(G) is NP-hard to approximate within n1−o(1) [51].”
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz (2017, neutral): “minimizethenumberofcolorsrequiredtoproperlycolorit. Approximability:Thebestclassicalalgorithm[83]achievesapproximationratioO(n(loglogn) 2 log3 n ), andwecannotdobetterthann1− forany>0 unlessP= NP[71]. Foredge-colorings ofmultigraphs,thereisa(1.1 + 0.8/κ∗)-approximatealgorithm[84]. Conﬁgurationspa”
A review on algorithms for maximum clique problems (2015, neutral): “An imrpoved result shows that the MCP is not approximable within n 1 − ǫ for any ǫ > 0 unless NP = P (Zuckerman, 2006).”