During the past decade, the quantitative analysis of random processes has led to dramatic advances in the design of efficient algorithms for fundamental computation problems. The PI is continuing research on the application of these ideas, as well as beginning to investigate new paradigms based on nonlinear and cooperative processes. Specifically, the project focuses on the following directions: (1) the analysis of mixing rates of Markov chains, with applications to efficient algorithms for problems in statistical physics and combinatorics; (2) the study of computational complexity of counting problems, and their classification with respect to efficient approximability; Algorithmic applications of nonlinear random processes, in particular quadratic dynamical systems; (3) the theoretical and experimental study of general randomized search heuristics in combinatorial optimization, including Metropolis algorithm, simulated annealing, and cooperative processes.
