[ University of Bonn | CS Department | Chair V | deutsche Version ]

ESPRIT BR Working Group RAND

Bonn Workshop On Randomized Algorithms (RAND)

The workshop was organized by ESPRIT BR Working Group on Randomized Algorithms (RAND), and the Department of Computer Science of the University of Bonn. It was concerned with the newest development in the design of efficient an pseudo-randomized algorithms, approxomation algorithms, circuit design, probabilistic methods and the constructions of small sampling spaces as well as with the foundations of complexity theory of randomized computation.

For more information see our research report (8590-CS).

Annual Progress Report 1992/1993

The research was conducted in all the main research areas of RAND:

  1. Design of Efficient Randomized Algorithms
  2. Foundations of Randomized Complexity
  3. Randomized Approximation Algorithms
  4. Derandomizing Algorithms
  5. Computational Learning Theory
The research on Design of Efficient Randomized Algorithms (Work Area 1) was focussed on design of efficient algorithms for combinatorial and algebraic problems.

The research on Foundations of Randomized Complexity (Work Area 2) was focussed on the problems of separation of randomized time classes, design of pseudorandom generators, and direct interactive protocols for combinatorial enumeration problems.

The research on Randomized Approximation (Work Area 3) and Derandomizing Algorithms (Work Area 4) was concentrated on efficient approximation algorithms for the number of important combinatorial counting problems, as well the uniform and deterministic simulations of general threshold circuits by the majority circuits.

The research activities in Computational Learning Theory (Work Area 5) was mainly concerned with the problems of learning some classes of boolean functions by queries, VC--dimension of polynomials and rational functions, and sparse interpolation.

For more information and the research papers resulting from the RAND activities see our research report (85100-CS).

Annual Progress Report 1993/1994

The research within RAND in reporting period June 1, 1993 -- July 30, 1994 was conducted again in all the main research areas of RAND:

  1. Design of Efficient Randomized Algorithms,
  2. Foundations of Randomized Complexity,
  3. Randomized Approximations Algorithms,
  4. Derandomizing Algorithms,
  5. Computational Learning Theory.
The research in Area (1) -- (4) followed the lines described in Annual Progress Report 1992 / 1993.

Compared with the Annual Progress Report 1992 / 1993 the Research Area (5) Computational Learning Theory was extended considerably by the study of the VC Dimension of general quantified formulas, and applications in neural networks and commputational geometry.

For more information and the research papers resulting from the RAND activities see our research report (85127-CS).

For more information see also:

Last modified: September 8th, 2004

[ University of Bonn | CS Department | Chair V | deutsche Version ]