The theme of this project is the application of probabilistic, algorithmic and combinatorial ideas to the following three areas: (1) Rigorous analysis of heuristics for statistical problems such as fast random generation and simulation of posterior distributions, and classification of the difficulty of these problems. Of particular interest are heuristics based on Markov Chain Monte Carlo. The emphasis will be on understanding the models for which such heuristics are provably efficient as well as cases where they are not. The investigator expects this to lead to a better understanding of how to design algorithms for these problems. (2) The proposal aims to explore the connection between phase transitions in Gibbs measures for spin systems on sparse random graphs and algorithmic phase transitions in constraint satisfaction problems. For example, one long-term goal is to rigorously show a connection between decay of correlations in the Gibbs measure and phase transitions in the connectivity of the solution space. (3) The investigator proposes to study properties of permutations under non-uniform measures, especially the asymptotics, large deviations and fluctuations of statistics such as the longest increasing subsequence. These questions give rise to interesting refinements of the theory of limiting shapes of random Young diagrams, point processes and interacting particle processes. One question we aim to shed more light on is the relationship between the number of inversions in a permutation and the longest increasing subsequence.
This project envisages using probabilistic techniques to solve problems from areas such as statistics, statistical physics, computer science and combinatorics. Problems involving large amounts of data and algorithms for fast simulation of large systems are of interest to researchers in industry and experimentalists in the physical sciences. The proposal aims to rigorously address the question of efficient simulation. The study of Gibbs measures is a classical topic in probability and statistical mechanics. The questions proposed here are of value in establishing connections between the theory of Gibbs measures and theoretical computer science which attempts to understand efficiency of algorithms, including those which make use of randomness. Permutations are well studied objects in combinatorics and probability. The investigator hopes that their study under distributions that are not uniformly random will contribute new methods of analysis and results to this classical subject. The areas described are a good source of problems of practical and theoretical importance which students at both graduate and undergraduate levels could find a stimulating point at which to start their scientific inquiries.
