Randomized and Approximate Computation (RAND-APX) Workshop


International Centre for Mathematical Sciences

Edinburgh, 17-19th September 2000


Most computational tasks that arise in realistic scenarios are intractable, at least if one insists on exact solutions delivered with certainty within a strict deadline. Nevertheless, necessity dictates that acceptable solutions of some kind must be found. Two means for circumventing the intractability barrier are randomized computation, where the answer is required to be optimal with high probability but not with certainty, and approximate computation, where the answer is guaranteed to be within, say, 5% of optimality.

The RAND-APX Thematic Network

RAND-APX ("Randomized and Approximate Computation") is a Thematic Network funded under the European IST Programme, with sites in Bonn, Edinburgh, Leeds, Lund, Oxford, Paris, and the Weizmann Institute, Rehovot. Its aim is to promote research in foundational aspects of randomised and approximate computation.

The Workshop

The RAND-APX Network will hold a workshop under the auspices of the International Centre for Mathematical Sciences (ICMS) at Edinburgh from Sunday 17th to Tuesday 19th September, 2000. The workshop will take place at the ICMS's headquarters at 14 India Street, Edinburgh, the birthplace of James Clerk Maxwell, which has been adapted to support meetings with up to about 40 participants. Although the workshop will cover all aspects of randomised and approximate computation, connections with Statistical Physics, the special theme of the meeting, will receive particular attention. The workshop will be open to non-RAND-APX members, subject to a limit on total number of participants. Invited speakers at the meeting are:

Contributed talks

Contributed talks of 30 minutes duration (including questions) are welcomed. In the case of non-RAND-APX members, acceptance of a contributed talk will be subject to sufficient time being available within the programme.


The final programme is available together with a complete list of abstracts.

How to register

Online registration is available. Stop press: In addition to the hotels listed in the "Accommodation near ICMS" list, there is also the Royal British Hotel right opposite Waverley (i.e., main) Station and airport bus terminus (and hence about 15 minutes walk to ICMS) which has a special University of Edinburgh rate of 55/night including breakfast. Just quote the secret code "University of Edinburgh". Contact me if you experience any problems obtaining the special rate.


On scientific matters, please contact

Mark Jerrum
Department of Computer Science
University of Edinburgh
The King's Buildings
United Kingdom

E-mail: mrj@dcs.ed.ac.uk
Tel: +44 131 650 5134
Fax: +44 131 667 7209

On organisational matters, please contact

14 India Street
United Kingdom

E-mail: icms@maths.ed.ac.uk
Tel: +44 (0) 131 220 1777
Fax: +44 (0) 131 220 1053
URL: http://www.ma.hw.ac.uk/icms/

Other meetings nearby

Information on Edinburgh

Information on Scotland

Information on Transport

Return to the ICMS Programme for 2000-01

Web page maintained by Mark Jerrum, mrj@dcs.ed.ac.uk