RAND2_logo.gif ESPRIT Working Group
"Randomized Algorithms"
RAND2 (No. 21726)

University of Bonn -> Department of Computer Science -> Chair V
  • Keywords
  • Objectives and Approach
  • Workshops and Seminars
  • Results
  • Contact Point
  • Partner List
  • Links
  • Acknowledgements
  • Keywords

    Randomized algorithms, approximation algorithms,
    quantum computation, neural networks,
    combinatorial enumeration, randomized complexity theory,
    random generation of combinatorial structures, pseudorandom computation,
    randomized boolean and arithmetic circuits,
    computational learning theory.

    Objectives and Approach

    In recent years randomized algorithms, approximation algorithms and randomized complexity theory have become major subjects of study in the design of computer algorithms and in the theory of computation. For some computational problems, it appears now that randomized or pseudo-randomized algorithms are more efficient than the deterministic ones (in terms of hardware size, running time, circuits depths, transparent descriptions, etc.). The very striking examples recently are the new randomized approximation algorithms for enumerating the number of perfect matchings in certain classes of graphs or for some enumeration problems in the boolean algebra and the finite fields, new approximation schemes for instances of NP-hard problems, estimating the volume of convex bodies, and the quantum algorithms for factoring integers. Another breakthrough on estimating VC dimension and sample sizes of sigmoidal neural networds, the networks most frequently used in various applications, was achieved recently by the RAND researchers (using a combination of certain techniques from combinatorics, differential topology, algebraic geometry and model theory). Solutions to these problems have applications ranging from the algorithms and network design and coding theory to statistic mechanic and quantum field theory.

    In this new and fast growing area, we are confronted with the number of very fundamental questions for which the classical theory of computation knows only hardly the answers. It remains for example an important open question how much randomness is necessary to accomplish certain levels of efficiency in algorithms, and also how efficient the deterministic simulation of some classes of algorithms is possible. The proposal plans on continuing the research started in RAND and will address the above mentioned problems, and concentrate on:

    1. Design of efficient (both sequential and parallel) randomized algorithms for some selected combinatorial, algebraic and geometric problems;
    2. Foundations of randomized complexity of computational problems;
    3. Randomized approximation problems;
    4. Computation with limited randomness resources (de-randomization methods);
    5. Error-Resilient ATM Based Transmission;
    6. Computational learning theory, theory of Neural Networks, and applications;
    7. Quantum Computation.

      The topic "Quantum Computation" extends the research program initiated in RAND - Working Group. We plan research on foundations of quantum computation, in particular on the power of quantum circuits, and the quantum approximation algorithms.

    The selection of the partners for this Working Group was based on the grounds of the relevance of their research towards the above topics. The extension of the RAND2 by the Weizmann Institute, Rehovot, was motivated by the relevance of the research conducted there towards topics (1) - (4).

    Workshops and Seminars

    1999 Program

    Esprit Working Group RAND2
    Workshop on Randomized Algorithms,
    Sept. 19-22, 1999.

    Esprit Working Group RAND2
    Workshop on Randomized Algorithms
    Thursday 20th May - Saturday 22nd May, 1999
    Gif-sur-Yvette, Université de Paris-Sud

    1998 Program

    RAND Seminar
    University of Bonn

    Séminaire Complexité
    Université de Paris-Sud

    Esprit Working Group RAND2
    Workshop under the auspices of the
    International Center for Mathematical Sciences
    Friday 27th - Sunday 29th March, 1998

    1997 Program

    RAND Seminar
    University of Bonn

    Séminaire Complexité
    Université de Paris-Sud

    Esprit Working Group RAND2
    Workshop on Randomized Approximation Algorithms
    Saturday 20th - Monday 22nd September, 1997
    University of Leeds


    Annual Progress Report 1996 / 1997

    Contact Point

    Contact Person:
    Marek Karpinski

    Postal Address:
    Dept. of Computer Science
    Römerstr. 164
    53117 Bonn

    Phone and Fax:
    +49 (0)228 734224 (office)
    +49 (0)228 734327 (secretary)
    +49 (0)228 734440 (fax)


    Partner List

    (with local RAND2 webpages)
    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
    Mail alias for all members of RAND2:



    Last Change: 08/18/99 at 13:00:39
    University of Bonn -> Department of Computer Science -> Chair V

    Powered by Zope