DIMACS Theory Seminar


Title:

Zero Knowledge and the Chromatic Number

Speaker:

Joe Kilian
NEC Research

Place:

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

Time:

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

Abstract:

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)


dimacs-www@dimacs.rutgers.edu
Document last modified on March 26, 1996