New Approaches to Questions in Sampling, Counting, and Optimization

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

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.