Markov Chain Algorithms for Problems from Computer Science and Statistical Physics
用于计算机科学和统计物理问题的马尔可夫链算法
基本信息
- 批准号:0505505
- 负责人:
- 金额:$ 18万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2005
- 资助国家:美国
- 起止时间:2005-09-15 至 2009-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
This proposal focuses on the connections between the efficiency of algorithms and phase transitions in related physical systems. Arguments for showing slow mixing, or the inefficiency, of Markov chains and the presence of phase transitions typically rely on sophisticated counting arguments. A new approach based on topological obstructions is suggested that would greatly simplify these arguments and moreover would strengthen known results. This will be explored in the context of independent sets and colorings in fixed dimensional lattices. A related topic examined in this proposal concerns the effects of boundary conditions on the mixing rates of certain Markov chains. Boundary conditions play a crucial role in the study of phase transitions of statistical physics models on the infinite lattice, so understanding their influence on the mixing rate of finite chains could provide insights for both the design of algorithms and the behavior of the underlying systems.Over the last ten years, a new interdisciplinary field has emerged at the interface of discrete probability, computer science and statistical physics. The research component of this proposal explores new directions for enhancing the connections between these fields in order to design better algorithms and study phase transitions of physical systems. Many of the questions posed, and the technical tools suggested for their solutions, are the result of a bilateral interplay between fields. This research will be supplemented through an educational component. Starting in Fall 2006, the P.I. will be chairing the organizing committee of a DIMACS/Georgia Tech special focus on "Discrete Random Systems," concentrating on this area of interdisciplinary research. In addition to the typical workshops bringing together leading researchers in the relevant areas, there will also be workshops and working groups promoting broader impact, both in terms of participants and topics. Tutorials will be included when beneficial.
该提案重点关注算法效率与相关物理系统中相变之间的联系。 显示马尔可夫链的缓慢混合或低效率以及相变的存在的论据通常依赖于复杂的计数论据。 提出了一种基于拓扑障碍的新方法,该方法将大大简化这些论点,而且会加强已知的结果。这将在固定维晶格中的独立集和着色的背景下进行探索。 该提案中研究的一个相关主题涉及边界条件对某些马尔可夫链混合率的影响。 边界条件在无限晶格统计物理模型的相变研究中起着至关重要的作用,因此了解它们对有限链混合率的影响可以为算法设计和底层系统的行为提供见解。过去十年,离散概率、计算机科学和统计物理学的交叉领域出现了一个新的跨学科领域。 该提案的研究部分探索了增强这些领域之间联系的新方向,以便设计更好的算法并研究物理系统的相变。 提出的许多问题以及为解决这些问题而建议的技术工具都是领域之间双边相互作用的结果。 这项研究将通过教育部分得到补充。 从 2006 年秋季开始,P.I.将担任 DIMACS/佐治亚理工学院组委会主席,该活动特别关注“离散随机系统”,专注于这一跨学科研究领域。 除了汇集相关领域领先研究人员的典型研讨会外,还将举办研讨会和工作组,在参与者和主题方面促进更广泛的影响。 有益时将包括教程。
项目成果
期刊论文数量(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 }}
Dana Randall其他文献
Mixing [Markov chain]
混合[马尔可夫链]
- DOI:
10.1109/sfcs.2003.1238175 - 发表时间:
2003-10-20 - 期刊:
- 影响因子:0
- 作者:
Dana Randall - 通讯作者:
Dana Randall
Socioeconomic Clustering and Racial Segregation on Lattices with Heterogeneous Sites
异质点格子上的社会经济集群和种族隔离
- DOI:
- 发表时间:
2021 - 期刊:
- 影响因子:0
- 作者:
Zhanzhan Zhao;Dana Randall - 通讯作者:
Dana Randall
Phase coexistence and torpid mixing in the 3-coloring model on ℤd
ℤd 上 3 着色模型中的相共存和呆滞混合
- DOI:
10.1137/12089538x - 发表时间:
2012-10-16 - 期刊:
- 影响因子:0
- 作者:
David J. Galvin;J. Kahn;Dana Randall;G. Sorkin - 通讯作者:
G. Sorkin
Convergence rates of Markov chains for some self-assembly and non-saturated Ising models
一些自组装和非饱和伊辛模型的马尔可夫链的收敛率
- DOI:
- 发表时间:
2009 - 期刊:
- 影响因子:1.1
- 作者:
Sam Greenberg;Dana Randall - 通讯作者:
Dana Randall
Mixing times of Markov chains on 3-Orientations of Planar Triangulations
平面三角剖分 3 方向上马尔可夫链的混合时间
- DOI:
- 发表时间:
2012 - 期刊:
- 影响因子:0
- 作者:
S. Miracle;Dana Randall;A. Streib;P. Tetali - 通讯作者:
P. Tetali
Dana Randall的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Dana Randall', 18)}}的其他基金
Collaborative Research: AF: Medium: Markov Chain Algorithms for Problems from Computer Science, Statistical Physics and Self-Organizing Particle Systems
合作研究:AF:中:计算机科学、统计物理和自组织粒子系统问题的马尔可夫链算法
- 批准号:
2106687 - 财政年份:2021
- 资助金额:
$ 18万 - 项目类别:
Continuing Grant
AiTF: Collaborative Research: Distributed and Stochastic Algorithms for Active Matter: Theory and Practice
AiTF:协作研究:活跃物质的分布式随机算法:理论与实践
- 批准号:
1733812 - 财政年份:2018
- 资助金额:
$ 18万 - 项目类别:
Standard Grant
TRIPODS+X: VIS: Creating an Annual Data Science Forum
TRIPODS X:VIS:创建年度数据科学论坛
- 批准号:
1839340 - 财政年份:2018
- 资助金额:
$ 18万 - 项目类别:
Standard Grant
Conference: Machine Learning in Science and Engineering
会议:科学与工程中的机器学习
- 批准号:
1822279 - 财政年份:2018
- 资助金额:
$ 18万 - 项目类别:
Standard Grant
AitF: Collaborative Research: A Distributed and Stochastic Algorithmic Framework for Active Matter
AitF:协作研究:活性物质的分布式随机算法框架
- 批准号:
1637031 - 财政年份:2016
- 资助金额:
$ 18万 - 项目类别:
Standard Grant
AF: Small: Markov Chain Algorithms for Problems from Computer Science and Statistical Physics
AF:小:计算机科学和统计物理问题的马尔可夫链算法
- 批准号:
1526900 - 财政年份:2015
- 资助金额:
$ 18万 - 项目类别:
Standard Grant
AF: Markov Chain Algorithms for Problems from Computer Science, Statistical Physics and Economics
AF:计算机科学、统计物理和经济学问题的马尔可夫链算法
- 批准号:
1219020 - 财政年份:2012
- 资助金额:
$ 18万 - 项目类别:
Standard Grant
Markov Chain Algorithms for Problems from Computer Science and Statistical Physics
用于计算机科学和统计物理问题的马尔可夫链算法
- 批准号:
0830367 - 财政年份:2008
- 资助金额:
$ 18万 - 项目类别:
Continuing Grant
Analysis of Markov Chains and Algorithms for Ad-Hoc Networks
Ad-Hoc 网络的马尔可夫链和算法分析
- 批准号:
0515105 - 财政年份:2005
- 资助金额:
$ 18万 - 项目类别:
Standard Grant
Markov Chain Algorithms for Computational Problems from Physics and Biology
用于物理和生物学计算问题的马尔可夫链算法
- 批准号:
0105639 - 财政年份:2001
- 资助金额:
$ 18万 - 项目类别:
Continuing Grant
相似国自然基金
大规模动态模态分解中的张量方法
- 批准号:11801479
- 批准年份:2018
- 资助金额:22.0 万元
- 项目类别:青年科学基金项目
基于交互式马尔可夫链的列车运行控制系统安全通信实时性的研究
- 批准号:61703028
- 批准年份:2017
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
心理与教育测量中项目反应时间数据的统计建模及其应用
- 批准号:11501094
- 批准年份:2015
- 资助金额:18.0 万元
- 项目类别:青年科学基金项目
偏振光模式产生与传输过程中的统计特性与可计算性研究
- 批准号:61271121
- 批准年份:2012
- 资助金额:68.0 万元
- 项目类别:面上项目
柔性Job Shop生产调度和预防性维护计划集成模型和优化方法研究
- 批准号:71171149
- 批准年份:2011
- 资助金额:34.2 万元
- 项目类别:面上项目
相似海外基金
EAGER: Search-Accelerated Markov Chain Monte Carlo Algorithms for Bayesian Neural Networks and Trillion-Dimensional Problems
EAGER:贝叶斯神经网络和万亿维问题的搜索加速马尔可夫链蒙特卡罗算法
- 批准号:
2404989 - 财政年份:2024
- 资助金额:
$ 18万 - 项目类别:
Standard Grant
CAREER: Scalable and Robust Uncertainty Quantification using Subsampling Markov Chain Monte Carlo Algorithms
职业:使用子采样马尔可夫链蒙特卡罗算法进行可扩展且稳健的不确定性量化
- 批准号:
2340586 - 财政年份:2024
- 资助金额:
$ 18万 - 项目类别:
Continuing Grant
CAREER: Towards Tight Guarantees of Markov Chain Sampling Algorithms in High Dimensional Statistical Inference
职业:高维统计推断中马尔可夫链采样算法的严格保证
- 批准号:
2237322 - 财政年份:2023
- 资助金额:
$ 18万 - 项目类别:
Continuing Grant
Bayesian Modeling and Inference for High-Dimensional Disease Mapping and Boundary Detection"
用于高维疾病绘图和边界检测的贝叶斯建模和推理”
- 批准号:
10568797 - 财政年份:2023
- 资助金额:
$ 18万 - 项目类别:
Bayesian modeling of multivariate mixed longitudinal responses with scale mixtures of multivariate normal distributions
具有多元正态分布尺度混合的多元混合纵向响应的贝叶斯建模
- 批准号:
10730714 - 财政年份:2023
- 资助金额:
$ 18万 - 项目类别: