Free Bits, PCPs and Non-Approximability

by Mihir Bellare, Oded Goldreich and Madhu Sudan


Abstract

We investigates several aspects of the connection between probabilistically checkable proof (PCP) systems and the complexity of approximation, with emphasis on proving tight non-approximability results.

A breakthrough in the study of the complexity of approximation came about with the reduction of Feige et. al. (FGLSS) which translates PCP systems (for NP) into NP-hardness approximation results for MaxClique. We show that PCP systems are inherent to the study of approximation, and in particular amortized free-bits capture the hardness factor for MaxClique. Specifically, the following two (loosely stated) conditions are equivalent:
(1) MaxClique is NP-hard to approximate to within $N^(1/(1+f))$ factor;
(2) NP has PCP systems of logarithmic randomness and amortized free-bit complexity $f$.

We also introduce new machinery (most notably the Long-Code) for the construction of PCP systems, yielding improvements in all investigated parameters of PCP systems for NP. In particular, we obatain,

Finally, we initiate a systematic study of properties of PCP systems and transformation among them.

Versions


Back to Oded Goldreich's homepage or to General list of Oded Goldreich's papers