Approximate Counting, Statistical Physics and Computation

近似计数、统计物理与计算

基本信息

  • 批准号:
    0635153
  • 负责人:
  • 金额:
    $ 33万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2007
  • 资助国家:
    美国
  • 起止时间:
    2007-02-01 至 2011-01-31
  • 项目状态:
    已结题

项目摘要

AbstractThe project contains two main themes that are related in various ways:(1) approximation algorithms for counting problems, and (2) computational aspects of statistical physics. Counting problems arise in numerous application areas, including combinatorics, algebra, volume and integration, statistical physics, computational finance and statistical hypothesis testing. In almost all cases they are intractable in exact form; theme (1) of the project is focused on constructing efficient algorithms for these problems that guarantee any desired degree of approximation. Theme (2) of the project aims to better understand deep emerging connections between phase transitions in physical systems on the one hand, and computational complexity or the running time of algorithms on the other. The two themes are united by various algorithmic and mathematical techniques (notably, the Markov chain Monte Carlo paradigm). In addition, there is a focus in the project on the application of ideas from theoretical Computer Science to problems in other sciences.Specific goals of theme (1) include the following: to resolve the status of a number of important counting problems, either by developing efficient approximation algorithms or by proving them hard to approximate; to construct more efficient approximation algorithms for central problems in the field; and to explore novel application areas such as computational finance. Specific topics to be addressed within theme (2) include the mixing time of Glauber dynamics; the behavior of message-passing algorithms such as Belief Propagation; and connections between physical models and random constraint satisfaction problems.
摘要该项目包含两个以各种方式相关的主题:(1)计数问题的近似算法,以及(2)统计物理的计算方面。 计数问题出现在许多应用领域,包括组合学、代数、体积和积分、统计物理、计算金融和统计假设检验。 几乎在所有情况下,它们的精确形式都是难以处理的。该项目的主题 (1) 侧重于为这些问题构建有效的算法,以保证任何所需的近似程度。 该项目的主题(2)旨在一方面更好地理解物理系统中相变之间的深层联系,另一方面理解计算复杂性或算法的运行时间。 这两个主题通过各种算法和数学技术(特别是马尔可夫链蒙特卡罗范式)统一起来。 此外,该项目的重点是将理论计算机科学的思想应用于其他科学的问题。主题(1)的具体目标包括以下内容:解决许多重要计数问题的现状,或者通过开发有效的近似算法或证明它们难以近似;为该领域的中心问题构建更有效的近似算法;并探索计算金融等新的应用领域。 主题(2)中要讨论的具体主题包括格劳伯动力学的混合时间;消息传递算法的行为,例如置信传播;以及物理模型和随机约束满足问题之间的联系。

项目成果

期刊论文数量(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 }}

Alistair Sinclair其他文献

Algorithms for Random Generation and Counting: A Markov Chain Approach
  • DOI:
    10.1007/978-1-4612-0323-0
  • 发表时间:
    1993-02
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Alistair Sinclair
  • 通讯作者:
    Alistair Sinclair
Physical chemical properties and antioxidant capacities of grapefruit juice (Citrus paradisi) extracted from two different varieties
两种不同品种提取的柚子汁(Citrus paradisi)的物理化学特性和抗氧化能力
  • DOI:
  • 发表时间:
    2018
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Alistair Sinclair
  • 通讯作者:
    Alistair Sinclair
Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow ( Extended Abstract )
马尔可夫链和多商品流混合率的改进界限(扩展摘要)
  • DOI:
  • 发表时间:
    1992
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Alistair Sinclair
  • 通讯作者:
    Alistair Sinclair
Embedding k-Outerplanar Graphs into l 1
将 k 外平面图嵌入到 l 1 中
  • DOI:
    10.1137/s0895480102417379
  • 发表时间:
    2006
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Chandra Chekuri;Anupam Gupta;Ilan Newman;Yuri Rabinovich;Alistair Sinclair
  • 通讯作者:
    Alistair Sinclair
R eport on BCTCS 2009
2009 年 BCTCS 报告
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    A. Czumaj;Sara Kalvala;Steven Matthews;Alistair Sinclair;J. Hillston
  • 通讯作者:
    J. Hillston

Alistair Sinclair的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Alistair Sinclair', 18)}}的其他基金

