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)
Document last modified on March 26, 1996