Search result: Catalogue data in Spring Semester 2016

Computer Science Master Information
Focus Courses
Focus Courses in Theoretical Computer Science
Focus Core Courses Theoretical Computer Science
NumberTitleTypeECTSHoursLecturers
252-0407-00LCryptography Foundations Information W7 credits3V + 2U + 1AU. Maurer
AbstractFundamentals 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.
ObjectiveThe 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.
ContentSee course description.
Lecture notesyes.
Prerequisites / NoticeFamiliarity 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-00LSatisfiability of Boolean Formulas - Combinatorics and Algorithms Information
Takes place for the last time in spring 2016.
W7 credits3V + 2U + 1AE. Welzl
AbstractBasics (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.
ObjectiveStudying of advanced methods in algorithms design and analysis, and in discrete mathematics along a classical problem in theoretical computer science.
ContentSatisfiability (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 notesThere exists no book that covers the many facets of the topic. Lecture notes covering the material of the course will be distributed.
LiteratureHere 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 / NoticeLanguage: 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
NumberTitleTypeECTSHoursLecturers
252-1403-00LIntroduction to Quantum Information Processing Information W3 credits2GS. Wolf
AbstractFollowed 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.
ObjectiveIt 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.
ContentAccording 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-00LModels of ComputationW6 credits2V + 2U + 1AM. Cook
AbstractThis 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.
Objectivesee above
ContentThis 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-05LGraph Theory Information W5 credits2V + 1UB. Sudakov
AbstractBasic 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
ObjectiveThe 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 notesLecture will be only at the blackboard.
LiteratureWest, D.: "Introduction to Graph Theory"
Diestel, R.: "Graph Theory"

Further literature links will be provided in the lecture.
Prerequisites / NoticeNOTICE: This course unit was previously offered as 252-1408-00L Graphs and Algorithms.
401-3903-11LGeometric Integer ProgrammingW6 credits2V + 1UR. Weismantel
AbstractInteger 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.
ObjectiveThe purpose of the lecture is to provide a geometric treatment of the theory of integer optimization.
ContentKey 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 notesnot available, blackboard presentation
LiteratureBertsimas, 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-09LPolyhedral ComputationW6 credits2V + 1UK. Fukuda
AbstractPolyhedral 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
ContentIn 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 notesLecture Notes and Introduction Materials:
Link

Exercises:
Link
Prerequisites / NoticeThis 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-00LCombinatorial Optimization Information W6 credits2V + 1UR. Zenklusen
AbstractCombinatorial 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.
ObjectiveThe 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.
ContentKey topics include:
- Polyhedral descriptions;
- Combinatorial uncrossing;
- Ellipsoid method;
- Equivalence between separation and optimization;
- Design of efficient approximation algorithms for hard problems.
Lecture notesNot 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 / NoticeWe recommend that students interested in Combinatorial Optimization first attend the course "Mathematical Optimization" (401-3901-00L).
252-0408-00LCryptographic Protocols Information
Does not take place this semester.
W5 credits2V + 2UU. Maurer
AbstractThe 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.
ObjectiveIndroduction to a very active research area with many gems and paradoxical
results. Spark interest in fundamental problems.
ContentThe 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 notesthe 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 / NoticeA 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
NumberTitleTypeECTSHoursLecturers
252-3002-00LAlgorithms for Database Systems Information
Limited number of participants.
W2 credits2SP. Widmayer
AbstractQuery processing, optimization, stream-based systems, distributed and parallel databases, non-standard databases.
ObjectiveDevelop an understanding of selected problems of current interest in the area of algorithms for database systems.
252-4102-00LSeminar on Randomized Algorithms and Probabilistic MethodsW2 credits2SA. Steger
AbstractThe 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).
ObjectiveRead papers from the forefront of today's research; learn how to give a scientific talk.
Prerequisites / NoticeThe 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-00LSeminar in Theoretical Computer Science Information W2 credits2SE. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, B. Sudakov
AbstractPresentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.
ObjectiveTo get an overview of current research in the areas covered by the involved research groups. To present results from the literature.
252-4302-00LSeminar Algorithmic Game Theory Information
Limited number of participants.
W2 credits2SP. Widmayer, P. Dütting
AbstractIn 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.
ObjectiveDevelop an understanding of selected problems of current interest in the area of algorithmic game theory, and a practice of a scientific presentation.
ContentStudy 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.
LiteratureSelected research articles.
Prerequisites / NoticeYou must have passed our "Algorithmic Game Theory" class (or have acquired equivalent knowledge, in exceptional cases).
252-4800-00LQuantum Information and Cryptography Information W2 credits3SS. Wolf
AbstractIn this advanced seminar, various topics are treated in the intersection of quantum physics, information theory, and cryptography.
Objectivesee above
263-4203-00LGeometry: Combinatorics and Algorithms Information W2 credits2SB. Gärtner, M. Hoffmann, E. Welzl
AbstractThis 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.
ObjectiveEach 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 / NoticeTo 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