[eas_cs_seminars] 21st February 2017

[Luca Rossi]

Dear all,

Next Tuesday (21/02) our CS seminar series will see Eike Neumann (Aston
University) giving a talk on "Representations for feasibly approximable
functions" in MB220 from 2pm to 3pm.

I'm forwarding this email to the Math staff as well as I believe it could
be of interest for many of you (see abstract below).

Best,
Luca

Abstract:

Given a continuous real function, two of the most basic computational tasks
are the computation of its integral and its range. Both problems are
generally perceived to be ``easy'' by practitioners (given that the domain
is one-dimensional). Hence it was surprising when Ko and Friedman in 1982
proved that these problems are #P-hard and NP-hard, respectively.

Our hypothesis is that this discrepancy is due to the fact that complexity
theorists use the simplest natural representation of continuous real
functions, which treats all polytime computable functions equally.
Practitioners, on the other hand, use representations which are biased
towards a small class of functions that typically occur in practice. We
evaluate this hypothesis using both theoretical and practical tools.

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 standard continuous function representation used in
computational complexity theory where all polytime computable functions are
polytime representable.

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 polytime computable functions are polytime 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.

-- 
Luca Rossi

Lecturer in Computer Science
School of Engineering and Applied Science
Aston University
Web: http://www.cs.aston.ac.uk/~rossil/ <http://www.cs.bham.ac.uk/~rossil/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.aston.ac.uk/pipermail/eas_cs_seminars/attachments/20170214/6296e656/attachment.html