Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
基本信息
- 批准号:RGPIN-2019-06522
- 负责人:
- 金额:$ 2.99万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2019
- 资助国家:加拿大
- 起止时间:2019-01-01 至 2020-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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 年代引入的一个数学领域。随机结构已被认为是可用于测试和改进算法的困难输入的巨大来源。******随机结构领域中的许多最重要的问题,例如随机图着色和随机布尔公式的可满足性,都属于随机约束满足问题的范畴。 该领域引起了计算机科学、数学和物理学等学科的浓厚兴趣。 最近,该领域的大部分领先工作都围绕着统计物理学家提出的一系列假设。 在大多数情况下,这些假设并不是严格建立的,而是通过非常繁重的数学分析得出的。它们解释了许多已知现象并预测了其他现象,例如一些深入寻求的参数值(“可满足性阈值”)以及长期观察到的此类问题在算法上往往非常具有挑战性。 我的大部分研究涉及通过严格的证明来奠定这些假设并理解其含义。**
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Molloy, Michael其他文献
Asymptotically optimal frugal colouring
- DOI:
10.1016/j.jctb.2009.07.002 - 发表时间:
2010-03-01 - 期刊:
- 影响因子:1.4
- 作者:
Molloy, Michael;Reed, Bruce - 通讯作者:
Reed, Bruce
The list chromatic number of graphs with small clique number
- DOI:
10.1016/j.jctb.2018.06.007 - 发表时间:
2019-01-01 - 期刊:
- 影响因子:1.4
- 作者:
Molloy, Michael - 通讯作者:
Molloy, Michael
Noise Pollution: Do We Need a Solution? An Analysis of Noise in a Cardiac Care Unit
- DOI:
10.1017/s1049023x16000388 - 发表时间:
2016-08-01 - 期刊:
- 影响因子:2.2
- 作者:
Ryan, Kevin M.;Gagnon, Matthew;Molloy, Michael - 通讯作者:
Molloy, Michael
VISTA expression and patient selection for immune-based anticancer therapy.
- DOI:
10.3389/fimmu.2023.1086102 - 发表时间:
2023 - 期刊:
- 影响因子:7.3
- 作者:
Martin, Alexander S.;Molloy, Michael;Ugolkov, Andrey;von Roemeling, Reinhard W.;Noelle, Randolph J.;Lewis, Lionel D.;Johnson, Melissa;Radvanyi, Laszlo;Martell, Robert E. - 通讯作者:
Martell, Robert E.
Molloy, Michael的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Molloy, Michael', 18)}}的其他基金
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2019-06522 - 财政年份:2022
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2019-06522 - 财政年份:2021
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2019-06522 - 财政年份:2020
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2014-03858 - 财政年份:2018
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2014-03858 - 财政年份:2017
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2014-03858 - 财政年份:2016
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2014-03858 - 财政年份:2015
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2014-03858 - 财政年份:2014
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic graph theory and theoretical computer science
概率图论和理论计算机科学
- 批准号:
184038-2009 - 财政年份:2013
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic graph theory and theoretical computer science
概率图论和理论计算机科学
- 批准号:
184038-2009 - 财政年份:2012
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
相似国自然基金
基于Graph-PINN的层结稳定度参数化建模与沙尘跨介质耦合传输模拟研
- 批准号:
- 批准年份:2025
- 资助金额:0.0 万元
- 项目类别:省市级项目
平面三角剖分flip graph的强凸性研究
- 批准号:12301432
- 批准年份:2023
- 资助金额:30.00 万元
- 项目类别:青年科学基金项目
基于graph的多对比度磁共振图像重建方法
- 批准号:61901188
- 批准年份:2019
- 资助金额:24.5 万元
- 项目类别:青年科学基金项目
基于de bruijn graph梳理的宏基因组拼接算法开发
- 批准号:61771009
- 批准年份:2017
- 资助金额:50.0 万元
- 项目类别:面上项目
基于Graph和ISA的红外目标分割与识别方法研究
- 批准号:61101246
- 批准年份:2011
- 资助金额:22.0 万元
- 项目类别:青年科学基金项目
中国Web Graph的挖掘与应用研究
- 批准号:60473122
- 批准年份:2004
- 资助金额:23.0 万元
- 项目类别:面上项目
相似海外基金
Developing quantum probabilistic approach to spectral graph theory and multi-variate orthogonal polynomials
开发谱图理论和多元正交多项式的量子概率方法
- 批准号:
23K03126 - 财政年份:2023
- 资助金额:
$ 2.99万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2019-06522 - 财政年份:2022
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2019-06522 - 财政年份:2021
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2019-06522 - 财政年份:2020
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2014-03858 - 财政年份:2018
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2014-03858 - 财政年份:2017
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2014-03858 - 财政年份:2016
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2014-03858 - 财政年份:2015
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
- 批准号:
RGPIN-2014-03858 - 财政年份:2014
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual