Hardness of Finding Independent Sets in Almost q-Colorable Graphs.

Subhash Khot Rishi Saket

Published in: FOCS (2012)

Keyphrases

information systems
computational complexity
directed graph
graph matching
learning theory
graph databases
series parallel
real time
graph structures
random graphs
graph theoretic
graph partitioning
graph model
graph theory
bipartite graph
information theoretic
random walk