The aim of this research is to develop new results in the probabilistic analysis of algorithms. In particular, this project will concentrate on three areas: Random walks on graphs: the aim is to improve the complexity of an algorithm for computing volume and to develop randomized counting schemes for some Randomized heuristics: the goal is to determine whether randomization helps in some heuristics for combinatorial optimization. Average performance of algorithms: algorithms with good avverage case performance will be developed for NP-hard problems and for problems which are complete for P.
