BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Theoretical computer science seminar
SUMMARY:Representations for feasibly approximable function
s - Michal Konečný (Aston University)
DTSTART:20161216T110000Z
DTEND:20161216T120000Z
UID:TALK2330AT
URL:/talk/index/2330
DESCRIPTION:This talk will be given jointly with Eike Neumann.
\n\n"Exact" continuous real functions can feature
as \nfirst-class objects in computation in a simil
ar way \nas so-called exact real numbers.\n\nWhile
all natural representations of continuous functio
ns \nused in computable analysis are computably eq
uivalent\, \ndifferent admissible representations
may fail to be \nequivalent under the polynomial-t
ime reduction \ndefined by Kawamura and Cook (2012
).\n\nBuilding on work by Labhalla\, Lombardi\, an
d Moutai (2001) \nand Kawamura\, Mueller\, Roesnic
k\, and Ziegler (2015)\, \nwe review several commo
n admissible representations\nof continuous real f
unctions\, study their polynomial-time \nreducibil
ity lattice and benchmark their performance\nusing
the AERN Haskell library for exact real computati
on.\n\nWe include the canonical function space rep
resentation\, \nin which all feasibly (= polynomia
l-time) computable \nfunctions are feasibly repres
entable\, but in which \nintegration and maximisat
ion are not feasibly computable\, \nas shown by Ko
and Friedman (1982).\n\nThe other representations
we study are all based on \nrigorous approximatio
ns by polynomials or rational \nfunctions with dya
dic coefficients. \nIn these representations maxim
isation and integration \nare feasibly computable
but not all feasibly computable\nfunctions are fea
sibly representable.\nWe show that the representat
ion by piecewise-polynomial \napproximations is eq
uivalent to the representation by \nrational funct
ion approximations with respect\nto polynomial-tim
e reducibility.\n\nThese two representations seem
to form a sweet spot \nregarding the trade-off bet
ween the ability to\nfeasibly represent a large nu
mber of functions and \nthe ability to feasibly co
mpute operations\nsuch as integration and maximisa
tion.\n
LOCATION:Computer Science\, The Sloman Lounge (UG)
CONTACT:Paul Taylor
END:VEVENT
END:VCALENDAR