The project is concerned with the quantitative analysis of random and physical processes, viewed both as application areas where techniques from theoretical computer science can be useful, and as an impetus that suggests novel directions for CS theory. Â In addition to core research topics in theoretical computer science (algorithms and computational complexity), the project makes connections with the fields of probability and statistical physics by examining them through the "computational lens."
Specifically, the project will address the following two broad themes:
1. Random processes with an algorithmic flavor: the rigorous study of iterative algorithms for matrix pre-conditioning that are widely used in numerical linear algebra but poorly understood theoretically; the analysis of certain fundamental Markov chains that are beyond the range of current techniques; and the understanding, from a computational viewpoint, of non-linear stochastic processes known as "quadratic dynamical systems," which generalize the classical Boltzmann equation in physics and models for recombination in population genetics.
2. Computational aspects of statistical physics: the development of more sophisticated techniques for studying the key property of spatial mixing in spin systems and its algorithmic implications; the investigation of stability properties of naturally occurring combinatorial polynomials (partition functions) in statistical physics, and their applications to algorithms and computational complexity; and the potential application of models from statistical physics to the study of phenomena such as viral marketing in social networks.
Broader impacts of the project include graduate student training in the interdisciplinary field of theoretical computer science, statistical physics and applied probability.
