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

AF：小：近似计数、随机局部搜索和非线性动力学

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

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.

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

项目成果

Zeros of ferromagnetic two-spin systems

铁磁双自旋系统的零点

• 发表时间: 2020-01
• 期刊: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA
• 作者: Guo, Heng;Liu, Jingcheng;Lu, Pinyan
• 通讯作者: Lu, Pinyan

Efficiently list-edge coloring multigraphs asymptotically optimally

有效地渐进最优地列出边缘着色多重图

• DOI: 10.1137/1.9781611975994.142
• 发表时间: 2020-01
• 期刊: Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
• 作者: Iliopoulos, Fotis;Sinclair, Alistair
• 通讯作者: Sinclair, Alistair

Uniform Sampling Through the Lovász Local Lemma

通过 Lovász 局部引理进行均匀采样

• DOI: 10.1145/3310131
• 发表时间: 2019-05
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: Guo, Heng;Jerrum, Mark;Liu, Jingcheng
• 通讯作者: Liu, Jingcheng

Private selection from private candidates

从私人候选人中私人挑选

• DOI: 10.1145/3313276.3316377
• 发表时间: 2018-11-19
• 期刊: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Jingcheng Liu;Kunal Talwar
• 通讯作者: Kunal Talwar

Low-temperature Ising dynamics with random initializations

具有随机初始化的低温 Ising 动力学

• DOI: 10.1145/3519935.3519964
• 发表时间: 2022-06
• 期刊: ACM
• 作者: Gheissari, Reza;Sinclair, Alistair
• 通讯作者: Sinclair, Alistair