BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Satisfiability of Boolean Formulas - Combinatorics and Algorithms
DTSTART:20090511T161500
DTSTAMP:20260407T074600Z
UID:6aa9278eec3c4d5b0c6611ba68f687e741cb479470d40c4ee59034cb
CATEGORIES:Conferences - Seminars
DESCRIPTION:Prof. Emo Welzl\, ETHZ\, Switzerland\nSAT\, the problem of dec
 iding satisfiability of a boolean formula in conjunctive normal form\, is 
 the classical NP-complete problem. Along with and besides its practical re
 levance\, it raises a number of interesting combinatorial and algorithmic 
 questions\, some of which we want to consider here. In a nutshell\, we wan
 t to understand how much interleaving of constraints (here clauses) is nec
 essary for unsatisfiability. This calls quite naturally for the Lovasz Loc
 al Lemma\, a powerful tool in combinatorics. We will review the role of th
 is lemma in SAT including some of the recent developments about an algorit
 hmic version of it (due to Robin Moser).\n\n-Bio:\nEmo Welzl received his 
 doctoral degree from Graz University of Technology\, Austria\, in 1983. He
  was a Professor at Berlin Free University and then moved to Zurich\, wher
 e he has been at the Institute for Theoretical Computer Science of ETH sin
 ce 1996. His research interests are in the foundations of computer science
 \, in particular computational geometry and applications\, combinatorial m
 odels for optimization\, and discrete geometry\; more recently also satisf
 iability of boolean formulas.\n\nE. Welzl's homepage
LOCATION:INM202
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR