Search result: Catalogue data in Spring Semester 2016
Computer Science Master | ||||||
Focus Courses | ||||||
Focus Courses in Theoretical Computer Science | ||||||
Focus Core Courses Theoretical Computer Science | ||||||
Number | Title | Type | ECTS | Hours | Lecturers | |
---|---|---|---|---|---|---|
252-0407-00L | Cryptography Foundations | W | 7 credits | 3V + 2U + 1A | U. Maurer | |
Abstract | Fundamentals and applications of cryptography. Cryptography as a mathematical discipline: reductions, constructive cryptography paradigm, security proofs. The discussed primitives include cryptographic functions, pseudo-randomness, symmetric encryption and authentication, public-key encryption, key agreement, and digital signature schemes. Selected cryptanalytic techniques. | |||||
Objective | The goals are: (1) understand the basic theoretical concepts and scientific thinking in cryptography; (2) understand and apply some core cryptographic techniques and security proof methods; (3) be prepared and motivated to access the scientific literature and attend specialized courses in cryptography. | |||||
Content | See course description. | |||||
Lecture notes | yes. | |||||
Prerequisites / Notice | Familiarity with the basic cryptographic concepts as treated for example in the course "Information Security" is required but can in principle also be acquired in parallel to attending the course. | |||||
252-0491-00L | Satisfiability of Boolean Formulas - Combinatorics and Algorithms Takes place for the last time in spring 2016. | W | 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. | |||||
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 English by default (it's German only 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.). | |||||
Focus Elective Courses Theoretical Computer Science | ||||||
Number | Title | Type | ECTS | Hours | Lecturers | |
252-1403-00L | Introduction to Quantum Information Processing | W | 3 credits | 2G | S. Wolf | |
Abstract | Followed by an introduction to the basic principles of quantum physics, such as superposition, interference, or entanglement, a variety of subjects are treated: Quantum algorithms, teleportation, quantum communication complexity and "pseudo-telepathy", quantum cryptography, as well as the main concepts of quantum information theory. | |||||
Objective | It is the goal of this course to get familiar with the most important notions that are of importance for the connection between Information and Physics. The formalism of Quantum Physics will be motivated and derived, and the use of these laws for information processing will be understood. In particular, the important algorithms of Grover as well as Shor will be studied and analyzed. | |||||
Content | According to Landauer, "information is physical". In quantum information, one is interested in the consequences and the possibilites offered by the laws of quantum physics for information processing. Followed by an introduction to the basic principles of quantum physics, such as superposition, interference, or entanglement, a variety of subjects are treated: Quantum algorithms, teleportation, quantum communication complexity and "pseude-telepathy", quantum cryptography, as well as the main concepts of quantum information theory. | |||||
252-1424-00L | Models of Computation | W | 6 credits | 2V + 2U + 1A | M. Cook | |
Abstract | This course surveys many different models of computation: Turing Machines, Cellular Automata, Finite State Machines, Graph Automata, Circuits, Tilings, Lambda Calculus, Fractran, Chemical Reaction Networks, Hopfield Networks, String Rewriting Systems, Tag Systems, Diophantine Equations, Register Machines, Primitive Recursive Functions, and more. | |||||
Objective | see above | |||||
Content | This course surveys many different models of computation: Turing Machines, Cellular Automata, Finite State Machines, Graph Automata, Circuits, Tilings, Lambda Calculus, Fractran, Chemical Reaction Networks, Hopfield Networks, String Rewriting Systems, Tag Systems, Diophantine Equations, Register Machines, Primitive Recursive Functions, and more. | |||||
401-3052-05L | Graph Theory | W | 5 credits | 2V + 1U | B. Sudakov | |
Abstract | Basic notions, . Trees, spanning trees, Caley formula, Vertex and edge connectivity, blocks, 2-connectivity, Maders theorem, Mengers theorem, Euleraing graphs, Hamilton cycle, Dirac theorem, Matchings, theorem of Hall, Konig, Tutte, Planar graph, Euler's formula, Basic non-planar graphs, Graph colorings, greedy, brooks theorem, 5-colorings of planar graphs | |||||
Objective | The students will get an overview over the most fundamental questions concerning graph theory. We expect them to understand the proof techniques and to use them autonomously on related problems. | |||||
Lecture notes | Lecture will be only at the blackboard. | |||||
Literature | West, D.: "Introduction to Graph Theory" Diestel, R.: "Graph Theory" Further literature links will be provided in the lecture. | |||||
Prerequisites / Notice | NOTICE: This course unit was previously offered as 252-1408-00L Graphs and Algorithms. | |||||
401-3903-11L | Geometric Integer Programming | W | 6 credits | 2V + 1U | R. Weismantel | |
Abstract | Integer programming is the task of minimizing a linear function over all the integer points in a polyhedron. This lecture introduces the key concepts of an algorithmic theory for solving such problems. | |||||
Objective | The purpose of the lecture is to provide a geometric treatment of the theory of integer optimization. | |||||
Content | Key topics are: - lattice theory and the polynomial time solvability of integer optimization problems in fixed dimension, - the theory of integral generating sets and its connection to totally dual integral systems, - finite cutting plane algorithms based on lattices and integral generating sets. | |||||
Lecture notes | not available, blackboard presentation | |||||
Literature | Bertsimas, Weismantel: Optimization over Integers, Dynamic Ideas 2005. Schrijver: Theory of linear and integer programming, Wiley, 1986. | |||||
Prerequisites / Notice | "Mathematical Optimization" (401-3901-00L) | |||||
401-3908-09L | Polyhedral Computation | W | 6 credits | 2V + 1U | K. Fukuda | |
Abstract | Polyhedral computation deals with various computational problems associated with convex polyhedra in general dimension. Typical problems include the representation conversion problem (between halfspace and generator representations), the polytope volume computation, the construction of hyperplane arrangements and zonotopes, the Minkowski addition of convex polytopes. | |||||
Objective | ||||||
Content | In this lecture, we study basic and advanced techniques for polyhedral computation in general dimension. We review some classical results on convexity and convex polyhedra such as polyhedral duality, Euler's relation, shellability, McMullen's upper bound theorem, the Minkowski-Weyl theorem, face counting formulas for arrangements, Shannon's theorem on simplicial cells. Our main goal is to investigate fundamental problems in polyhedral computation from both the complexity theory and the viewpoint of algorithmic design. Optimization methods, in particular, linear programming algorithms, will be used as essential building blocks of advanced algorithms in polyhedral computation. Various research problems, both theoretical and algorithmic, in polyhedral computation will be presented. We also study applications of polyhedral computation in combinatorial optimization, integer programming, game theory, parametric linear and quadratic programming. Teaching assistant: May Szedlák | |||||
Lecture notes | Lecture Notes and Introduction Materials: Link Exercises: Link | |||||
Prerequisites / Notice | This course assumes the basic knowledge of linear programming, which is taught in courses such as "Mathematical Optimization" (401-3901-00L) and "Introduction to Optimization" (401-2903-00L). / Solving all exercise problems is recommended for a student to be ready for the exam. | |||||
401-4904-00L | Combinatorial Optimization | W | 6 credits | 2V + 1U | R. Zenklusen | |
Abstract | Combinatorial Optimization deals with efficiently finding a provably strong solution among a finite set of options. This course discusses key combinatorial structures and techniques to design efficient algorithms for combinatorial optimization problems. We put a strong emphasis on polyhedral methods, which proved to be a powerful and unifying tool throughout combinatorial optimization. | |||||
Objective | The goal of this lecture is to get a thorough understanding of various modern combinatorial optimization techniques with an emphasis on polyhedral approaches. Students will learn a general toolbox to tackle a wide range of combinatorial optimization problems. | |||||
Content | Key topics include: - Polyhedral descriptions; - Combinatorial uncrossing; - Ellipsoid method; - Equivalence between separation and optimization; - Design of efficient approximation algorithms for hard problems. | |||||
Lecture notes | Not available. | |||||
Literature | - Bernhard Korte, Jens Vygen: Combinatorial Optimization. 5th edition, Springer, 2012. - Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003. This work has 3 volumes. | |||||
Prerequisites / Notice | We recommend that students interested in Combinatorial Optimization first attend the course "Mathematical Optimization" (401-3901-00L). | |||||
252-0408-00L | Cryptographic Protocols Does not take place this semester. | W | 5 credits | 2V + 2U | U. Maurer | |
Abstract | The course presents a selection of hot research topics in cryptography. The choice of topics varies and may include provable security, interactive proofs, zero-knowledge protocols, secret sharing, secure multi-party computation, e-voting, etc. | |||||
Objective | Indroduction to a very active research area with many gems and paradoxical results. Spark interest in fundamental problems. | |||||
Content | The course presents a selection of hot research topics in cryptography. The choice of topics varies and may include provable security, interactive proofs, zero-knowledge protocols, secret sharing, secure multi-party computation, e-voting, etc. | |||||
Lecture notes | the lecture notes are in German, but they are not required as the entire course material is documented also in other course material (in english). | |||||
Prerequisites / Notice | A basic understanding of fundamental cryptographic concepts (as taught for example in the course Information Security or in the course Cryptography) is useful, but not required. | |||||
Seminar in Theoretical Computer Science | ||||||
Number | Title | Type | ECTS | Hours | Lecturers | |
252-3002-00L | Algorithms for Database Systems Limited number of participants. | W | 2 credits | 2S | P. Widmayer | |
Abstract | Query processing, optimization, stream-based systems, distributed and parallel databases, non-standard databases. | |||||
Objective | Develop an understanding of selected problems of current interest in the area of algorithms for database systems. | |||||
252-4102-00L | Seminar on Randomized Algorithms and Probabilistic Methods | W | 2 credits | 2S | A. Steger | |
Abstract | The aim of the seminar is to study papers which bring the students to the forefront of today's research topics. This semester we will study selected papers of the conference Symposium on Discrete Algorithms (SODA16). | |||||
Objective | Read papers from the forefront of today's research; learn how to give a scientific talk. | |||||
Prerequisites / Notice | The seminar is open for both students from mathematics and students from computer science. As prerequisite we require that you passed the course Randomized Algorithms and Probabilistic Methods (or equivalent, if you come from abroad). | |||||
252-4202-00L | Seminar in Theoretical Computer Science | W | 2 credits | 2S | E. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, B. Sudakov | |
Abstract | Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates. | |||||
Objective | To get an overview of current research in the areas covered by the involved research groups. To present results from the literature. | |||||
252-4302-00L | Seminar Algorithmic Game Theory Limited number of participants. | W | 2 credits | 2S | P. Widmayer, P. Dütting | |
Abstract | 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. | |||||
Objective | Develop an understanding of selected problems of current interest in the area of algorithmic game theory, and a practice of a scientific presentation. | |||||
Content | 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. | |||||
Literature | Selected research articles. | |||||
Prerequisites / Notice | You must have passed our "Algorithmic Game Theory" class (or have acquired equivalent knowledge, in exceptional cases). | |||||
252-4800-00L | Quantum Information and Cryptography | W | 2 credits | 3S | S. Wolf | |
Abstract | In this advanced seminar, various topics are treated in the intersection of quantum physics, information theory, and cryptography. | |||||
Objective | see above | |||||
263-4203-00L | Geometry: Combinatorics and Algorithms | W | 2 credits | 2S | B. Gärtner, M. Hoffmann, E. Welzl | |
Abstract | This seminar is held once a year and complements the course Geometry: Combinatorics & Algorithms. Students of the seminar will present original research papers, some classic and some of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area. | |||||
Objective | Each student is expected to read, understand, and elaborate on a selected research paper. To this end, (s)he should give a 45-min. presentation about the paper. The process includes * getting an overview of the related literature; * understanding and working out the background/motivation: why and where are the questions addressed relevant? * understanding the contents of the paper in all details; * selecting parts suitable for the presentation; * presenting the selected parts in such a way that an audience with some basic background in geometry and graph theory can easily understand and appreciate it. | |||||
Prerequisites / Notice | To attend the seminar, some knowledge in (discrete and computational) geometry and graphs and algorithms is required. Thus, previous participation in the course "Geometry: Combinatorics & Algorithms" or a comparable course is strongly encouraged. |
- Page 1 of 1