AF: Small: Probabilistic Considerations in the Analysis of Algorithms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

The aim of this project is to advance the understanding of various aspects of probability in relation to algorithm design and analysis. In general this means the study of randomized algorithms, the average case performance of algorithms and related, seemingly random, structures such as social networks. Randomized algorithms are important because they are often the most efficient and some times the only efficient way to solve computational problems. The study of the average case sheds light on why problems which in the worst-case seem computationally difficult or even intractable, can be routinely solved in practise, by simple algorithms. The research on random models of large real world networks is important for answering algorithmic questions about them and for understanding their evolution. The project will study several important problems from the point of view of average case analysis: (i) Cuckoo Hashing is a relatively new hashing algorithm and some of the basic questions about its performance remain unanswered, even though there has been significant progress of late. (ii) The matching problem for graphs is the quintissential polynomial time solvable problem in Combinatorial Optimiztion. Its polynomial time solution is one of the great achievements of the area. Its worst-case complexity, while polynomial still leaves room for improvement and one of the aims of the project is to settle the average case completely. (iii) The hamilton cycle problem for graphs is one of the canonical NP-hard problems. The average-case complexity was reduced to polynomial time some time ago and one of the aims of the project is to reduce this to as close to expected linear time as possible. The project will also several other problems involving average case complexity. The methodology employed will involve the tools and techniques from the field of Random Graphs. The two main tools being concentration of measure and concentration on events that happen with probability close to one. The project will also consider the use of Rapidly Mixing Markov Chains to generate random colorings of graphs and hypergraphs. This topic has close ties to Statistical Physics and has benefited a great deal from the cross-fertilization of ideas. There are still many gaps, particularly in the case of hypergraphs, and the project aims to close them. While graph theory is at least a hundred years old, it is only in recent years that the ubiquitousness of graphs or networks has been so widely recognized. The study of Random Graphs is about fifty years old and techniques from this area are needed to study real world networks. Simply because they evolve in a seemingly random manner. The project will involve several analyses from this area. For example, it is not known what is the component structure of a random graph, evolving under preferential attachment but subject to deletions.