DIMACS Theory Seminar


Zero Knowledge and the Chromatic Number


Joe Kilian
NEC Research


Room 402, Computer Science Building
35 Olden Street
Princeton University.


12:05 PM (Lunch will be served at 11:45 AM)
Friday, March 29, 1996


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 {\sf max-3-coloring} and {\sf max-3-sat}, showing that it is hard to approximate the chromatic number within $\Omega(N^{\delta})$, for some $\delta> 0$. We then apply our technique in conjunction with the probabilistically checkable proofs of Bellare, Goldreich and Sudan, and of H\a{a}stad, and show that it is hard to approximate the chromatic number to within $\Omega(N^{1-\epsilon})$ for any $\epsilon>0$, assuming ${\sf NP}\not\subseteq {\sf ZPP}$. Here, ${\sf 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 $O(N^{\delta})$ gaps for approximating the chromatic number (such as those by Lund and Yannakakis, and by Furer) did not match the gap for independent set, and do not extend beyond $\Omega(N^{1/2 - \epsilon})$.

(joint work with Uri Feige)

Document last modified on March 26, 1996