# Search result: Catalogue data in Autumn Semester 2020

Computer Science Master | ||||||

Master Studies (Programme Regulations 2020) | ||||||

Majors | ||||||

Major in Theoretical Computer Science | ||||||

Elective Courses | ||||||

Number | Title | Type | ECTS | Hours | Lecturers | |
---|---|---|---|---|---|---|

252-1407-00L | Algorithmic Game Theory | W | 7 credits | 3V + 2U + 1A | P. Penna | |

Abstract | Game theory provides a formal model to study the behavior and interaction of self-interested users and programs in large-scale distributed computer systems without central control. The course discusses algorithmic aspects of game theory. | |||||

Learning objective | Learning the basic concepts of game theory and mechanism design, acquiring the computational paradigm of self-interested agents, and using these concepts in the computational and algorithmic setting. | |||||

Content | The Internet is a typical example of a large-scale distributed computer system without central control, with users that are typically only interested in their own good. For instance, they are interested in getting high bandwidth for themselves, but don't care about others, and the same is true for computational load or download rates. Game theory provides a mathematical model for the behavior and interaction of such selfish users and programs. Classic game theory dates back to the 1930s and typically does not consider algorithmic aspects at all. Only a few years back, algorithms and game theory have been considered together, in an attempt to reconcile selfish behavior of independent agents with the common good. This course discusses algorithmic aspects of game-theoretic models, with a focus on recent algorithmic and mathematical developments. Rather than giving an overview of such developments, the course aims to study selected important topics in depth. Outline: - Introduction to classic game-theoretic concepts. - Existence of stable solutions (equilibria), algorithms for computing equilibria, computational complexity. - Speed of convergence of natural game playing dynamics such as best-response dynamics or regret minimization. - Techniques for bounding the quality-loss due to selfish behavior versus optimal outcomes under central control (a.k.a. the 'Price of Anarchy'). - Design and analysis of mechanisms that induce truthful behavior or near-optimal outcomes at equilibrium. - Selected current research topics, such as Google's Sponsored Search Auction, the U.S. FCC Spectrum Auction, Kidney Exchange. | |||||

Lecture notes | Lecture notes will be usually posted on the website shortly after each lecture. | |||||

Literature | "Algorithmic Game Theory", edited by N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge University Press, 2008; "Game Theory and Strategy", Philip D. Straffin, The Mathematical Association of America, 5th printing, 2004 Several copies of both books are available in the Computer Science library. | |||||

Prerequisites / Notice | Audience: Although this is a Computer Science course, we encourage the participation from all students who are interested in this topic. Requirements: You should enjoy precise mathematical reasoning. You need to have passed a course on algorithms and complexity. No knowledge of game theory is required. | |||||

401-3054-14L | Probabilistic Methods in Combinatorics | W | 6 credits | 2V + 1U | B. Sudakov | |

Abstract | This course provides a gentle introduction to the Probabilistic Method, with an emphasis on methodology. We will try to illustrate the main ideas by showing the application of probabilistic reasoning to various combinatorial problems. | |||||

Learning objective | ||||||

Content | The topics covered in the class will include (but are not limited to): linearity of expectation, the second moment method, the local lemma, correlation inequalities, martingales, large deviation inequalities, Janson and Talagrand inequalities and pseudo-randomness. | |||||

Literature | - The Probabilistic Method, by N. Alon and J. H. Spencer, 3rd Edition, Wiley, 2008. - Random Graphs, by B. Bollobás, 2nd Edition, Cambridge University Press, 2001. - Random Graphs, by S. Janson, T. Luczak and A. Rucinski, Wiley, 2000. - Graph Coloring and the Probabilistic Method, by M. Molloy and B. Reed, Springer, 2002. | |||||

401-3901-00L | Mathematical Optimization | W | 11 credits | 4V + 2U | R. Zenklusen | |

Abstract | Mathematical treatment of diverse optimization techniques. | |||||

Learning objective | The goal of this course is to get a thorough understanding of various classical mathematical optimization techniques with an emphasis on polyhedral approaches. In particular, we want students to develop a good understanding of some important problem classes in the field, of structural mathematical results linked to these problems, and of solution approaches based on this structural understanding. | |||||

Content | Key topics include: - Linear programming and polyhedra; - Flows and cuts; - Combinatorial optimization problems and techniques; - Equivalence between optimization and separation; - Brief introduction to Integer Programming. | |||||

Literature | - Bernhard Korte, Jens Vygen: Combinatorial Optimization. 6th edition, Springer, 2018. - Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. This work has 3 volumes. - Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. - Alexander Schrijver: Theory of Linear and Integer Programming. John Wiley, 1986. | |||||

Prerequisites / Notice | Solid background in linear algebra. | |||||

401-4521-70L | Geometric Tomography - Uniqueness, Statistical Reconstruction and Algorithms | W | 4 credits | 2V | J. Hörrmann | |

Abstract | Self-contained course on the theoretical aspects of the reconstruction of geometric objects from tomographic projection and section data. | |||||

Learning objective | Introduction to geometric tomography and understanding of various theoretical aspects of reconstruction problems. | |||||

Content | The problem of reconstruction of an object from geometric information like X-ray data is a classical inverse problem on the overlap between applied mathematics, statistics, computer science and electrical engineering. We focus on various aspects of the problem in the case of prior shape information on the reconstruction object. We will answer questions on uniqueness of the reconstruction and also cover statistical and algorithmic aspects. | |||||

Literature | R. Gardner: Geometric Tomography F. Natterer: The Mathematics of Computerized Tomography A. Rieder: Keine Probleme mit inversen Problemen | |||||

Prerequisites / Notice | A sound mathematical background in geometry, analysis and probability is required though a repetition of relevant material will be included. The ability to understand and write mathematical proofs is mandatory. |

- Page 1 of 1