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.

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