AF: Medium: Collaborative Research: Information Compression in Algorithm Design and Statistical Physics

AF:媒介:协作研究:算法设计和统计物理中的信息压缩

基本信息

项目摘要

The existence of connections between probabilistic algorithms, statistical physics and information theory has been known for decades and has yielded a number of unexpected breakthroughs. Recent discoveries of the PIs and other researchers give clear indications that these connections go much deeper than previously thought. A key new idea is the realization that stochastic local search algorithms can be judged by their capacity to compress the randomness they consume, with convergence following as a consequence of compressibility. Further exploration of this idea is expected to have significant impact, both conceptual and technical, in multiple scientific fields. This includes algorithm design by information theoretic methods, the study of phase transitions in statistical mechanical systems based on information bottleneck arguments, and non-constructive proofs of existence of combinatorial objects. The project will offer a wide range of research opportunities at various levels of sophistication for graduate and undergraduate students in three state universities.Information compression arguments have recently found striking applications in computer science and combinatorics. A glowing example is Moser's proof of the algorithmic Lovasz Local Lemma, which suggested an entirely new way of reasoning about randomized algorithms. Inspired by the work of Moser, one of the PIs with a collaborator has very recently created a general framework for analyzing stochastic local search algorithms using information compression. The framework is purely algorithmic, completely bypassing the Probabilistic Method. Besides helping to analyze the running times of existing algorithms it can also be used as a powerful new tool for designing novel, non-obvious randomized algorithms. The proposed research further develops this framework with the aim of unearthing completely new applications in computer science and combinatorics, while establishing mathematically rigorous connections to statistical physics. Concrete examples of such applications to be investigated include new tools for bounding the mixing time of Markov chains and algebraic connections between randomized algorithms and the classical theory of phase transitions in statistical physics.
概率算法、统计物理学和信息论之间的联系已经存在了几十年,并取得了一些意想不到的突破。PI和其他研究人员最近的发现清楚地表明,这些联系比以前认为的要深刻得多。一个关键的新思想是实现随机局部搜索算法可以通过它们压缩它们消耗的随机性的能力来判断,收敛性是可压缩性的结果。对这一想法的进一步探索预计将在多个科学领域产生重大的概念和技术影响。这包括信息理论方法的算法设计,基于信息瓶颈参数的统计力学系统中的相变研究,以及组合对象存在的非构造性证明。该项目将为三所州立大学的研究生和本科生提供各种复杂程度的广泛研究机会。信息压缩论点最近在计算机科学和组合学中得到了惊人的应用。一个光辉的例子是莫泽对算法的洛瓦兹局部引理的证明,它提出了一种全新的推理随机算法的方法。受Moser工作的启发,其中一个PI与合作者最近创建了一个通用框架,用于分析使用信息压缩的随机局部搜索算法。该框架是纯粹的算法,完全绕过概率方法。除了帮助分析现有算法的运行时间外,它还可以用作设计新颖、非显而易见的随机算法的强大新工具。拟议的研究进一步发展了这一框架,旨在发掘计算机科学和组合学中全新的应用,同时建立与统计物理学的数学严格联系。具体的例子,这样的应用程序进行调查,包括新的工具,为边界的混合时间的马尔可夫链和代数之间的连接随机算法和经典理论的相变统计物理。

项目成果

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

Jose Garcia-Luna-Aceves其他文献

Jose Garcia-Luna-Aceves的其他文献

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

{{ truncateString('Jose Garcia-Luna-Aceves', 18)}}的其他基金

AitF: Collaborative Research: Efficient High-Dimensional Integration using Error-Correcting Codes
AitF:协作研究:使用纠错码进行高效高维积分
  • 批准号:
    1733884
  • 财政年份:
    2017
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Standard Grant
Many-to-Many Communication for Scalable Ad Hoc Networks
可扩展自组织网络的多对多通信
  • 批准号:
    0729230
  • 财政年份:
    2007
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Standard Grant
NeTS-ProWiN: Spectrum-Agile Wireless Available Networking (SWAN)
NetS-ProWiN:频谱敏捷无线可用网络 (SWAN)
  • 批准号:
    0435522
  • 财政年份:
    2004
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Standard Grant

相似海外基金

Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
  • 批准号:
    2402836
  • 财政年份:
    2024
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
  • 批准号:
    2402851
  • 财政年份:
    2024
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
  • 批准号:
    2422926
  • 财政年份:
    2024
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
  • 批准号:
    2402283
  • 财政年份:
    2024
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
  • 批准号:
    2402852
  • 财政年份:
    2024
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
  • 批准号:
    2402284
  • 财政年份:
    2024
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
  • 批准号:
    2402837
  • 财政年份:
    2024
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
  • 批准号:
    2402835
  • 财政年份:
    2024
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Adventures in Flatland: Algorithms for Modern Memories
合作研究:AF:媒介:平地历险记:现代记忆算法
  • 批准号:
    2423105
  • 财政年份:
    2024
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Sketching for privacy and privacy for sketching
合作研究:AF:中:为隐私而素描和为素描而隐私
  • 批准号:
    2311649
  • 财政年份:
    2023
  • 资助金额:
    $ 45.2万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了