RAND-APX Thematic Network

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.

RANDOMISED AND APPROXIMATE COMPUTATION

Workshop held in Mathematical Institute, Oxford from Wednesday 10 December to Friday 12 December 2003