[ University of Bonn | Department of Computer Science | Chair V | deutsche Version ]

RAND logo


Dept. of
Computer Science
University of
53117 Bonn

Preprint Series



RAND-APX (IST-1999-14036)

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, small percentage of optimality.

RAND-APX ("Randomized and Approximate Computation") is a Themat 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.

Partner List

(with local RAND-APX web pages)
Contact Email
University of Bonn Marek Karpinski marek@cs.uni-bonn.de
University of Edinburgh Mark Jerrum mrj@dcs.ed.ac.uk
University of Leeds Martin Dyer dyer@scs.leeds.ac.uk
Lund University Andrzej Lingas Andrzej.Lingas@dna.lth.se
Oxford University Dominic Welsh dwelsh@maths.ox.ac.uk
Université de Paris-Sud Miklos Santha Miklos.Santha@lri.fr
Weizmann Institute, Rehovot Moni Naor naor@wisdom.weizmann.ac.il

Last updated: February 05st, 2001.
Maintained by: