AF: Small: Random Processes, Statistical Physics and Computation

该项目涉及随机和物理过程的定量分析，既被视为理论计算机科学技术可以有用的应用领域，也被视为为CS理论提出新方向的推动力。除了理论计算机科学(算法和计算复杂性)的核心研究课题外，该项目还通过“计算透镜”研究概率和统计物理领域，与它们建立联系。具体地说，该项目将解决以下两个广泛的主题：1.具有算法味道的随机过程：严格研究在数值线性代数中广泛使用但在理论上知之甚少的矩阵预条件迭代算法；分析某些超出当前技术范围的基本马尔可夫链；从计算的角度理解被称为“二次动力系统”的非线性随机过程，它概括了物理学中的经典波尔兹曼方程和种群遗传学中的重组模型。统计物理的计算方面：开发更复杂的技术来研究自旋系统中空间混合的关键性质及其算法含义；调查统计物理中自然出现的组合多项式(配分函数)的稳定性性质，以及它们在算法和计算复杂性中的应用；以及统计物理模型在社会网络中病毒式营销等现象的研究中的潜在应用。该项目的广泛影响包括理论计算机科学、统计物理和应用概率等交叉学科领域的研究生培训。

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.