New Approaches to Questions in Sampling, Counting, and Optimization

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.