![]() |
![]() |
University of Birmingham > Talks@bham > Theoretical computer science seminar > Representations for feasibly approximable functions
Representations for feasibly approximable functionsAdd to your list(s) Download to your calendar using vCal
If you have a question about this talk, please contact Paul Taylor. This talk will be given jointly with Eike Neumann. “Exact” continuous real functions can feature as first-class objects in computation in a similar way as so-called exact real numbers. While all natural representations of continuous functions used in computable analysis are computably equivalent, different admissible representations may fail to be equivalent under the polynomial-time reduction defined by Kawamura and Cook (2012). Building on work by Labhalla, Lombardi, and Moutai (2001) and Kawamura, Mueller, Roesnick, and Ziegler (2015), we review several common admissible representations of continuous real functions, study their polynomial-time reducibility lattice and benchmark their performance using the AERN Haskell library for exact real computation. We include the canonical function space representation, in which all feasibly (= polynomial-time) computable functions are feasibly representable, but in which integration and maximisation are not feasibly computable, as shown by Ko and Friedman (1982). The other representations we study are all based on rigorous approximations by polynomials or rational functions with dyadic coefficients. In these representations maximisation and integration are feasibly computable but not all feasibly computable functions are feasibly representable. We show that the representation by piecewise-polynomial approximations is equivalent to the representation by rational function approximations with respect to polynomial-time reducibility. These two representations seem to form a sweet spot regarding the trade-off between the ability to feasibly represent a large number of functions and the ability to feasibly compute operations such as integration and maximisation. This talk is part of the Theoretical computer science seminar series. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other lists'Roles' Postgraduate Gender and Sexuality Network Discussion Type the title of a new list here Data Science and Computational Statistics SeminarOther talksTowards Efficient and Robust Data-Driven Optimization [Seminar]: Two easy three-body problems Seminar [Friday seminar]: Irradiated brown dwarfs in the desert Non-Newtonian fluid injection into an otherwise Newtonian boundary layer Signatures of structural criticality and universality in the cellular anatomy of the brain |