AF: Small: Approximate Counting, Stochastic Local Search and Nonlinear Dynamics

理论计算机科学（TCS）关注算法和复杂性理论中的核心问题，以及通过所谓的“计算透镜”看待的其他科学学科中的许多问题。这指的是对许多科学现象的研究，这些现象本质上基本上是计算性的，因此可以从TCS的角度受益。该项目既涉及核心主题，也涉及与其他学科的联系，特别是统计物理学和群体遗传学。该项目的一个统一主题是分析所有这些领域中出现的随机和物理过程的技术。该项目将与复杂分析、应用概率和统计物理等领域的专家合作，共同研究这些界面领域。该项目为研究生和博士后培训提供了许多机会，并且本研究的想法将进入课程课程。研究者还对本科和K-12教学保持着浓厚的兴趣，后者通过他参与伯克利数学圈。在更技术性的层面上，该项目包含三个主题：1。近似计数：用于计数问题的近似算法的发展，特别强调“多项式几何”的新兴技术及其与更经典的马尔可夫链蒙特卡罗和相关衰减技术的联系。应用包括组合学中的生成函数、统计物理中的配分函数、体积计算以及机器学习中的图形模型分析。随机局部搜索算法：研究一种新的框架，源于Lovasz局部引理算法的最新进展，用于设计和分析随机局部搜索算法，该算法通过连续消除“缺陷”来搜索具有所需性质的组合结构。新框架基于矩阵范数，并受到控制理论中的线性时不变分析的启发。非线性动力学：研究两个不同但相关的非线性动力系统的计算方面：质量作用动力学和“红皇后”动力学。质量作用动力学是化学反应网络的标准模型，也捕获了其他过程，如统计物理学中的玻尔兹曼方程，遗传算法和群体遗传学中的重组。更具推测性的红后动力学是多物种在选择下进化的新模型。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Theoretical Computer Science (TCS) is concerned with core questions in algorithms and complexity theory, and also with many questions in other scientific disciplines viewed through the so-called "computational lens." This refers to the study of many scientific phenomena that are fundamentally computational in nature and can therefore benefit from a TCS perspective. This project addresses both core topics and connections with other disciplines, notably statistical physics and population genetics. A unifying theme in the project is techniques for the analysis of random and physical processes arising in all of these fields. The project will engage as collaborators experts in fields such as complex analysis, applied probability and statistical physics to work on these interface areas. The project affords many opportunities for graduate student and postdoctoral training and ideas from this research will find their way into course curricula. The investigator also maintains a strong interest in undergraduate and K-12 teaching, the latter through his involvement with the Berkeley Math Circle.On a more technical level, the project contains three broad themes:1. Approximate counting: the development of approximation algorithms for counting problems, with special emphasis on the emerging technique of "geometry of polynomials" and its connections to the more classical techniques of Markov chain Monte Carlo and correlation decay. Applications include generating functions in combinatorics, partition functions in statistical physics, the computation of volumes, and the analysis of graphical models in machine learning.2. Stochastic local search algorithms: the study of a novel framework, arising from recent advances on the algorithmic Lovasz Local Lemma, for the design and analysis of stochastic local search algorithms, which search for combinatorial structures with desired properties by successively eliminating "flaws". The new framework is based on matrix norms and is inspired by linear time invariant analysis in control theory.3. Nonlinear dynamics: the study of computational aspects of two distinct, but related nonlinear dynamical systems: mass action kinetics and the "red-queen" dynamics. Mass action kinetics is a standard model for chemical reaction networks, and also captures other processes such as the Boltzmann equation in statistical physics, genetic algorithms and recombination in population genetics. The more speculative red-queen dynamics is a novel model for the evolution of multiple species under selection.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.