Presentation
Alchemists wanted to create gold, Hilbert wanted an algorithm to solve Diophantine equations, researchers want to make deep learning robust in AI without hallucinations, MATLAB wants (but fails) to detect when it provides wrong solutions to linear programs, etc. Why do we fail in so many of these fundamental cases? The reason is typically methodological barriers. The history of science is full of methodological barriers – reasons for why we never succeed in reaching certain goals. In many cases, this is due to barriers in the foundations of mathematics. This talk introduces new such barriers from foundations: the phenomenon of generalised hardness of approximation (GHA). GHA grows out of our work on Smale’s 9th problem on the list of mathematical problems for the 21st century. This phenomenon is not a rare issue – but happens on a daily basis in computations (in particular in AI) – and causes modern software such as MATLAB to fail on basic problems, and even certify nonsensical solutions as correct.
GHA is close in spirit to hardness of approximation (HA) in computer science. Assuming P not equal to NP, HA is the phenomenon that one can easily compute an epsilon-approximation to the solution of a discrete computational problem for epsilon > epsilon_0>0, but for epsilon < epsilon_0 it suddenly becomes intractable. HA was discovered decades ago and has been transformative being the subject of several Goedel, Nevanlinna and ACM prizes. GHA is a similar but distinct mathematical phenomenon that requires a new set of mathematical tools in computation rather than computer science (NB: GHA is independent of P vs. NP). The GHA grows out of the Solvability Complexity Index (SCI) hierarchy framework, and has so far been detected in optimisation, inverse problems, deep learning and AI, as well as computer-assisted proofs. We will discuss in particular the connections to AI.
Speaker
Anders C. Hansen is a member of the Department of Applied Mathematics and Theoretical Physics at University of Cambridge, and head of the Applied Functional and Harmonic Analysis research group. His current research interests include but are not limited to Functional Analysis (applied), operator/ Spectral Theory, Compressed Sensing, Mathematical Signal Processing, Sampling Theory, Compressed Sensing, Mathematical Signal Processing, Sampling Theory, Computational Harmonic Analysis, Inverse problems, Medical Imaging, Geometric Intergration, Numerical Analysis, C*- algebras.
Program
11:45 – Doors open and lunch is served
12:00 – "On Smale’s 9th problem, generalised hardness of approximation and the limits of AI" by Anders C. Hansen (Professor, Faculty of Mathematics, University of Cambridge)
13:00 – Mingling (and goodbye)
To participate, please fill out the registration form. This way, we will not be short on food and drinks! (Registration is not binding and you are welcome to join us anyway!)
About the seminar series
Once a month, dScience will invite you to join us for lunch and professional talks at the Science Library. In addition to these, we will serve lunch in our lounge in Kristine Bonnevies house every Thursday. Due to limited space (40 people), this will be first come, first served. See how to find us here.
Our lounge can also be booked by PhDs and Postdocs on a regular basis, whether it is for a meeting or just to hang out – we have fresh coffee all day long!