MIT Department of Electrical Engineering & Computer Science

MIT TOC SEMINAR

Thursday, April 13, 1995

Refreshments at 4:00pm, Talk at 4:15pm in NE43-3rd Floor Lounge

Free bits and approximation

by Mihir Bellare
IBM T.J. Watson Research Center

In a seminal paper in 1991, Feige, Goldwasser, Lovasz, Safra, and Szegedy showed that results on interactive proofs could be used to indicate the hardness of approximation of the Max Clique in a graph. Since then results have got steadily stronger, as larger and larger non-approximability factors are indicated, to the point where the upper bound seems in sight.

Instrumental to the improvements is a focus on a new parameter in proof checking. This is the number of (amortized) free bits used by the verifier-- if he uses f free bits to recognize NP then Max Clique is hard to approximate within N^{1/(1+f)}.

So how low can the free bits go? We begin by lowering them to a value of 2, yielding a N^{1/3} hardness for Max Clique. This is done by introducing a new, and maximally redundant error correcting code.

We then indicate that not only PCPs, but free bits, are intimately associated to Clique hardness: ANY method of proving N^{1/(1+f)} hardness for clique yields essentially a f free bit proof system for NP.

We also indicate some new and quite strong non-approximability factors for Max 3SAT, Max 2SAT and Vertex Cover.

Joint work with: Oded Goldreich (Weizmann) and Madhu Sudan (IBM).

Host: Shafi Goldwasser