Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, March 08, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Lars Engebretsen (KTH Stockholm)
The much celebrated PCP-Theorem can be restated as follows: There is a constant c < 1 such that the following problem is NP-hard: Given a 3-SAT formula and the promise that the either the formula is satisfiable or else at most a fraction c of the clauses in the formula are simultaneously satisfiable, decide if the formula is in fact satisfiable. Using this formulation of the PCP Theorem as a starting point, Håstad [J. ACM 48(4):798--859] obtained optimal inapproximability results for a large number of constraint satisfaction problems. His paper also initiated a large activity in the field of PCP constructions. In this talk, I will give a high-level overview of Håstad's construction and mention some recent results that were proven using Håstad's paradigm.
Automatic MiSe System Software Version 1.4803M | admin login