Zero knowledge and the chromatic number
Uriel Feige, Joe Kilian · 2002
We present a new technique, inspired by zero-knowledge proof systems, for proving lower bounds on approximating the chromatic number of a graph. To illustrate this technique we present simple reductions from max-3-coloring and max-3-sat, showing that it is hard to approximate the chromatic number within /spl Omega/(N/sup /spl delta//), for some /spl delta/>0. We then apply our technique in conjunction with the probabilistically checkable proofs of Bellare, Goldreich and Sudan (1995), and of Hastad (1996), and show that it is hard to approximate the chromatic number to within /spl Omega/(N/sup 1-/spl epsiv//) for any E>0, assuming NP/spl sub/ ZPP. Here, ZPP denotes the class of languages decidable by a random expected polynomial-time algorithm that makes no errors. Our result matches (up to low order terms) the known gap for approximating the size of the largest independent set. Previous 0(N/sup /spl delta//) gaps for approximating the chromatic number (such as those by Lund and Yannakakis (1994), and by Furer (1995)) did not match the gap for independent set, and do not extend beyond /spl Omega/(N/sup 1/2-/spl epsiv//).