Abstract

We derandomize results of Hstad (1999) and We further derandomize results of Khot (FOCS '01) and show that for some > 0, no quasi-polynomial time algorithm approximates MAX CLIQUE or CHROMATIC NUMBER to within n/2 (log n) 1- , unless N P = P.

Citation impact

641

total citations

FWCI: 31.44
Percentile: 100%
References: 40

Citations per year

Authors

DZ
David ZuckermanCorresponding

Topics & keywords

Topics

Complexity and Algorithms in Graphs100%
Cryptography and Data Security100%
Machine Learning and Algorithms98%

Keywords

Randomness
Mathematics
Combinatorics
Binary logarithm
Clique
Constant (computer programming)
Omega
Discrete mathematics

No related works found for this paper.

Funding

NS
National Science Foundation
Awards: 0310960, 0634811, CCF-0634811
JS
John Simon Guggenheim Memorial Foundation
HU
Harvard University
RI
Radcliffe Institute for Advanced Study, Harvard University