Anders C. Hansen (Cambridge/Oslo): What is the Solvability Complexity Index (SCI) of your problem? - On the SCI Hierarchy and the foundations of computational mathematics

Abstract: This talk addresses some of the fundamental barriers in the theory of computations. Many computational problems can be solved as follows: a sequence of approximations is created by an algorithm, and the solution to the problem is the limit of this sequence (think about computing eigenvalues of a matrix for example). However, as we demonstrate, for several basic problems in computations such as computing spectra of operators, solutions to inverse problems, roots of polynomials using rational maps, solutions to convex optimization problems, imaging problems etc. such a procedure based on one limit is impossible. Yet, one can compute solutions to these problems, but only by using several limits. This may come as a surprise, however, this touches onto the boundaries of computational mathematics. To analyze this phenomenon we use the Solvability Complexity Index (SCI). The SCI is the smallest number of limits needed in order to compute a desired quantity. The SCI phenomenon is independent of the axiomatic setup and hence any theory aiming at establishing the foundations of computational mathematics will have to include the so called SCI Hierarchy. We will specifically discuss the vast amount of classification problems in this non-collapsing complexity/computability hierarchy that occur in inverse problems, compressed sensing problems, l1 and TV optimization problems, spectral problems, PDEs and computational mathematics in general.