AF: Small: Markov Chain Algorithms for Problems from Computer Science and Statistical Physics

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Sampling algorithms based on Markov chains are used across the sciences, primarily for approximate counting, combinatorial optimization and modeling. These algorithms use random walks to explore a large state space, and determining their convergence time is typically the critical step for establishing the efficiency of many approximation algorithms using random sampling. The primary goals of this project are identifying problems amenable to this approach, designing provably efficient algorithms, and developing probabilistic techniques to enable such analyses. For each of these goals, computer science benefits from insights from related fields, especially statistical physics and discrete probability. The project explores strong connections between phase transitions of physical systems and convergence rates of local Markov chains to explain the limitations of various natural approaches to sampling. This correspondence also guides our search for more efficient algorithms by allowing nonlocal moves or designing Markov chains on modified state spaces. This PI will explore both aspects, by designing methods from stronger analysis in the efficient and non-efficient regimes on both sides of the phase transition, and by searching for alternative non-local algorithms for sampling when local algorithms have been proven to be prohibitively slow. Applications to be explored include the hard-core model from statistical physics, the Schelling model of segregation from economics, geometric sampling problems form planning and design, and sampling problems from data science where inputs are noisy or evolving over time. The broader impacts of this interdisciplinary work have many facets, especially for bridging scientific fields by bringing insights from one field to another. The PI regularly gives technical and survey talks to students and faculty across fields, directs an interdisciplinary research center and organizes workshops and conferences including participants from disparate disciplines. The results disseminated by talks, publications and will be made accessible on websites. The PI continues to be a strong advocate for women in academia, including serving as the ADVANCE Professor of Computing, participating on equity panels, presenting lectures to broad groups of women, and advising women Ph.D. students.