MIT Department of Electrical Engineering & Computer Science
Some Optimal Inapproximability Results
Johan Hastad
Royal Institute of Technology
Friday, October 18, 1996
10:30 AM
Room NE43-308
Theory of Computation Seminar
Abstract
Very informally we will discuss some recent inapproximability results.
Let MAX-LIN-EQ-2 be the problem of given a set of linear equations
mod 2 determine the maximal number of equations that can be solved
simultaneously. We aim to present a proof that unless NP=P for any e>0
this problem cannot be approximated with 2-e in polynomial time.
The techniques extend to get the inapproximability constant 8/7-e for
MAX-3-SAT.
Host: Shafi Goldwasser
URL of this page:
http://www-eecs.mit.edu/AY96-97/events/11.html
Created: Oct 24, 1996
|
Modified: Jun 24, 1997
This announcement is from the MIT EECS 1996-97 archive.
|
Current events
To MIT EECS home page
|
Your comments
and inquiries are welcome.
