Satisfiability of Boolean Formulas - Combinatorics and Algorithms
Event details
| Date | 11.05.2009 |
| Hour | 16:15 |
| Speaker | Prof. Emo Welzl, ETHZ, Switzerland |
| Location |
INM202
|
| Category | Conferences - Seminars |
SAT, the problem of deciding satisfiability of a boolean formula in conjunctive normal form, is the classical NP-complete problem. Along with and besides its practical relevance, it raises a number of interesting combinatorial and algorithmic questions, some of which we want to consider here. In a nutshell, we want to understand how much interleaving of constraints (here clauses) is necessary for unsatisfiability. This calls quite naturally for the Lovasz Local Lemma, a powerful tool in combinatorics. We will review the role of this lemma in SAT including some of the recent developments about an algorithmic version of it (due to Robin Moser).
-Bio:
Emo 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, where he has been at the Institute for Theoretical Computer Science of ETH since 1996. His research interests are in the foundations of computer science, in particular computational geometry and applications, combinatorial models for optimization, and discrete geometry; more recently also satisfiability of boolean formulas.
E. Welzl's homepage
Practical information
- General public
- Free