New Approaches to Questions in Sampling, Counting, and Optimization

该项目涉及与概率，组合学，统计力学和优化领域重叠的基础研究方向。技术挑战包括加速离散结构（如图）上的随机游动，限制于特殊格子集的经典随机游动的最优分析，以及开发从图到超图的新组合枚举技术。所得到的方法在统计物理学中有潜在的应用。 其中一些应用，如旅行消防员问题，是受到实际挑战的启发，并将产生重要的社会影响。该项目为学生提供培训机会。PI将继续举办临时讲座系列以及工作组活动，这些活动以初级研究人员为特色并为他们提供支持，包括来自代表性不足的少数民族的研究人员。该项目包括努力加速随机游走，以实现更快的采样，灵感来自Langevin动力学和连续优化的加速技术;严格估计分布格上受约束随机游走的混合时间，这项研究最初是由正方形格上键渗透的动力学方面激发的;以及超图产生的簇扩展和独立多项式的零自由度的发展。提出的一个基本问题集中在是否采样使用传统的一阶马尔可夫链动态从一个离散的有限集与规定的分布可以加速，使用某些二阶动态。虽然最初的研究表明，这样的加速谱隙是可行的，但目前还不清楚如何在离散空间上的离散（或连续）时间随机游走的背景下模拟这样的过程。第二个主题解决了一个更深入的理解，在超图的采样和计数独立集的追求。 由于直接计算这些对象是众所周知的是棘手的;概率方面通过集群扩展和超图多项式的零被认为是潜在的富有成效的方向。这个奖项反映了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.