CAREER: Phase Transitions in Randomized Combinatorial Search and Optimization Problems

点击翻译按钮获取中文摘要

This project centers on constraint satisfaction problems (csps) - archetypal examples of combinatorial search/optimization problems - with a principal aim of building mathematical theory for these problems. A further objective is to promote connections to statistical physics and computer science, where random csps are fundamental models. Indeed, recent progress on random csps has crucially relied on the exchange of ideas among several disciplines: probability, statistical physics, combinatorics, and computer science. The proposed research will endeavor to advance this dialogue, which has potential to open new research avenues in those disciplines. The proposed research is interdisciplinary in nature: its primary focus is in the development of probability theory, but it is expected that the research approach will be much influenced by developments in statistical physics and computer science. The educational component of the proposal seeks to further promote this interdisciplinary aspect, in classroom education as well as in mentorship of graduate students. With the proliferation of statistical inference problems on large datasets, the development of fast algorithms for combinatorial problems becomes an increasingly urgent problem. At the same time it becomes more important to quantify fundamental barriers in these problems, in terms of information-theoretic and algorithmic limits. This study is complemented by proposing to develop more robust techniques to handle a wider range of problems, including some concrete problems of interest for network theory and machine learning. The educational component involves curriculum development at undergraduate and graduate levels, graduate special topic course development, and mentoring graduate students and postdocs.Combinatorial search/optimization problems are prominent in a wide range of scientific contexts. Broadly, the defining feature of these problems is that the a priori solution requires exhaustive search over a combinatorial state space such as {0,1}^n. A major challenge is that many such problems are expected to be computationally intractable in worst-case instances (np-hard). In response to this, significant attention has been directed towards random problem instances - they represent natural average-case scenarios, and serve as a useful practical benchmark. A deeper understanding of obstacles in the random setting has potential to inspire algorithmic advances. Practical considerations aside, random problem instances are of deep theoretical interest, and full of rich connections among diverse fields of research. In probability theory, random csps have contributed numerous long-standing open problems - especially ones concerning various phase transitions, conjectured either from numerical simulations or from physical heuristics. A notable problem of this type is the location of sharp satisfiability thresholds. It is a widely held belief that for many random csps, the solution space has a complicated geometric structure; and that this is precisely what obstructs standard probabilistic approaches for analyzing phase transitions. Moreover, it is conjectured that essential features of the solution space geometry are universal to a large class of random csps. Some components of this conjectural picture have been validated by recent progress in the theory of random csps, including results on satisfiability thresholds and partition function asymptotics. However, many key aspects of this picture - particularly ones relevant to algorithmic challenges - remain at the level of conjecture. One of the main goals of the current project is to shed light on these questions: to this end, specific research problems are posed regarding asymptotic properties of the solution space (in the search context) and energy landscape (in the optimization context).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.