Funding: FWF
Funding period: Sep 2021 - Aug 2025
Project number: P34808


  • Peter Kritzer (PI, project leader, RICAM, since Sep 2021)
  • Aicke Hinrichs (PI, national research partner, JKU, since Sep 2021)
  • Mathias Sonnleitner (PhD student, JKU, since Sep 2021)


The topic of the project is in the field of Information-Based Complexity (IBC), which is a sub-field of mathematics concerned with the following questions: if a mathematical problem depends on a large number of variables, how much information about the problem is required to solve it approximately, but not exceeding a certain error threshold? How does the amount of required information change if the number of variables and/or the error threshold change?

To quantify the dependence of a problem on the number of variables and the error threshold, this can be done by using a concept called tractability, and studying the tractability of various computational problems is among the core questions of IBC. Various notions of tractability, quantifying the dependence on the number of variables and the threshold, exist in the literature.

This project is devoted to the study of IBC, and, in particular tractability, in frameworks that have so far not been studied extensively. Doing so, we hope to push the boundaries of the research field further, and to make make the theory more useful for applications. To give an example, we plan to consider problems where we allow the number of variables to be unbounded, which is an additional challenge in comparison to the standard settings. This and all other problems that shall be dealt with in the course of the project are motivated by recent publications of experts in the field of IBC.



Here, we will list information on publications written in the course of this project.


  • M. Sonnleitner. Random sections of p-ellipsoids and optimal recovery. Austrian Stochastics Days. Sep. 10, 2021. Leoben, Austria.