CAREER: Algorithms and Models for Random Structures

University Of California-Santa Cruz, Santa Cruz CA

Investigators

Abstract

Random structures have become an indispensable tool of computer science over the last two decades. When used to model input distributions, they provide an easily accessible experimental platform for exploring and testing new algorithms: a number of practically important algorithmic developments have been made by designing algorithms that perform well on certain simple input distributions. When used to model the formation and growth of networks, they have been the dominant analytical tool in an area that has seen explosive growth in recent years: random graphs are now central objects in areas ranging from communications and information retrieval to biology and game theory. This research project focuses on i) the analysis of algorithms on random constraint satisfaction problems, such as random k-SAT and, ii) the development of analytically tractable models of random networks that incorporate realistic constraints, such as low-dimensionality and total connection length. The goal of the first part is to address a number of questions relating the performance of algorithms on random constraint satisfaction problems to structural properties of their solution--spaces. It is partly motivated by the remarkable experimental performance of a new algorithm for such problems, Survey Propagation, that employs a number of deep, but non-rigorous, ideas from statistical physics. The goal of the second part is to remove a number of unrealistic, hard-coded assumptions underlying existing models of random networks by introducing generative models in which networks are maximum entropy solutions of optimization tradeoffs.