Probabilistic Considerations in the Analysis of Algorithms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

The investigator will continue his work on the interplay between probability and algorithms. He has identified two distinct but very important aspects of such study. In the first instance he will study randomized algorithms i.e. those algorithms that introduce randomness as a means of speeding up computation. In the second instance, he will consider the average case performance of algorithms. Here, he wants to try to explain the good performance of simple algorithms on "typical" problems as opposed to the worst-case performance exemplified by the pathological examples of complexity theory. In the area of randomized algorithms, the investigator will consider problems arising in the study of Monte Carlo Markov Chain algorithms. In particular he will study their use in problems associated with combinatorial counting problems and with problems in Statistical Physics. He will also continue his study of the Edge Disjoint Path problem and the construction of a generalisation of the well known matrix Singular Value Decomposition to multi-dimensional matrices. In the area of average case analysis, he will continue his work on the Traveling Salesman Problem and try to extend his ideas to the independent symmetric model. He will continue his work on analysing the efficacy of the Sequencing By Hybridization technique in Computational Biology. Finally, he will continue to work on probabilistic models of the World Wide Web in an attempt to find a useful model for the testing of algorithmic ideas.