DIMACS Princeton Theory Seminar


Non-Approximability Results for MAX SNP -- Towards Tight Results


Oded Goldreich
Weizmann Institute of Science


Room 402, Computer Science Building
35 Olden Street
Princeton University.


12:05 PM (Lunch will be served at 11:45 AM)
Friday, April 19, 1996


The state-of-the art with respect to the non-approximability of MAX SNP hard problems has been steadily improving over the last few years. In combination with the development of new techniques for positive results on approximation, the lower bounds and upper bounds on the approximability of several benchmark problems are already within sight of each other and there's hope that they may get tighter. An interesting feature of the negative results is that while the analysis has gotten tighter, in many senses it has gotten simpler and more general. At this stage it is possible to see the tightness of almost all steps of the analysis. In this talk we will attempt to show all the ingredients leading to the current hardness results for MAX SNP hard problems.

This is joint work with Mihir Bellare (UCSD) and Madhu Sudan (IBM). This talk covers a portion of the work titled ``Free bits, PCP and Non-approximability: Towards tight results''. Previous talks on this work were concentrated on the Max Clique results.

Document last modified on April 16, 1996