Probabilistic Graph Theory and Random Constraint Satisfaction Problems

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

• 批准号: RGPIN-2014-03858
• 负责人: Molloy, Michael
• 金额: $ 4.52万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=587459
• 关键词: 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 concentrates on areas which involve probability. Graph theory is a fascinating and important pure mathematical field which, with the advent of the computer age, gained a new importance because of its applied aspects. Many of the problems that arise in computer science are best modelled by graphs. For example, massive networks are massive graphs and the problem of finding good schedules is what is known as a graph colouring problem. Thus, over the past few decades, 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 theory. The probabilistic method is a powerful and elegant tool for proving theorems. Also, the use of random choices in algorithms has led to the development of much simpler and more efficient methods for many important 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, long before its importance to computer science was realized. In more recent decades, 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 this field, eg. colouring of random graphs and random instances of boolean formulae, fall under the category of random constraint satisfaction problems. This area has attracted intense interest from disciplines including mathematics, computer science and physics. Recently, much of the leading research in this area has revolved around a collection of hypotheses developed by physicists. For the most part, these hypotheses are not rigorously established, but they are developed using substantial mathematical analysis. They explain many known phenomena and predict others involving, eg. the values of some intensively sought parameters (the "satisfiability thresholds''), and the long-standing 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年代引入的数学领域，早在实现了计算机科学的重要性之前。 在最近的几十年中，随机结构被认为是可用于测试和完善算法的困难输入的广泛来源。 该领域的许多最重要的问题，例如。随机图的着色和布尔公式的随机实例，属于随机约束满意度问题的类别。 该领域吸引了包括数学，计算机科学和物理在内的学科的浓厚兴趣。 最近，该领域的许多领先研究围绕着物理学家提出的一系列假设。 在大多数情况下，这些假设不是严格确定的，但是它们是使用大量数学分析来开发的。 他们解释了许多已知现象，并预测其他涉及的现象，例如。 某些强烈寻求参数的价值（“满意度阈值”），以及长期以来，这种问题在算法上倾向于非常具有挑战性。我的许多研究都涉及将这些假设与严格的证据扎根，并理解它们的含义。