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