Randomised Algorithms


Keywords: randomised algorithms, approximation, multimedia transmission, computer security, cryptography

Start Date: 1 July 93 / Duration: 48 months

[ participants / contact]

Objectivies and Approach

The objective is to develop efficient algorithms for various applications by using randomisation and general probabilistic constructions. The research aims at understanding the nature and the power of randomisation in making the algorithms more efficient.

The collaboration will combine the European strength in design of randomised algorithms, approximation algorithms and the foundations of randomised computation, with US strengths in the design of parallel algorithms and the new derandomisation techniques.

European links: ESPRIT BRA working group RAND (7097), Randomised Algorithms.

Progress and Results

A significant progress has been achieved in design of efficient randomised approximation algorithms for some computationally hard combinatorial and algebraic problems, in design of fast parallel algorithms and analysis of sigmoidal neural networks, as well as in proving lower bounds on randomised decision trees solving a number of long standing open problems. A study of erasure-resilient coding schemes for multimedia transmissions has also been conducted. It resulted in the first construction and the first real time implementation of such coding schemes on Sun SPARC20 workstations.

Information Dissemination Activities and/or Exploitation

The results within the project were presented at the Workshop on Randomised Algorithms and Computation, RAC'95, coorganised by International Computer Science Institute in Berkeley and the Computer Science Departement of the University of California, Berkeley, in December 1995.


University of Bonn
Dept. of Computer Science
Römerstrasse 164
D - 53117 BONN, D

EU Partners

University of Bonn, D
Lund University, S
Université Paris Sud, CNRS, F
University of Oxford, UK
University of Edinburgh, UK
University of Leeds, UK

Non-EU Partners

International Computer Science Institute, Berkeley, USA


Prof. Marek Karpinski
Tel: +49 228 73 42 24
Fax: +49 228 73 44 00
E-mail: karpinski@cs.uni-bonn.de

INCO synopses home page INCO cooperation index INCO keyword index
INCO acronym index INCO number index INCO Working Groups index
synopses home page all keywords index all acronyms index all numbers index

RAND-REC - EC-US030, May 1997

please address enquiries to the ESPRIT Information Desk

html version of synopsis by Nick Cook