New Approaches to Questions in Sampling, Counting, and Optimization

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

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.