Courses
Offered every summer, in turn with T. Kaiser.
Contents
Mathematical logic takes its origin in Gottlob Frege's Begriffschrift 1879, and was pushed forward by David Hilbert's program during the so-called foundational crisis of mathematics in the beginning of the 20th century. Today it is an established disciplin of mathematics with broad connections to other areas of mathematics, and in particular to theoretical computer science. Among the greatest achievements of mathematical logic, and generally mathematics of the 20th century, are Alan Turing's formal definition of the notion of computability 1936, and Kurt Gödel's proof of impossibility of Hilbert's program, namely his incompleteness theorems 1931. The course offers an introduction into mathematical logic, and in particular into computability theory and the incompleteness theorems.
Table of contents
Evaluation
Literature
Ziegler, Mathematische Logik, Birkhäuser, 2010, Springer
Ziegler, Vorlesungsskript
Ebbinghaus, Flum, Thomas, Mathematical Logic, 1994 Springer
Ebbinghaus, Flum, Thomas, Einführung in die mathematische Logik, 2018, Springer
Shoenfield, Mathematical Logic, Addison-Wesley, 1967
Offered every winter, in turn with T. Kaiser
Contents
Model theory = logic + algebra
The course offers an introduction to classical model theory. It develops a broad general toolkit to construct and analyze theories and their models. It gives special emphasis to applications and examples, especially from algebra. It starts with a crash course in set theory and infinite cardinal numbers, and continues with the theory of Boolean algebras, ultraproducts, the back and forth method, algebraic and elementary diagrams, realizing and omitting types, quantifier elimination, applications thereof to algebraically closed and real closed fields, and finally describes theories with exactly one countable model (up to isomorphism).
Evaluation
Literatur
Chang, Keisler, Model theory, 3rd edition, North Holland, 1990.
Tent, Ziegler, A Course in Model Theory (Lecture Notes in Logic), Cambridge University Press, 2012.
Marker, Model Theory : An Introduction, Springer Graduate Texts in Mathematics 217, 2010. Here.
Contents
The course is about circuit complexity. Boolean circuits are a formal model of parallel computation: the size of a circuit models the total work done by the algorithm, the depth of a circuit models parallel time. The course has two parts. The part on upper bounds introduces some parallel algorithmics and treats, in particular, addition, multiplication, and division. We shall see that multiplication is strictly harder than addition in some precise sense in the second part on lower bounds. There we prove Andreev's fixed polynomial size lower bounds for formulas, Hastad's switching lemma and an exponential lower bound for bounded depth circuits, Razborov-Smolensky's exponential lower bound for such circuits with mod p counting gates, and Razborov's lower bound for monotone circuits. The course presupposes some elementary algebra and number theory.
Table of contents
Literature
Jukna, Boolean Function Complexity Springer
Arora, Barak, Computational Complexity: A Modern Approach,CUP, Draft
Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer
Håstad, Wegener, Wurm, Yi. Optimal depth, very small size circuit for symmetric functions in AC0. Here
A Constraint Satisfaction Problem (CSP) asks to decide whether there is an assignment to given variables, ranging over a certain domain, that satisfies a given set of constraints. Equivalently, this asks for a homomorphism between given structures. A famous example is the satisfiability problem for the Boolean domain (SAT).
The story of CSPs started 50 years ago, and during the last 25 years CSPs play a prominent role throughout computer science. On the one hand, they allow to model a wide variety of combinatorial problems (in mathematics, computer science, artificial intelligence...) in a natural and faithful way. On the other hand, they come together with general algorithmic techniques for their solution, or general reasons for their computational hardness. These techniques are based on universal algebra.
The course offers an introduction to the algebraic approach to CSPs. Knowledge of universal algebra is not assumed but developed as needed. Knowledge of mathematical logic is also not assumed. But students should have a basic knowledge of computational complexity, e.g., on the level of Theoretical Computer Science II. The lecture is accompanied by exercises. The course is conducted in English and is aimed at Master students. Details are to be found on StudIP.
Offered every winter.
Contents
Computational complexity theory aims to classify computational problems according to the algorithmic resources required for their solution. Resources are for example time, space, nondeterminism, or randomness. A central role is played by the class P of problems solvable in polynomial time. The central problem is the P versus NP problem, one of the Clay institute's millenium problems of mathematics, and, according to Smale, one of the three greatest open problems of mathematics. The course offers an introduction to this problem and its surrounding theory.
Evaluations
Literatur
Arora, Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. Draft
Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
Offered every semester.
This is an advanced seminar joint with Tobias Kaiser. It offers research talks of the respective groups and their visitors. Advanced students who wish to deepen their knowledge in mathematical logic and/or complexity theory can give talks on jointly chosen and jointly elaborated topics.
Share this page
