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年代引入的数学领域。随机结构被认为是可用于算法测试和完善的困难输入的广泛来源。****** ******随机结构领域中许多最重要的问题，例如随机颜色随机图和随机布尔格式的满足性，属于随机约束满意度问题的类别。 该领域吸引了包括计算机科学，数学和物理学在内的学科的浓厚兴趣。 最近，该领域的大多数主要工作围绕着统计物理学家提出的一系列假设。 在大多数情况下，这些假设不是严格确定的，但是它们是使用非常大的数学分析来开发的。他们解释了许多已知现象，并预测了其他现象，例如某些强烈寻求参数的价值（“满意度阈值”）是长期以来的观察结果，即这种问题往往是算法上非常具有挑战性的。 我的大部分研究都涉及将这些假设与严格的证据结合起来并理解它们的含义。**