What we do

General

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)
Theoretical cryptography
Secure protocols for communication and computation, applications in computational complexity.

Discrete mathematics

Combinatorics and graph theory
Properties of combinatorial objects, Ramsey theory, applications of analytic, probabilistic, and topological methods, enumeration, ...
Structural graph theory and graph coloring
Structural properties of graphs and their algorithmic applications, graph decompositions and colorings.
Network theory
Dynamic, asymptotic and structural properties of large graphs, motivated by networks in biology, sociology, computer science, ...