Random, Computational, and Statistical Processes on Networks

Princeton University, Princeton NJ

Investigators

Abstract

This project will apply modern methods in probability theory to a range of problems arising in combinatorics, theoretical computer science, mathematical physics, statistics and other fields. A central focus will be understanding the problem of simultaneously satisfying many constraints each chosen randomly. We will determine when there are solutions, how many solutions and when it is possible to efficiently find them. A second direction involves models of shortest paths with random costs where we will study the geometry and chaotic nature of these paths. Finally we will consider a range of questions involving the statistical inference of combinatorial objects such as networks, trees and partitions which will be applicable to problems such as finding communities in networks and uncovering the genetic relationships between different species. Throughout this project we will work to make mathematically rigorous ideas and heuristics originating in statistical physics. In the case of random constraint satisfaction problems, we will establish a range of one-step replica symmetry breaking predictions for models such as colorings, satisfiability and large independent sets in random networks. In first and last passage percolation we will combine more classical methods of percolation with results from exactly solvable models to answer questions about the slow bond model, coalescence of geodesics and rotationally invariant first passage percolation. Many problems in statistical inference involve recovering combinatorial structures. For models of group synchronization and phylogenetic reconstruction we will give rigorous bounds on the sampling complexity and computational efficiency. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.