CAREER: Phase Transitions in Randomized Combinatorial Search and Optimization Problems

职业：随机组合搜索和优化问题中的相变

• 批准号: 1940092
• 负责人: Nike Sun
• 金额: $ 44.99万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-06-01 至 2023-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1940092&HistoricalAwards=false
• 关键词: CAREER; Phase; Transitions; Randomized; Combinatorial

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.

该项目以约束满意度问题（CSP）为中心 - 组合搜索/优化问题的原型示例 - 主要目的是为这些问题构建数学理论。一个进一步的目标是促进与统计物理和计算机科学的联系，其中随机CSP是基本模型。确实，随机CSP的最新进展至关重要地依赖于几个学科之间的思想交流：概率，统计物理学，组合学和计算机科学。拟议的研究将努力推进这种对话，该对话有可能在这些学科中开放新的研究途径。拟议的研究本质上是跨学科的：它的主要重点是概率理论的发展，但预计研究方法将受到统计物理学和计算机科学发展的发展。该提案的教育部分旨在在课堂教育以及研究生的指导中进一步促进这一跨学科的方面。随着大型数据集统计推断问题的扩散，组合问题的快速算法的发展成为一个日益紧迫的问题。同时，就信息理论和算法限制而言，量化这些问题中的基本障碍变得更加重要。通过建议开发更强大的技术来处理更广泛的问题，包括网络理论和机器学习感兴趣的一些具体问题，可以补充这项研究。教育组成部分涉及本科和研究生级别的课程开发，研究生特殊主题课程的发展以及指导研究生以及PostDocs.combinatorial搜索/优化问题在广泛的科学环境中很明显。从广义上讲，这些问题的定义特征是先验解决方案需要在组合状态空间（例如{0,1}^n）上进行详尽的搜索。一个主要的挑战是，在最坏情况下（NP-HARD），预计许多此类问题在计算上是棘手的。为此，很大程度上关注了随机问题实例 - 它们代表了自然的平均场景，并作为有用的实用基准。对随机环境中的障碍有更深入的了解有可能激发算法的进步。除了实际的考虑之外，随机问题实例具有深厚的理论兴趣，并且在不同的研究领域之间充满了联系。在概率理论中，随机CSP贡献了许多长期存在的开放问题，尤其是关于各种相变的问题，这些问题是由数值模拟或物理启发式方法推测的。这种类型的一个值得注意的问题是尖锐的满足性阈值的位置。人们普遍认为，对于许多随机的CSP，解决方案空间具有复杂的几何结构。这正是妨碍分析相变的标准概率方法的原因。此外，人们认为，解决方案空间几何形状的基本特征与大型随机CSP是通用的。随机CSP理论的最新进展，包括满足性阈值和分区函数渐近性的结果，已经验证了这种猜想的某些组成部分。但是，这张图片的许多关键方面（尤其是与算法挑战相关的关键方面）仍然处于猜想的水平。当前项目的主要目标之一是阐明以下问题：为此，针对解决方案空间的渐近特性（在搜索环境中）和能源格局（在优化环境中）提出了具体的研究问题。该奖项反映了NSF的法定任务，并认为通过基金会的知识优点和广泛的criperia criperia criperia criperia criperia criperia criperia rection the Awmentia the奖励。