Probabilistic Graph Theory and Random Constraint Satisfaction Problems

概率图论和随机约束满足问题

• 批准号: RGPIN-2019-06522
• 负责人: Molloy, Michael
• 金额: $ 2.99万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=688341
• 关键词: Probabilistic; Graph; Theory; Random; Constraint

My research program encompasses many aspects of graph theory and related fields, and their role in theoretical computer science. Much of my work in these areas involves probability.******Graph theory is a fascinating and important pure mathematical field which, with the advent of modern computing, gained a new importance because of its applications. Many of the problems that arise in computer science are best modelled with graphs. For example, massive networks are massive graphs and the problem of finding good schedules is a graph colouring problem. So the use of graph theory to study computing has grown immensely.******One of the most important modern trends in graph theory is the use of tools and concepts from probability. The probabilistic method is a powerful and elegant tool for proving theorems and for designing algorithms. The use of random choices has led to the development of much simpler and more efficient algorithms for many fundamental problems. When studying the behaviour of an algorithm, we often ask how it performs on an average input, which amounts to analyzing its behaviour on a random input. This has led to a whole new need for the study of random graphs, a mathematical field that was introduced by Erdos and Renyi in the 1950's. Random structures have been recognized as a vast source for difficult inputs that can be used for the testing and refinement of algorithms.******Many of the most important problems in the field of random structures, eg colouring random graphs and the satisifiability of random boolean formulae, fall under the category of random constraint satisfaction problems. This area has attracted intense interest from disciplines including computer science, mathematics and physics. Recently, most of the leading work in this area has revolved around a collection of hypotheses developed by statistical physicists. For the most part, these hypotheses are not rigorously established, but they are developed using very heavy mathematical analysis. They explain many known phenomena and predict others involving, eg the values of some intensively sought parameters (the 'satisfiability thresholds') ad the longstanding observation that such problems tend to be algorithmically very challenging. Much of my research involves grounding these hypotheses with rigorous proofs and understanding their implications.**

我的研究项目涵盖图论和相关领域的许多方面，以及它们在理论计算机科学中的作用。 我在这些领域的大部分工作都涉及概率。******图论是一个令人着迷且重要的纯数学领域，随着现代计算的出现，它因其应用而获得了新的重要性。 计算机科学中出现的许多问题最好用图表来建模。 例如，大规模网络是大规模的图，找到好的时间表的问题是图着色问题。因此，使用图论来研究计算的情况已大大增加。******图论最重要的现代趋势之一是使用概率工具和概念。概率方法是证明定理和设计算法的强大而优雅的工具。 随机选择的使用导致了针对许多基本问题的更简单、更有效的算法的开发。 在研究算法的行为时，我们经常会问它在平均输入上的表现如何，这相当于分析其在随机输入上的行为。 这引发了对随机图研究的全新需求，随机图是 Erdos 和 Renyi 在 1950 年代引入的一个数学领域。随机结构已被认为是可用于测试和改进算法的困难输入的巨大来源。******随机结构领域中的许多最重要的问题，例如随机图着色和随机布尔公式的可满足性，都属于随机约束满足问题的范畴。 该领域引起了计算机科学、数学和物理学等学科的浓厚兴趣。 最近，该领域的大部分领先工作都围绕着统计物理学家提出的一系列假设。 在大多数情况下，这些假设并不是严格建立的，而是通过非常繁重的数学分析得出的。它们解释了许多已知现象并预测了其他现象，例如一些深入寻求的参数值（“可满足性阈值”）以及长期观察到的此类问题在算法上往往非常具有挑战性。 我的大部分研究涉及通过严格的证明来奠定这些假设并理解其含义。**