Search result: Catalogue data in Autumn Semester 2023
Cyber Security Master  | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 Minor | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Theoretical Computer Science | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Elective Courses | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Number | Title | Type | ECTS | Hours | Lecturers | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 227-0417-00L | Information Theory I | W | 6 credits | 4G | A. Lapidoth | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Abstract | This course covers the basic concepts of information theory and of communication theory. Topics covered include the entropy rate of a source, mutual information, typical sequences, the asymptotic equi-partition property, Huffman coding, channel capacity, the channel coding theorem, the source-channel separation theorem, and feedback capacity. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Learning objective | The fundamentals of Information Theory including Shannon's source coding and channel coding theorems | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Content | The entropy rate of a source, Typical sequences, the asymptotic equi-partition property, the source coding theorem, Huffman coding, Arithmetic coding, channel capacity, the channel coding theorem, the source-channel separation theorem, feedback capacity | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Literature | T.M. Cover and J. Thomas, Elements of Information Theory (second edition) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 263-5300-00L | Guarantees for Machine Learning  | W | 7 credits | 3V + 1U + 2A | F. Yang | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Abstract | This course is aimed at advanced master and doctorate students who want to conduct independent research on theory for modern machine learning (ML). It teaches standard methods in statistical learning theory commonly used to prove theoretical guarantees for ML algorithms. The knowledge is then applied in independent project work to understand and follow-up on recent theoretical ML results. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Learning objective | By the end of the semester students should be able to - understand a good fraction of theory papers published in the typical ML venues. For this purpose, students will learn common mathematical techniques from statistical learning in the first part of the course and apply this knowledge in the project work - critically examine recently published work in terms of relevance and find impactful (novel) research problems. This will be an integral part of the project work and involves experimental as well as theoretical questions - outline a possible approach to prove a conjectured theorem by e.g. reducing to more solvable subproblems. This will be practiced in in-person exercises, homeworks and potentially in the final project - effectively communicate and present the problem motivation, new insights and results to a technical audience. This will be primarily learned via the final presentation and report as well as during peer-grading of peer talks. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Content | This course touches upon foundational methods in statistical learning theory aimed at proving theoretical guarantees for machine learning algorithms. It touches on the following topics - concentration bounds - uniform convergence and empirical process theory - regularization for non-parametric statistics (e.g. in RKHS, neural networks) - high-dimensional learning - computational and statistical learnability (information-theoretic, PAC, SQ) - overparameterized models, implicit bias and regularization The project work focuses on current theoretical ML research that aims to understand modern phenomena in machine learning, including but not limited to - how overparameterized models generalize (statistically) and converge (computationally) - complexity measures and approximation theoretic properties of randomly initialized and trained neural networks - generalization of robust learning (adversarial or distribution-shift robustness) - private and fair learning | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Prerequisites / Notice | Students should have a very strong mathematical background (real analysis, probability theory, linear algebra) and solid knowledge of core concepts in machine learning taught in courses such as “Introduction to Machine Learning”, “Regression”/ “Statistical Modelling”. In addition to these prerequisites, this class requires a high degree of mathematical maturity—including abstract thinking and the ability to understand and write proofs. Students have usually taken a subset of Fundamentals of Mathematical Statistics, Probabilistic AI, Neural Network Theory, Optimization for Data Science, Advanced ML, Statistical Learning Theory, Probability Theory (D-MATH) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Competencies |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 401-3055-64L | Algebraic Methods in Combinatorics | W | 5 credits | 2V + 1U | L. Gishboliner | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Abstract | Combinatorics is a fundamental mathematical discipline as well as an essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. This course provides a gentle introduction to Algebraic methods, illustrated by examples and focusing on basic ideas and connections to other areas. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Learning objective | The students will get an overview of various algebraic methods for solving combinatorial problems. We expect them to understand the proof techniques and to use them autonomously on related problems. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Content | Combinatorics is a fundamental mathematical discipline as well as an essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. While in the past many of the basic combinatorial results were obtained mainly by ingenuity and detailed reasoning, the modern theory has grown out of this early stage and often relies on deep, well-developed tools. One of the main general techniques that played a crucial role in the development of Combinatorics was the application of algebraic methods. The most fruitful such tool is the dimension argument. Roughly speaking, the method can be described as follows. In order to bound the cardinality of of a discrete structure A one maps its elements to vectors in a linear space, and shows that the set A is mapped to linearly independent vectors. It then follows that the cardinality of A is bounded by the dimension of the corresponding linear space. This simple idea is surprisingly powerful and has many famous applications. This course provides a gentle introduction to Algebraic methods, illustrated by examples and focusing on basic ideas and connections to other areas. The topics covered in the class will include (but are not limited to): Basic dimension arguments, Spaces of polynomials and tensor product methods, Eigenvalues of graphs and their application, the Combinatorial Nullstellensatz and the Chevalley-Warning theorem. Applications such as: Solution of Kakeya problem in finite fields, counterexample to Borsuk's conjecture, chromatic number of the unit distance graph of Euclidean space, explicit constructions of Ramsey graphs and many others. The course website can be found at https://moodle-app2.let.ethz.ch/course/view.php?id=15757 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lecture notes | Lectures will be on the blackboard only, but there will be a set of typeset lecture notes which follow the class closely. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Prerequisites / Notice | Students are expected to have a mathematical background and should be able to write rigorous proofs. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 401-3901-00L | Linear & Combinatorial Optimization | W | 10 credits | 4V + 2U | R. Zenklusen | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Abstract | Mathematical treatment of optimization techniques for linear and combinatorial optimization problems. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Learning objective | The goal of this course is to get a thorough understanding of various classical mathematical optimization techniques for linear and combinatorial optimization problems, 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 such structural insights. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Content | Key topics include: - Linear programming and polyhedra; - Flows and cuts; - Combinatorial optimization problems and polyhedral techniques; - Equivalence between optimization and separation. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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. Former course title: Mathematical Optimization. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Competencies |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 402-0448-01L | Quantum Information Processing I: Concepts This theory part QIP I together with the experimental part 402-0448-02L QIP II (both offered in the autumn semester) combine to the core course in experimental physics "Quantum Information Processing" (totally 10 ECTS credits). This applies to the Master's degree programme in Physics. | W | 5 credits | 2V + 1U | J. Renes | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Abstract | The course covers the key concepts and formalism of quantum information processing. Topics include quantum algorithms, quantum error correction, quantum cryptography, and quantum metrology, with an emphasis on the power of quantum information processing beyond that of classical information processing. The formalism of quantum states, measurements, and channels is developed in detail. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Learning objective | By the end of the course students are able to explain the basic mathematical formalism of quantum mechanics and apply it to quantum information processing problems. They are able to adapt and apply these concepts and methods to analyze and discuss quantum algorithms and other quantum information-processing protocols. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Content | The topics covered in the course will include quantum circuits, gate decomposition and universal sets of gates, efficiency of quantum circuits, quantum algorithms (Shor, Grover, Deutsch-Josza,..), stabilizer-based quantum error correction, fault-tolerant designs, the BB84 quantum key distribution protocol, and simple methods of quantum metrology. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lecture notes | Will be provided. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Literature | Quantum Computation and Quantum Information Michael Nielsen and Isaac Chuang Cambridge University Press | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Prerequisites / Notice | A good understanding of finite dimensional linear algebra is recommended. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Competencies |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Page
1
of
1
