BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:On the Solvability Complexity Index (SCI) hierarch
y - Establishing the foundations of computational
mathematics - Anders Hansen (University of Cambri
dge)
DTSTART;TZID=Europe/London:20191126T150500
DTEND;TZID=Europe/London:20191126T160500
UID:TALK135277AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/135277
DESCRIPTION:There are four areas in computational mathematics
that have been intensely investigated over more th
an half a century: Spectral problems\, PDEs\, opti
misation and inverse problems. However\, despite t
he matureness of these fields\, the foundations ar
e far from known. Indeed\, despite almost 90 years
of quantum mechanics\, it is still unknown whethe
r it is possible to compute the spectrum of a self
-adjoint Schrodinger operator with a bounded smoot
h potential. Similarly\, it is not known which tim
e dependent Schrodinger equations can be computed
(despite well posedness of the equation). Linear p
rograms (LP) can be solved with rational inputs in
polynomial time\, but can LPs be solved with irra
tional inputs? Problems in signal and image proces
sing tend to use irrational numbers\, so what happ
ens if one plugs in the discrete cosine transform
in one'\;s favourite LP solver? Moreover\, can
one always compute the solutions to well-condition
ed infinite-dimensional inverse problems\, and if
not\, which inverse problems can then be solved?
In this talk we will discuss solutions to many of
the questions above\, and some of the results may
seem paradoxical. Indeed\, despite being an open p
roblem for more than half a century\, computing sp
ectra of \;Schrodinger operators with a bounde
d potential is not harder than computing spectra o
f infinite diagonal matrices\, the simplest of all
infinite-dimensional spectral problems. Moreover\
, computing spectra of compact operators\, for whi
ch the method has been known for decades\, is stri
ctly harder than computing spectra of such Schrodi
nger operators. Regarding linear programs (and bas
is pursuit\, semidefinite programs and LASSO) we h
ave the following. For any integer K >\; 2 and a
ny norm\, there exists a family of well conditione
d inputs containing irrational numbers so that no
algorithm can compute K correct digits of a minimi
ser\, however\, there exists an algorithm that can
compute K-1 correct digits. But any algorithm pro
ducing K-1 correct digits will need arbitrarily lo
ng time. Finally\, computing K-2 correct digits ca
n be done in polynomial time in the number of vari
ables. As we will see\, all of these problems can
be solved via the the Solvability Complexity Index
(SCI) hierarchy\, which is a theoretical program
for establishing the boundaries of what computers
can achieve in the sciences. \;
<
br>
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:INI IT
END:VEVENT
END:VCALENDAR