Princeton Theory Lunch

Title:

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

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.