Emo Welzl: Catalogue data in Spring Semester 2014 |  |
| Name | Prof. em. Dr. Emo Welzl |
| Name variants | Emo Welzl |
| Field | Computer Science |
| Address | Inst. f. Theoretische Informatik ETH Zürich, OAT Z 13.2 Andreasstrasse 5 8092 Zürich SWITZERLAND |
| emo@inf.ethz.ch | |
| URL | http://www.inf.ethz.ch/personal/emo/ |
| Department | Computer Science |
| Relationship | Professor emeritus |
| Number | Title | ECTS | Hours | Lecturers | |
|---|---|---|---|---|---|
| 252-0491-00L | Satisfiability of Boolean Formulas - Combinatorics and Algorithms  | 7 credits | 3V + 2U + 1A | E. Welzl | |
| Abstract | Basics (CNF, resolution), extremal properties (probabilistic method, derandomization, Local Lemma, partial satisfaction), 2-SAT algorithms (random walk, implication graph), NP-completeness (Cook-Levin), cube (facial structure, Kraft inequality, Hamming balls, covering codes), SAT algorithms (satisfiability coding lemma, Paturi-Pudlák-Zane, Hamming ball search, Schöning), constraint satisfaction. | ||||
| Learning objective | Studying of advanced methods in algorithms design and analysis, and in discrete mathematics along a classical problem in theoretical computer science. | ||||
| Content | Satisfiability (SAT) is the problem of deciding whether a boolean formula in propositional logic has an assignment that evaluates to true. SAT occurs as a problem and is a tool in applications (e.g. Artificial Intelligence and circuit design) and it is considered a fundamental problem in theory, since many problems can be naturally reduced to it and it is the 'mother' of NP-complete problems. Therefore, it is widely investigated and has brought forward a rich body of methods and tools, both in theory and practice (including software packages tackling the problem). This course concentrates on the theoretical aspects of the problem. We will treat basic combinatorial properties (employing the probabilistic method including a variant of the Lovasz Local Lemma), recall a proof of the Cook-Levin Theorem of the NP-completeness of SAT, discuss and analyze several deterministic and randomized algorithms and treat the threshold behavior of random formulas. In order to set the methods encountered into a broader context, we will deviate to the more general set-up of constraint satisfaction and to the problem of proper k-coloring of graphs. | ||||
| Lecture notes | There exists no book that covers the many facets of the topic. Lecture notes covering the material of the course will be distributed. | ||||
| Literature | Here is a list of books with material vaguely related to the course. They can be found in the textbook collection (Lehrbuchsammlung) of the Computer Science Library: George Boole, An Investigation of the Laws of Thought on which are Founded the Mathematical Theories of Logic and Probabilities, Dover Publications (1854, reprinted 1973). Peter Clote, Evangelos Kranakis, Boolean Functions and Computation Models, Texts in Theoretical Computer Science, An EATCS Series, Springer Verlag, Berlin (2002). Nadia Creignou, Sanjeev Khanna, Madhu Sudhan, Complexity Classifications of Boolean Constrained Satisfaction Problems, SIAM Monographs on Discrete Mathematics and Applications, SIAM (2001). Harry R. Lewis, Christos H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall (1998). Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, (1995). Uwe Schöning, Logik für Informatiker, BI-Wissenschaftsverlag (1992). Uwe Schöning, Algorithmik, Spektrum Akademischer Verlag, Heidelberg, Berlin (2001). Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, Boston (1997). Klaus Truemper, Design of Logic-based Intelligent Systems, Wiley-Interscience, John Wiley & Sons, Inc., Hoboken (2004). | ||||
| Prerequisites / Notice | Language: The course will be given in German if nobody expresses preference for English. All accompanying material (lecture notes, web-page, etc.) is supplied in English. Prerequisites: The course assumes basic knowledge in propositional logic, probability theory and discrete mathematics, as it is supplied in the first two years of the Bachelor Studies at ETH. Outlook: There will be a follow-up seminar, SAT, on the topic in the subsequent semester (attendance of this course will be a prerequisite for participation in the seminar). There are ample possibilities for theses of various types (Master-, etc.). | ||||
| 252-4202-00L | Seminar in Theoretical Computer Science | 2 credits | 2S | E. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger | |
| Abstract | Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates. | ||||
| Learning objective | To get an overview of current research in the areas covered by the involved research groups. To present results from the literature. | ||||
| 252-4220-00L | A Taste of Research: Algorithms and Combinatorics | 2 credits | 2S | B. Gärtner, J. Matousek, A. Steger, E. Welzl, P. Widmayer | |
| Abstract | Students work together with lecturers on open problems in algorithms and combinatorics. | ||||
| Learning objective | The goal is to learn and practice important research techniques: literature search, understanding and presenting research papers, developing ideas in the group, testing of conjectures with the computer, writing down results. | ||||
| Content | Work on original research papers and open problems in the areas of algorithms and combinatorics. | ||||
| Lecture notes | Not available. | ||||
| Literature | Will be announced in the seminar and on the seminar's web page. | ||||
| Prerequisites / Notice | Passed first-year exam. | ||||
| 263-4205-00L | Polynomials | 4 credits | 2V + 1U | J. Matousek, E. Welzl | |
| Abstract | Algebraic methods belong among the most powerful and succesful mathematical tools in computer science and discrete mathematics. The course covers a number of results, some of them fairly recent, whose proofs illustrate general techniques. | ||||
| Learning objective | Extending the knowledge of mathematical methods that proved useful in recent research related to theoretical computer science. The students should understand several successful ideas of applying the properties of multivariate polynomials to various problems. | ||||
| Content | From the wide area of algebraic methods, we focus mainly on applications of polynomials, and we will encounter some of the elementary concepts of algebraic geometry. Here are some of the main themes: Dimension arguments using spaces of polynomials. Matchings and determinants. Randomized testing of polynomial identities. Space partitions using polynomials and geometric incidence theorems. "Contagious vanishing" arguments, geometry of lines in space. | ||||
| Lecture notes | One part of the lecture will follow the book "Thirty-three miniatures" by J. Matousek. The rest will be based on recent research papers and on a book in preparation by Larry Guth. | ||||
| Literature | J. Matousek: Thirty-three miniatures, Amer. Math. Soc. 2010 | ||||