Paolo Penna: Katalogdaten im Frühjahrssemester 2018 |
| Name | Herr Dr. Paolo Penna |
| URL | https://www.inf.ethz.ch/personal/pennap/ |
| Departement | Informatik |
| Beziehung | Dozent |
| Nummer | Titel | ECTS | Umfang | Dozierende | |
|---|---|---|---|---|---|
| 252-4302-00L | Seminar Algorithmic Game Theory  Limited number of participants. | 2 KP | 2S | P. Widmayer, P. Penna | |
| Kurzbeschreibung | In the seminar we will get familiar with the current original research in the area of algorithmic game theory by reading and presenting selected research papers in that area. | ||||
| Lernziel | Develop an understanding of selected problems of current interest in the area of algorithmic game theory, and a practice of a scientific presentation. | ||||
| Inhalt | Study and understanding of selected topics of current interest in algorithmic game theory such as: Complexity Results (class PPAD, PLS, NP), Sponsored Search, Approximation Algorithms via Algorithmic Game Theory, Price of Anarchy, New paradigms of computation (e.g., envy-fee, truthful), Mechanism Design. | ||||
| Literatur | Selected research articles. | ||||
| Voraussetzungen / Besonderes | You must have passed our "Algorithmic Game Theory" class (or have acquired equivalent knowledge, in exceptional cases). | ||||
| 263-4310-00L | Linear Algebra Methods in Combinatorics | 5 KP | 2V + 2U | P. Penna | |
| Kurzbeschreibung | This course describes the linear algebra bound technique also called dimension argument. To learn the technique we discuss several examples in combinatorics, geometry, and computer science. Besides this technique, the course aims at showing the mathematical elegance of certain proofs and the simplicity of the statements. | ||||
| Lernziel | Becoming familiar with the method and being able to apply it to problems similar to those encountered during the course. | ||||
| Inhalt | This course is (essentially) about one single technique called the "linear algebra bound" (also known as "dimension argument"). We shall see several examples in combinatorics, geometry, and computer science and learn the technique throughout these examples. Towards the end of the course, we shall see the power of this method in proving rather amazing results (e.g., a circuit complexity lower bound, explicit constructions of Ramsey graphs, and a famous conjecture in geometry disproved). The course also aims at illustrating the main ideas behind the proofs and how the various problems are in fact connected to each other. | ||||
| Skript | Lecture notes of each single lecture will be made available (shortly after the lecture itself). | ||||
| Literatur | Most of the material of the course is covered by the following book: 1. Linear algebra methods in combinatorics, by L. Babai and P. Frankl, Department of Computer Science, University of Chicago, preliminary version, 1992. Some parts are also taken from 2. Extremal Combinatorics (with Applications in Computer Science), by Stasys Jukna, Springer-Verlag 2001. | ||||