Random Structures and Algorithms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

This research project is an investigation of discrete mathematical objects, like networks or codes, whose structure is generated randomly. Randomness has long played an important role in the construction of sophisticated mathematical objects and randomness plays a central role in many algorithms in computer science. Part of this research focuses on objects that are generated by a sequence of dependent random choices. Such processes can be good models for the dynamics of real-world phenomenon, like the spread of a disease in a network, the evolution of social networks such as facebook or twitter, or phase transitions in materials. We are particularly interested in the solution of challenging computational problems in the context of random structures, and this work will hopefully be useful in drawing back the shadow of the negative results of complexity theory. The study of random combinatorial structures has emerged as an important component of Discrete Mathematics. This research project focuses on various structural properties of random graphs and hypergraphs. One area of emphasis is the study of the existence of Hamilton cycles in various sparse random graph models. It is natural to conjecture that any suitably random model that ensures that a graph has minimum degree 3 will have a Hamilton cycle with high probability. While this has been established in a few setting, a number of very natural open questions remain, and the development of a unified theory of Hamiltonicity of sparse random graphs is a long range goal of this research. This project also includes the study of algorithmic questions. For example, we will put significant effort into the study of Cuckoo hashing. Here the main question is whether or not the insertion of a new item into the hash table takes constant expected time. Our approach here will be to show that an associated graph has a fast mixing time, applying the theory of mixing times for Markov chains.