Zero Knowledge and the Chromatic Number

✍ Scribed by Uriel Feige; Joe Kilian

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 483 KB
• Volume: 57
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1998.1587

✦ Synopsis

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 0(N $ ) for some $>0. We then apply our technique in conjunction with the probabilistically checkable proofs of Ha# stad and show that it is hard to approximate the chromatic number to within 0(N 1&= ) for any =>0, assuming NP 3 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 O(N $ ) gaps for approximating the chromatic number (such as those by Lund and Yannakakis, and by Furer) did not match the gap for independent set nor extend beyond 0(N 1Â2&= ).