IUBio

Workshop on Complexity and Exact Computation over the reals

John Shawe-Taylor john at dcs.rhbnc.ac.uk
Fri May 14 05:56:33 EST 1999



         COMPLEXITY AND EXACT COMPUTATION OVER THE REAL NUMBERS
                             10 - 12 July 1999
                    Royal Holloway, University of London
                            Egham, Surrey, UK

A three day workshop, jointly sponsored by the EPSRC and the LMS under
the MathFit Programme, will be hosted by the Department of Computer
Science at Royal Holloway, University of London. The workshop is
particularly aimed at PhD students who would like to know more about
the subject, although any interested participants are welcome.
Registration and accommodation are FREE for EPSRC-funded students and
LMS support is also available for other research students.

                                 Background

Computations involving real numbers are handled in microprocessors, in
calculators, in programming languages, and in numerical software by
approximation, whether it be fixed precision or, as in some numerical
software, arbitrary precision. Such calculations are based upon binary
or decimal representations of numbers. Over the last 25 years or so, an
alternative approach to real computation has been developed, called
exact real computation in which results are generated exactly, without
approximation. Systems for exact real computation have been built based
upon alternative representations of real numbers, especially continued
fractions.  However, although such systems have been around for a while
they have often been viewed as a curiosity, and mainly of research
interest. However, the state of the art, as developed at several sites
around the world is moving towards exact systems which could be used to
replace the traditional approximate systems. Indeed various industrial
organisations are showing interest in using such systems in numerical
and simulation software, as well as in Computer Algebra Systems.

However, for exact systems to be fully developed there are several
remaining areas to be understood and implemented. Traditionally, such
systems have focussed on arithmetic. Extending exact computation to
differential and integral calculus, and to solutions of differential
equations, requires new techniques, including an understanding of the
semantics of such systems and also the notions of constructivity
involved and the relevant logics and algebraic framework. A quite
different aspect is that of efficiency of exact systems. To what extent
can they match the present numerical systems in terms of performance?
This is not an easy question. There is efficiency in the demand-driven
nature of exact systems, but most implementations are orders of
magnitude slower than inexact systems. Moreover, there is a question
whether efficient methods from numerical analysis, such as adaptive
methods, can be used to provide a reasonable performance for exact
calculus.  A great deal of expertise about efficiency of implementation
of exact systems has been developed but no systematic understanding of
the area has yet emerged.

Recently, however, there has been an explosive growth in the study of
the complexity (ie measures of efficiency) of computation involving
real numbers. Complexity traditionally has been used to count numbers
of operations in algorithms that are mainly of a combinatorial nature.
Generalising complexity theory to computations involving real numbers
has been a relatively recent development, in which many of the standard
complexity theory concepts take on a very different flavour. We will
give four examples of the types of problems considered:

   * Characterize the power of real machines over binary inputs. This is
     closely related to the study of the power of analog neural nets.
   * Characterize the power of randomization.
   * Characterize the complexity of specific computational problems.
   * Characterize complexity classes by means of logic.
   * Prove the equivalence of different models of continuous computation, in
     order to strengthen the ``Church-Turing thesis for continuous computation''.

By bringing together those interested in either of these two fields,
the workshop will enable participants to learn sufficient about each
other's fields to make progress in developing systematic approaches to
the efficiency of exact computation, and also to bring to those working
in real complexity some of the practical issues involving the
efficiency of exact computation. The workshop will function mainly as a
tutorial on both topics, together with discussions in which
interactions between the two topics will be developed.

Invited Speakers
----------------

Real valued complexity:
Professor Pascal Koiran, ENS Lyon
Machines over the Reals - Exact and round-off computations - Basics in
complexity (NP-completeness) - Condition numbers in perturbation, round-off,
and complexity

Professor Felipe Cucker, Universitat Pompeu Fabra, Barcelona
Randomized algorithms - Complexity of geometric problems (dimensions of
algebraic varieties and semi-algebraic sets) - Transfer theorems for the
"P = NP?" problem.

Exact real computation:
Dr David Lester, Department of Computer Science, University of Manchester
Implementation of exact real computation - Constructive real analysis -
Functional languages

Professor Klaus Weihrauch, FernUniversitt Hagen, Germany
Exact Real Computation and Real Complexity


                      Location, Accommodation and Cost

Royal Holloway, University of London, UK (with its famous, ornate
Victorian Building) is easily accessible from London, the M25, and
Heathrow Airport.  En-suite accommodation in single study bedrooms is
provided in our newest hall of residence on campus, and all
refreshments and meals, from lunch on Saturday to lunch on Monday,
including a Dinner in the famous Picture Gallery, are included in the
price of 120 pounds per person. Non-residential attendance will cost 52
pounds per person.

                                 Programme

The Workshop starts at midday on Saturday 10 July and closes mid
afternoon on Monday 12 July. The material will be presented in a series
of one-hour sessions, and the two tracks will run through the period of
the workshop.  Participants will also be able to access one or more
implementations of exact real arithmetic, with support provided in a
practical session.

                            Organising Committee

   * David Rydeheard david at cs.man.ac.uk
   * Simon Thompson S.J.Thompson at ukc.ac.uk
   * John Shawe-Taylor jst at dcs.rhbnc.ac.uk

The organisers wish to thank the Engineering and Physical Sciences
Research Council and the London Mathematical Society for their
financial support, particularly in assisting research students to
participate in the Workshop.

                        Support for Research Students

EPSRC and LMS have agreed to provide support for  EPSRC-funded research
students and other research students - available on a first come, first
served basis - so contact us now to check your eligibility and secure
your place. If you are a research student who wishes to take advantage
of this, or a supervisor wishing to apply on behalf of a research
student please contact the registration secretary (address below, or
from webpage application).

                             Registration

For more details and on-line registration forms, see the webpage:

http://www.cs.rhbnc.ac.uk/events/realwork/index.shtml

To book a place at the Workshop please fill out the registration form,
send
e-mail to J.Hales at dcs.rhbnc.ac.uk or fax to +44-1784-439786 (Janet Hales)

Royal Holloway, University of London
Department of Computer Science
www at dcs.rhbnc.ac.uk

Janet Hales
Departmental Events Co-ordinator
Dept of Computer Science, Royal Holloway, University of London
Tel +44 1784 443432
Fax +44 1784 439786
Email J.Hales at dcs.rhbnc.ac.uk



---



More information about the Neur-sci mailing list

Send comments to us at biosci-help [At] net.bio.net