In theoretical computer science, we study information and computation.
Because these concepts are general and abstract, the field is quite diverse.
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 lab—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.