# 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)