Tractability of high dimensional problems and discrepancy, September 11 - October 13, 2017, ESI Vienna
Sprache des Titels:
Many important scientific and engineering problems have continuous mathematical formulations. These problems can almost never be solved analytically, but rather only approximately to within some error threshold. Computational complexity is an area of applied mathematics and theoretical computer science that studies the minimal computational resources needed for the approximate solution of such problems. Often the resource of interest is time. The minimal computational time can be measured in different settings and for different error criteria.
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 us to vanquish the curse. This exciting research area studies the tractability of such problems.
Discrepancy theory is directly related to the quality of quasi-Monte Carlo methods for the approximation of integrals. It deals with the problem of distributing points as uniformly as possible and estimating the inevitable errors from approximating a continuous distribution by a discrete one. Naturally, discrepancy is intimately related to tractability studies. Although the classical theory has already answered many questions for low dimensional problems, the high dimensional situation is not well understood and many challenging fundamental problems still need to be studied