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的法定任务，并且使用基金会的知识分子优点和更广泛的影响审查标准，被认为是值得通过评估来支持的。

项目成果

期刊论文数量（17）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Zeros of ferromagnetic two-spin systems

铁磁双自旋系统的零点

DOI：
发表时间：
2020
期刊：
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
0
作者：
Guo, Heng;Liu, Jingcheng;Lu, Pinyan
通讯作者：
Lu, Pinyan

The Ising Partition Function: Zeros and Deterministic Approximation

DOI：
10.1007/s10955-018-2199-2
发表时间：
2017-04
期刊：
Journal of Statistical Physics
影响因子：
1.6
作者：
Jingcheng Liu;A. Sinclair;P. Srivastava
通讯作者：
Jingcheng Liu;A. Sinclair;P. Srivastava

Efficiently list-edge coloring multigraphs asymptotically optimally

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

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

Entropy decay in the Swendsen–Wang dynamics on Zd

Zd 上的 Swendsen-Wang 动力学中的熵衰减

DOI：
10.1214/21-aap1702
发表时间：
2022
期刊：
The Annals of Applied Probability
影响因子：
0
作者：
Blanca, Antonio;Caputo, Pietro;Parisi, Daniel;Sinclair, Alistair;Vigoda, Eric
通讯作者：
Vigoda, Eric

A Deterministic Algorithm for Counting Colorings with 2-Delta Colors