[eas_cs_seminars] 21st February 2017

[Luca Rossi]

Hi all,

This is just a reminder of next week's seminar on "Representations for
feasibly approximable functions", which will take place in MB220 from 2pm
to 3pm.

Best,
Luca

On 14 February 2017 at 19:53, Luca Rossi <l.rossi at aston.ac.uk> wrote:

> 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/>
>



-- 
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/20170220/43643e3d/attachment.html