Conference abstracts

Session C5 - Information-Based Complexity

July 17, 18:30 ~ 18:55 - Room T1

Computing the non-computable - On fundamental barriers in computational mathematics

Anders Hansen

University of Cambridge, United Kingdom   -   ach70@cam.ac.uk

In the beginning of the 20th century Hilbert asked abut the existence of algorithms for decision problems, which sparked the birth of modern theoretical computer science. Similarly, in the 1980s, Smale asked about the existence of algorithms for problems in scientific computing, such as polynomial root finding. This led to a comprehensive program on the foundations of computational mathematics. Questions a la Hilbert and Smale, regarding the existence of algorithms, can be asked in any area of computational mathematics. As we show in this talk, possibly surprisingly, the answer is often negative in many contemporary fields such as compressed sensing, statistical estimation, image processing, machine learning, deep neural networks, computer aided proofs, computational quantum mechanics etc. The non-existence of algorithms for many of these problems may seem like a great paradox given that they are used successfully in so many applications. In this talk we will discuss how these paradoxes yield a very rich classification theory in the foundations of computational mathematics. This is done through the Solvability Complexity Index (SCI) hierarchy. By using the SCI hierarchy one can show how many core problems are formally non-computable yet explain why they are computed efficiently on a daily basis. Moreover, this allows for a complexity theory for the many non-computable problems in the applications mentioned above. In particular, the new results show that theories such as Information Based Complexity (IBC) can be applied in a much wider context than traditionally used.

Joint work with Alex Bastounis (University of Cambridge), Matt Colbrooke (University of Cambridge) and Verner Vlacic (University of Cambridge).

View abstract PDF



FoCM 2017, based on a nodethirtythree design.