<div dir="ltr">Dear all,<div><br></div><div>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.</div><div><br></div><div>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).</div><div><br></div><div>Best,</div><div>Luca</div><div><br></div><div>Abstract:</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>We include the standard continuous function representation used in computational complexity theory where all polytime computable functions are polytime representable.</div><div><br></div><div>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.</div><div><br></div><div>We show that the representation by piecewise-polynomial approximations is equivalent to the representation by rational function approximations with respect to polynomial-time reducibility.</div><div><br></div><div>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.<br></div><div><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr">Luca Rossi</div><div dir="ltr"><br></div><div dir="ltr">Lecturer in Computer Science</div><div dir="ltr">School of Engineering and Applied Science</div><div dir="ltr">Aston University</div><div dir="ltr">Web: <a href="http://www.cs.bham.ac.uk/~rossil/" target="_blank">http://www.cs.aston.ac.uk/~rossil/</a></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</div></div>