AF: Small: Random Processes, Statistical Physics and Computation

AF：小：随机过程、统计物理和计算

• 批准号: 1420934
• 负责人: Alistair Sinclair
• 金额: $ 44.97万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-01 至 2018-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1420934&HistoricalAwards=false
• 关键词: AF; Small; Random; Processes; Statistical

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.

该项目关注随机和物理过程的定量分析，既被视为理论计算机科学技术可以发挥作用的应用领域，也被视为为计算机科学理论提出新方向的推动力。除了理论计算机科学（算法和计算复杂性）的核心研究课题外，该项目还通过“计算透镜”检查与概率和统计物理领域的联系。具体而言，该项目将处理以下两大主题：带有算法味道的随机过程：对矩阵预处理的迭代算法的严格研究，这种算法在数值线性代数中广泛使用，但在理论上却很少被理解；对超出当前技术范围的某些基本马尔可夫链的分析；从计算的角度理解非线性随机过程，称为“二次动力系统”，它推广了物理学中的经典玻尔兹曼方程和群体遗传学中的重组模型。统计物理的计算方面：发展更复杂的技术来研究自旋系统中空间混合的关键特性及其算法含义；统计物理中自然发生的组合多项式（配分函数）稳定性性质的研究及其在算法和计算复杂性中的应用；以及统计物理模型在社交网络病毒式营销等现象研究中的潜在应用。该项目更广泛的影响包括在理论计算机科学、统计物理和应用概率等跨学科领域培养研究生。