New Approaches to Questions in Sampling, Counting, and Optimization

解决采样、计数和优化问题的新方法

• 批准号: 2151283
• 负责人: Prasad Tetali
• 金额: $ 30.3万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-08-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2151283&HistoricalAwards=false
• 关键词: New; Approaches; Questions; Sampling; Counting

The project addresses fundamental research directions overlapping with the areas of probability, combinatorics, statistical mechanics and optimization. The technical challenges include acceleration of random walks on discrete structures such as graphs, optimal analysis of classical random walks restricted to special subsets of lattices, and developing new combinatorial enumeration techniques from graphs to hypergraphs. The resulting methods have potential for applications in statistical physics. Some of the applications, such as the Traveling Fireman Problem, are inspired by practical challenges and would have important societal impacts. The project provides training opportunities for students. The PI will continue to host expository lecture series as well as working group activities that feature and support junior researchers, including those from underrepresented minorities. The project includes efforts to speed up random walks for faster sampling, inspired by acceleration techniques in Langevin dynamics and continuous optimization; tight estimates on the mixing time of constrained random walks on distributive lattices, a study originally motivated by dynamical aspects of bond percolation on the square lattice; and the development of cluster expansion and zero-freeness of independence polynomials arising from hypergraphs. A fundamental question raised focuses on whether sampling using traditionally first-order Markov chain dynamics from a discrete finite set with a prescribed distribution can be accelerated, using certain second-order dynamics. While the initial investigation suggests such a speed-up of spectral gap is feasible, it is unclear how to simulate such a process in the context of discrete (or continuous)-time random walks on a discrete space. A second topic addresses a quest for a deeper understanding of sampling and counting independent sets in hypergraphs. As direct counting of these objects is well-known to be intractable; probabilistic aspects by way of cluster expansion and zeros of hypergraph polynomials are considered as potentially fruitful directions.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.

该项目涉及与概率、组合学、统计力学和优化领域重叠的基础研究方向。技术挑战包括加速离散结构（例如图）上的随机游走、仅限于特殊格子子集的经典随机游走的优化分析，以及开发从图到超图的新组合枚举技术。由此产生的方法具有在统计物理学中应用的潜力。 一些应用程序，例如流动消防员问题，是受到实际挑战的启发，并将产生重要的社会影响。该项目为学生提供培训机会。 PI 将继续举办说明性讲座系列以及工作组活动，以支持初级研究人员，包括来自代表性不足的少数群体的研究人员。该项目包括加速随机游走以实现更快的采样，其灵感来自朗之万动力学和持续优化的加速技术；对分布晶格上约束随机游走的混合时间的严格估计，这项研究最初是由方晶格上键渗流的动力学方面激发的；以及由超图产生的簇扩展和独立多项式的零自由度的发展。提出的一个基本问题集中在是否可以使用某些二阶动力学来加速使用传统的一阶马尔可夫链动力学从具有规定分布的离散有限集进行采样。虽然初步调查表明这种谱间隙加速是可行的，但尚不清楚如何在离散空间上的离散（或连续）时间随机游走的背景下模拟这样的过程。第二个主题致力于更深入地理解超图中独立集合的采样和计数。 众所周知，直接计算这些物体是很困难的；通过聚类扩展和超图多项式零点的概率方面被认为是潜在富有成效的方向。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。