An advanced course in graph theory and combinatorics. Includes topics from:

• structural graph theory (properties of graph classes defined by forbidden minors, detailed introduction to treewidth from the structural perspective, Erdős-Pósa theorem, Nash-Williams theorem on spanning trees, VC dimension)
• extremal graph theory and additive combinatorics (regularity lemma and its applications)
• polynomial method (in list coloring and graph regularization)

Cílem semináře je dát dohromady studenty a vyučující, které zajímá, nebo by mohla zajímat teorii kooperativní her. Slouží především jako platforma pro vznik nových témat a formulaci zajímavých problémů, které následně diskutujeme a řešíme. Seminář je směřovaný tím, co jeho účastníky baví a zajímá. Chceme vybudovat kolektiv a propojit mezi sebou lidi, kteří mohou spolupracovat i nad rámec samotného semináře. Studenti si mohou také prostřednictvím semináře vyzkoušet, co obnáší výzkum v matematice, otestovat své schopnosti a na základě této zkušenosti na seminář i navázat prostřednictvím bakalářské/magisterské práce.

The lecture covers advanced algorithms for shortest paths, network flows, minimum spanning trees, and some other graph problems. Several graph data structures will be mentioned, too. Knowledge of Bachelor-level Algorithms and Data Structures 1+2 is assumed.

The basic course in extremal graph theory, introducing the fundamental concepts (extremal function, stability), constructions (Turán's graph, algebraic constructions), and techniques used to show that sufficiently dense graphs must contain the specified configurations. We focus on giving an overview of the foundational results on the edge-density extremal function when various natural types of graphs (cliques, cycles, graphs of bounded degeneracy, ...) are forbidden, using this as an opportunity to introduce several more advanced methods that are generally useful (dependent random choice, regularity lemma, the method of flag algebras, ...) not just in the extremal combinatorics.

Parameterized algorithmics analyzes the runtime in finer detail than classical complexity theory: instead of expressing the runtime as a function of the input size only, the dependence on a parameter of the input is taken into account. The aim is to isolate any fast growth of the runtime to a parameter, while the remaining growth of the time is kept low. Apart from giving a deeper theoretical understanding of the complexity of a problem, this can also lead to efficient (practical) algorithms if the parameter describes a property of the inputs, for which the parameter is typically small.

See also video trailer.

We will show several (sometimes rather unexpected) applications of linear algebraical methods in combinatorics and graph theory. As a sample for tasting: Can you describe all graphs with the property that any two different vertices have exactly one common neighbor?

Games have long served as benchmarks and marked milestones of progress in artificial intelligence (AI). This course teaches you fundamental formalisms, solution concepts and algorithms. We show how to solve both perfect and imperfect information games, and you will understand the deep connections and application of reinforcement learning to game theory. At the end of the course, you will implement algorithms to optimally solve (i.e. converge to Nash Equilibria) in small interesting games - notably small poker variants.

We will discuss advanced topics of code generation. While the lecture freely continues from previous semester, it can be made independent of it.

This semester, selected chapters from combinatorics will focus on Steiner systems and block schemes.

The content of this course are advanced topics in computational complexity. This semester will be devoted to fine-grained complexity. Fine-grained complexity is a field that has emerged and developed remarkably over the last fifteen years. It tries to answer the question why the best known algorithms, for example, for finding the longest common subsequence, have quadratic time complexity, while for other problems all known algorithms have cubic complexity. This is related to exponential time algorithms for satisfiability (SAT).

A series of lectures on advanced data structures, which extends Master-level Data structures 1 and 2. You can take this course repeatedly, we tackle different topics each year.

Training for programming competitions, especially International Collegiate Programming Contest (ICPC). Practice contests and tutorials on important techniques and problem types. Held once every two weeks for 3 hours.

The students will collaborate on solving open combinatorial problems, which are easily formulated and do not require deep background knowledge. We attempt to choose problems of medium difficulty.

Also known as the pizza seminar. Come enjoy a slice of pizza and a talk on current topics in theoretical computer science.

The Complex Networks Applications seminar covers selected modern topics in complex networks. The principle of the seminar is to introduce several topics and let the students work on them. We first give a short introduction to the topic and present several topics from which students can choose. The topics include both theoretical and programming problems.

The history of Forcing in bounded arithmetic and proof complexity goes back to 1985 paper of Paris and Wilkie. Subsequently, Ajtai's 1988 lower bound for bounded depth Frege was originally obtained by a forcing argument and is still considered as one of the most important ones in the area. These results motivated further research into forcing in the context of bounded arithmetic. This semester, we will be covering Forcing with random variables in Proof Complexity (Krajíček 2011). In this setting, the constructed models are Boolean-valued and their behaviour is parametrized by random variables computed by some class of functions of fixed computational complexity.