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在20世纪50年代引入的数学领域。随机结构被认为是一个巨大的困难输入源，可用于测试和改进算法。随机结构领域中的许多重要问题，如随机图的着色和随机布尔公式的可满足性，都属于随机约束满足问题的范畴。 这一领域吸引了包括计算机科学、数学和物理学在内的学科的浓厚兴趣。 最近，这一领域的大部分主要工作都围绕着统计物理学家提出的一系列假设。 在大多数情况下，这些假设并不是严格建立的，而是使用非常繁重的数学分析来发展的。他们解释了许多已知的现象，并预测其他涉及，例如一些集中寻求参数（“可满足性阈值”）的值和长期观察，这些问题往往是非常具有挑战性的算法。 我的大部分研究都涉及用严格的证据为这些假设奠定基础，并理解它们的含义。