What we do
General
Seminars for students
Seminars where students present and discuss interesting papers and solve open problems.
Computer science
Computational complexity
Lower bounds on the complexity in various models of computation, communication complexity.
- EPAC: Efficient approximation algorithms and circuit complexity (EXPRO project)
- Monotone computations and proof complexity (student GAUK project)
- LBCAD: Lower bounds for combinatorial algorithms and dynamic problems (past ERC project)
- Computational complexity and interactive protocols
- Nonuniform computational models
- Selected Topics in Computational Complexity I
- Selected Topics in Computational Complexity II
- Introduction to Information Transmission and Processing
- Constructions of Bounded-depth Superconcentrators (bachelor's thesis)
- Pseudorandom walks and chip firing games (master's thesis)
- New Bounds for Combinatorial Problems and Quasi-Gray Codes (dissertation thesis)
Design and analysis of algorithms
Exact, approximation, on-line, parameterized, ...
- EPAC: Efficient approximation algorithms and circuit complexity (EXPRO project)
- Introduction to Approximation and Randomized Algorithms
- Approximation and Online Algorithms
- Randomized Algorithms
- Selected Topics in Algorithms
- Selected Topics in Algorithms II
- Combinatorial Algorithms for Flow Problems (bachelor's thesis)
- Online scheduling of multiprocessor jobs with preemption (master's thesis)
- Online Algorithms for Packet Scheduling (dissertation thesis)
Theoretical cryptography
Secure protocols for communication and computation, applications in computational complexity.
- Modern applications of zero-knowledge protocols (bachelor's thesis)
- On search complexity of discrete logarithm (master's thesis)
- On the Complexity of Search Problems with a Unique Solution (dissertation thesis)
Discrete mathematics
Combinatorics and graph theory
Properties of combinatorial objects, Ramsey theory, applications of analytic, probabilistic, and topological methods, enumeration, ...
- CoSP: Combinatorial Structures and Processes (RISE project)
- Computational aspects and structure of graph homomorphisms (student GAUK project)
- Selected Chapters on Combinatorics 1
- Selected Chapters on Combinatorics 2
- Combinatorics and Graph Theory 3
- Combinatorial game theory
- Analytic combinatorics
- Introduction to extremal graph theory
- Probabilistic Techniques
- Probabilistic Techniques 2
- Structure and enumeration of permutation classes (bachelor's thesis)
- Algorithmic aspects of intersection representations (bachelor's thesis)
- Intersection representations of graphs (master's thesis)
- The complexity of constrained graph drawing (master's thesis)
- Structure and complexity of homomorphisms (dissertation thesis)
Structural graph theory and graph coloring
Structural properties of graphs and their algorithmic applications, graph decompositions and colorings.
- ACoBE: Algorithms and Complexity within and beyond Bounded Expansion (ERC-CZ project)
- Ramsey-like aspects of graph coloring (past GAČR project)
- Topics in Structural Graph Theory and Algorithms
- Matroid Theory
- Graph minor theory
- Flows and Cycles in Graphs
- Coloring of Graphs and Other Combinatorial Structures
- Number of faces in a random embedding of a complete graph (bachelor's thesis)
- Variants of Petersen coloring for some graph classes (master's thesis)
- Structural aspects of graph coloring (dissertation thesis)
Network theory
Dynamic, asymptotic and structural properties of large graphs, motivated by networks in biology, sociology, computer science, ...
- DYNASNET: Dynamics and Structure of Networks (ERC project)
- Modular tool for parametric analysis of dynamical systems using complex networks (bachelor's thesis)
- Properties of network centralities (master's thesis)
- Combinatorial properties of complex networks (dissertation thesis)