Representations for feasibly approximable functions

Add to your list(s) Download to your calendar using vCal

• Michal Konečný (Aston University)
• Friday 16 December 2016, 11:00-12:00
• Computer Science, The Sloman Lounge (UG).

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:

• Computer Science Departmental Series
• Computer Science Distinguished Seminars
• Computer Science, The Sloman Lounge (UG)
• Theoretical computer science seminar
• computer sience

Note that ex-directory lists are not shown.