The research program can be subsummed under four guiding themes:
- Characterization of random objects
- Characterization of objects using randomness
- Analysis of algorithms with random input
- Analysis of randomized algorithms
Theme 1: Characterization of random objects
In classical graph theory and combinatorics, the approach is mostly deterministic. For example, one wishes to know the conditions a graph, a partial order, or some other combinatorial object has to satisfy, so that it possesses, with certainty, a particular property.
In contrast, when characterizing random objects one examines a class of discrete objects with a probability distribution. The main concern is then to determine the probability that a randomly chosen object from this class possesses a particular property. The aim is to compute average values of parameters and to find properties, whose probability tends to one as the size of the objects is increasing. Such a characterization can often be given relatively easily, if the objects can be modelled using local, independent random experiments. The classic example of such a model is the theory of random graphs Gn,p, whose edges independently exist with probability p. But the problem becomes far more difficult, if one investigates graphs chosen randomly from some restricted class.
Theme 2: Characterization of objects using randomness
In the problems addressed so far, the probability distribution was given as part of the model under consideration, and the focus was laid on determining typical properties of its representatives. In the context of Theme 2 - Characterization of objects using randomness - however, randomness will be a tool rather than the object of investigation. Accordingly, the probability distributions are adjusted as to meet certain requirements.
One of the aims are existence proofs using the so-called probabilistic method: instead of specifically constructing a desired object, one carries out a number of random experiments and shows that there is a positive probability that the required structure is finally obtained, and thus the object must exist. It is no coincidence that similarities to the methods of Theme 4 arise in this way - as this is a randomized algorithm.
Another objective of Theme 2 is to model and analyse complex real systems (such as the world wide web, social networks, etc.). The motivation is the empirical observation that many of these real systems display similar properties (few edges in total, yet a low diameter and high local density), which one would like to specify more precisely and to model in mathematical terms. The underlying vision is to get a better "understanding" of these real networks by ways of such a modeling and the subsequent analysis. Related to this is the aspiration that further properties will emerge, which can also be found in the real structures, and which, for example, makes it possible to design search or sort algorithms, specifically adjusted to these networks.
Theme 3: Analysis of algorithms with random input
Algorithms are classically evaluated on the basis of a worst case analysis - their performance is measured using the most difficult input (for them). This assessment relies on the construction of artificial inputs for complexity reductions. However, an algorithm which is exponential in the worst case often performs well in practice. The example par excellence is the simplex algorithm.
Theme 3 - Analysis of algorithms with random input - surveys the performance of an algorithm adopting the following point of view: How does the algorithm behave on an input, which is chosen randomly according to a probability distribution on the space of all inputs? In this regard, there are basically two different criteria of interest, namely the expected runtime and the expected quality of the solution, measured as the "distance" from the optimal solution. This probabilistic perspective, also known as the average case analysis of an algorithm, attempts to provide a sound theoretical basis for the behaviour, that is observed in practice.
Theme 4: Analysis of randomized algorithms
While under Theme 3 the emphasis is on the performance of deterministic algorithms on random input, here we consider algorithms which, during their course, make decisions based on random experiments. In doing so, one normally considers deterministic inputs, i.e. a worst case analysis is carried out. This addition of random elements in algorithms may be done with two different objectives in mind.
One may view the classical worst case analysis of algorithms (with bounds for the runtime or quality guarantees for the produced solution as objectives) as a game, in which a "malicious" opponent attempts to discredit the algorithm by constructing precisely those instances which are most difficult for the algorithm in question. In this case, the insertion of random decisions in the algorithm can limit the possibilities of the opponent enormously (if the expected runtime or quality, taken over all random decisions of the algorithm, is taken as the measure for the worst case analysis). But not only do random algorithms often produce notably good solutions with respect to quality or runtime, in many cases they are also surprisingly elegant.
Deutsch