3:00–4:00 pm
To receive the event link and other details, please sign up to receive colloquia emails from the department here.
The Extended Smale's 9th problem — On hardness of approximation in computation and non-computable problems in computer-assist
Abstract:
In the list of problems for the 21st century S. Smale calls for extended '[Computational] models which process approximate inputs'. In addition, Smale's 9th problem asks for an algorithm over the reals that decides feasibility and produces a minimiser of linear programs (LPs) in polynomial time (or strongly polynomial time in the Turing case). The extended model — in combination with Smale's 9th problem — yields an extended version of Smale's 9th problem for which we show several surprises:
(1) Given the extended model, for any eps_0 > 0 there is a class of LPs such that no algorithm can compute an epsilon-approximation to a minimiser (even in the randomised case) if epsilon < eps_0. However, computing an epsilon-approximation is in P (computable in polynomial time in the number of variables) if epsilon > eps_0. This result is independent of the P vs NP question unlike the typical hardness of approximation phenomenon in computer science.
(2) Hence, the extended Smale's 9th problem leads to new type of hardness of approximation results not previously known. Moreover, similar behaviour occurs in statistical estimation with the Lasso and in sparse regularisation with Basis Pursuit. Thus, one computes with non-computable functions on a daily basis.
(3) The extended Smale's 9th problem demonstrates how the proof of Kepler's conjecture by T. Hales was done based on successfully computing with non-computable problems. This phenomenon is not exclusive and happens also in the proof of the Dirac-Schwinger conjecture of C. Fefferman and L. Seco.
The above results demonstrate — paradoxically — the need for a complexity theory for non-computable functions. We will discuss this issue and the implications in mathematics, computations and computer-assisted proofs.
