RAND-APX Thematic Network: Edinburgh Site

RAND2 Working Group The University of Edinburgh


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.

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 randomized and approximate computation. The RAND-APX members associated with the Edinburgh site are Mary Cryan (publications), Leslie Goldberg (publications), and Mark Jerrum (publications).

Recent workshops

Forthcoming workshop

The next meeting is in Oxford, from Wednesday 10 December to Friday 12 December 2003.


Mark Jerrum
Last modified: Mon Dec 1 19:03:48 GMT 2003