Free Bits, PCPs and Non-Approximability
by Mihir Bellare, Oded Goldreich and Madhu Sudan
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
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,
- PCP systems for NP, of logarithmic randomness
and 2 amortized free-bits.
Thus MaxClique is NP-hard to approximate within yields a $N^(1/3)$ factor.
- Simple PCP systems for NP leading to substantial improvements
in the hardness results for several popular MaxSNP problems
such as Max3SAT, Max2SAT, MaxCUT and MinVertexCover.
Finally, we initiate a systematic study of properties of PCP systems
and transformation among them.
- 1st version, May 1995. (Not avialable - superseded by 2nd version.)
version, August 1995. (126 pages, 1.2 MB)
version, December 1995. (128 pages, 1.2 MB)
Starting with this version, our best results for PCP and non-approximability
of MaxSNP problems are obtained via a new adaptive
codeword test (and the induced new verifier).
version, December 1996. (127 pages, 1.2 MB)
Corrects a (resticted in scope) error in previous versions.
- 5th version, July 1997.
(120 pages, 1.2 MB) [PDF]
Significant re-organization of previous versions.
- Final version
Vol. 27, No. 3, pages 804-915, June 1998.
Back to Oded Goldreich's homepage
or to General list of Oded Goldreich's papers