Research group Theory of complex systems

News
[HTML, ICAL]

Main Focus

The "Theory of Complex Systems" group focuses on theoretical computer science, with an emphasis on complexity theory, logic, and database theory. Paticular attention is put on the relations between these areas. For example, logics serve as a basis for database query languages and specification languages used for automatic verification; and many aspects of complex systems can be modeled by logical structures, so that properties of complex systems can be specified by logical formulas.

The overall aim of the TKS group is to gain a better understanding of the complexity inherent in a problem or a system. Here, we are interested in various measures of complexity, including the computational complexity (question: How difficult is it to algorithmically solve the problem?) and the descriptive complexity (Question: How difficult is it to describe the problem in a suitable formalism?). Particular attention is paid to the connection between logical descriptions of problems and efficient algorithmic solutions.

One focus of the TKS group is the expressive power and the complexity of various logics. Another focus is the complexity of processing massive data sets and data streams. Here we are particularly interested in designing and analysing computation models suitable for classifying the resources necessary for processing massive data sets and data streams. We aim at developing efficient data stream algorithms as well as proving lower bounds on the costs produced by external memory accesses that are inherently necessary for solving certain problems.