AF: Small: Markov Chains and Mass Action Kinetics
AF:小:马尔可夫链和质量作用动力学
  • 批准号:
    2231095
  • 财政年份:
    2023
  • 资助金额:
    $ 33万
  • 项目类别:
    Standard Grant
AF: Small: Approximate Counting, Stochastic Local Search and Nonlinear Dynamics
AF:小:近似计数、随机局部搜索和非线性动力学
  • 批准号:
    1815328
  • 财政年份:
    2018
  • 资助金额:
    $ 33万
  • 项目类别:
    Standard Grant
AF: Medium: Collaborative Research: Information Compression in Algorithm Design and Statistical Physics
AF:媒介:协作研究:算法设计和统计物理中的信息压缩
  • 批准号:
    1514434
  • 财政年份:
    2015
  • 资助金额:
    $ 33万
  • 项目类别:
    Standard Grant
AF: Small: Random Processes, Statistical Physics and Computation
AF:小:随机过程、统计物理和计算
  • 批准号:
    1420934
  • 财政年份:
    2014
  • 资助金额:
    $ 33万
  • 项目类别:
    Standard Grant
AF: Small: Markov Chains, Statistical Physics, and Mobile Geometric Graphs
AF:小:马尔可夫链、统计物理和移动几何图
  • 批准号:
    1016896
  • 财政年份:
    2010
  • 资助金额:
    $ 33万
  • 项目类别:
    Standard Grant
ITR/SY: Discrete Models & Algorithms in the Sciences
ITR/SY:离散模型
  • 批准号:
    0121555
  • 财政年份:
    2001
  • 资助金额:
    $ 33万
  • 项目类别:
    Continuing Grant
A Proposal for Research on Markov Chains, Approximate Counting and Finite Metric Spaces
关于马尔可夫链、近似计数和有限度量空间的研究建议
  • 批准号:
    9820951
  • 财政年份:
    1999
  • 资助金额:
    $ 33万
  • 项目类别:
    Continuing Grant
A Proposal for Research on Random Processes and Algorithms
随机过程和算法研究的提案
  • 批准号:
    9505448
  • 财政年份:
    1995
  • 资助金额:
    $ 33万
  • 项目类别:
    Continuing Grant

相似国自然基金

删失面板计数数据的统计分析
  • 批准号:
    12271459
  • 批准年份:
    2022
  • 资助金额:
    46 万元
  • 项目类别:
    面上项目
复杂面板计数数据的建模和有效统计推断
  • 批准号:
    12171374
  • 批准年份:
    2021
  • 资助金额:
    51 万元
  • 项目类别:
    面上项目
中国与贸易伙伴贸易统计数据差异:基于企业错报动机的研究
  • 批准号:
  • 批准年份:
    2020
  • 资助金额:
    24 万元
  • 项目类别:
    青年科学基金项目
组合计数与组合统计量分布问题的研究
  • 批准号:
  • 批准年份:
    2020
  • 资助金额:
    51 万元
  • 项目类别:
    面上项目
协同VIIRS时序遥感影像与统计数据的农作物丰度提取方法研究
  • 批准号:
    41901380
  • 批准年份:
    2019
  • 资助金额:
    25.0 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

CAREER: New methods in curve counting
职业:曲线计数的新方法
  • 批准号:
    2422291
  • 财政年份:
    2024
  • 资助金额:
    $ 33万
  • 项目类别:
    Continuing Grant
Development of highly efficient and stable photon-counting type X-ray detectors using single crystal metal halide perovskite semiconductors
利用单晶金属卤化物钙钛矿半导体开发高效稳定的光子计数型X射线探测器
  • 批准号:
    24K15592
  • 财政年份:
    2024
  • 资助金额:
    $ 33万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Photon counting CTによるエンドリークの詳細評価および臨床的有用性の検証
使用光子计数 CT 详细评估内漏并验证临床有效性
  • 批准号:
    24K18761
  • 财政年份:
    2024
  • 资助金额:
    $ 33万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
Counting neutrinos to per-mill accuracy
计算中微子的精确度
  • 批准号:
    DP240103130
  • 财政年份:
    2024
  • 资助金额:
    $ 33万
  • 项目类别:
    Discovery Projects
Foundations of Anonymous Dynamic Networks
匿名动态网络的基础
  • 批准号:
    23K10985
  • 财政年份:
    2023
  • 资助金额:
    $ 33万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了