Princeton Theory Lunch


Title:

Hastad's paper on "Tight Inapproximability Results

Speaker:

George Karakostas
Princeton University

Place:

Computer Science Building, Room 402
Princeton University

Time:

Lunch will be served at 11:45 a.m.
Talk will begin at 12:10
Thursday, December 5, 1996
Abstract:

This talk presents the basic ideas in Johan Hastad's recent paper, in which he shows (among other things) that approximating MAX-3SAT within a factor 7/8 - \epsilon is NP-hard. He uses fourier analysis to obtain his result.


dimacs-www@dimacs.rutgers.edu
Document last modified on November 26, 1996