Information-based complexity

Information-based complexity

26.04.2015 -  02.05.2015 | Będlewo



Many important scientific and engineering problems have continuous mathematical formulations. They occur in numerous areas, including physics, chemistry, finance, economics, statistics, and all computational sciences. Such problems often lead to ordinary or partial differential equations, integral equations, stochastic differential equations, high-dimensional and path integration, nonlinear equations, and various types of optimization problems. Problems of this sort can almost never be solved analytically, but rather only approximately to within some error threshold. Computational complexity is an area of applied mathematics that studies the minimal computational resources needed for the approximate solution of such problems.

Information-based complexity (IBC), which is the theme of the conference, deals with the computational complexity of continuous problems for which available information is partial, priced, and noisy. As we study the computational complexity of such problems, we encounter many challenging research questions. It suffices to mention high-dimensional problems that occur almost everywhere. Their study has become one of the most important research areas. High-dimensional problems usually suffer from the curse of dimensionality if we consider them over spaces where all variables play the same role. A challenging problem is to find a way of structuring such problems that will allow to vanquish the curse. This exciting research area studies the tractability of such problems. IBC provides, in particular, methodological tools for proving the curse of dimensionality as well as provides various ways of vanquishing the curse of dimensionality. There are already several positive results in this direction. We believe that this is only the beginning, and that we will find many other ways to break the curse. Furthermore, we also believe that high-dimensional problems occuring in computational practice are structured so that the curse of dimensionality does not hold. This would explain why practically important high-dimensional problems can be solved with reasonable computational effort.

The conference is co-organized and partially supported by the Banach Center and Warsaw Center of Mathematics and Computer Science.