Keywords: randomised algorithms, approximation, multimedia transmission, computer security, cryptography
Start Date: 1 July 93 / Duration: 48 months
[ participants / contact]
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.
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.
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
D - 53117 BONN, D
University of Bonn, D
Lund University, S
Université Paris Sud, CNRS, F
University of Oxford, UK
University of Edinburgh, UK
University of Leeds, UK
International Computer Science Institute, Berkeley, USA
Prof. Marek Karpinski
Tel: +49 228 73 42 24
Fax: +49 228 73 44 00
RAND-REC - EC-US030, May 1997
please address enquiries to the ESPRIT Information Desk
html version of synopsis by Nick Cook