Reductions, codes, PCPs, and inapproximability

Research output: Contribution to journalConference articlepeer-review

5 Scopus citations

Abstract

Many recent results show the hardness of approximating NP-hard functions. We formalize, in a very simple way, what these results involve: a code-like Levin reduction. Assuming a well-known complexity assumption, we show that such reductions cannot prove the NP-hardness of the following problems, where ε is any positive fraction: (i) achieving an approximation ratio n 1/2 +ε for Clique, (ii) achieving an approximation ratio 1.5 + ε for Vertex Cover, and (iii) coloring a 3-colorable graph with O(log n) colors. In fact, we explain why current reductions cannot prove the NP-hardness of coloring 3-colorable graphs with 9 colors. Our formalization of a code-like reduction, together with our justification of why such reductions are natural, also clarifies why current proofs of inapproximability results use error-correcting codes.

Original languageEnglish (US)
Pages (from-to)404-413
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 1995
EventProceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science - Milwaukee, WI, USA
Duration: Oct 23 1995Oct 25 1995

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Reductions, codes, PCPs, and inapproximability'. Together they form a unique fingerprint.

Cite this