Research

In theoretical computer science, we study information and computation. Some example topics include the following:

• Models of computation. What is computation? What are suitable models to describe computational artefacts such as modern computer hardware, the human brain, or society? How powerful are quantum computers?
• Privacy. When a social media platform publishes a supposedly anonymized data set, what kinds of information about individuals can be inferred anyway? How to release data in such a way that anonymity can be provably guaranteed?
• Efficiency. Which tasks can be computed efficiently and which cannot be? Which tasks can be solved faster than by trying out all possibilities?
• Cryptography. When establishing a supposedly secure internet connection with my bank, how sure can I be that the data transmission truly cannot be read or altered by an attacker?

The algorithmic foundations of network science are a re-occurring theme of the research conducted in the group—this is an interdisciplinary field that needs algorithmic methods to study extremely large networks, such as the Connectome, the​ Proteome, financial transaction networks, or social networks. Particular research interest present in this lab include:

• Algorithms for and the complexity of specific computational tasks, such as exactly or approximately counting subgraph patterns in large networks.
• The implementation and validation of these algorithms on real networks (algorithmic engineering, network science, and data science).
• Novel algebraic techniques in algorithms, especially algebraic graph algorithms.
• Algorithmic aspects of combinatorics, graph theory, logics, and statistical physics.
• Machine models that are suitable to analyze modern hardware capabilities (such as GPUs) or situations in which the data is enormous (such as the streaming model).
• Pseudorandomness, derandomization, and hashing techniques.
• The structure of fine-grained and parameterized complexity, and the complexity of satisfiability problems.
• Kernelization, rigorous preprocessing, and compression algorithms for computational problems.