Information-Based Complexity: Beyond the Standard Settings

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. The primary researchers involved in this project are Peter Kritzer (Austrian Academy of Sciences), and Aicke Hinrichs (Johannes Kepler University Linz). Furthermore, a PostDoc and a PhD student shall be funded by the project.