New Applications of Error-Correcting Codes in Complexity and Algorithms

纠错码在复杂性和算法方面的新应用

基本信息

  • 批准号:
    0830787
  • 负责人:
  • 金额:
    $ 37.5万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    2008
  • 资助国家:
    美国
  • 起止时间:
    2008-09-01 至 2012-08-31
  • 项目状态:
    已结题

项目摘要

Computational Complexity excels at posing fundamental questions with far-reaching consequences regarding the nature of computation, but so far it has been not nearly as successful at answering them. To propel the field forward, broadly useful tools and techniques must be cultivated, and new ones invented.This project aims to significantly broaden the reach of error-correcting codes as a powerful tool to attack central problems in Complexity (and one fundamental problem in Algorithms). Error-correcting codes lie at the core of some of the deepest results in Complexity; recent developments in the area reveal possible routes to a number of further breakthroughs.The PI will pursue research organized in the following threethrusts: (1) developing a generalization of Parvaresh-Vardy codes possessing a crucial feature -- local decodability -- often exploited in Complexity applications, with applications to derandomization and surrounding problems; (2) devising a real analog of error-correcting codes possessing an approximate version of the defining feature of error-correcting codes -- that two codewords that differ in one coordinate must differ in most coordinates -- with a concrete application to proving circuit lower bounds in the complexity class MA; and (3) utilizing error-correcting codes to bridge the gap between "approximate" and exact algorithms for matrix multiplication, with the intention of obtaining an optimal algorithm for matrix multiplication using a group-theoretic approach developed by the PI and coauthors.The overall goal is to develop new tools and techniques around error-correcting codes, while attacking well-motivated and significant problems in different application domains. Resolving fundamental problems in Complexity and Algorithms in turn enhances our understanding and mastery of efficient computation.
计算复杂性擅长提出对计算本质具有深远影响的基本问题,但到目前为止,它在回答这些问题方面还没有那么成功。为了推动这一领域的发展,必须培育广泛有用的工具和技术,并发明新的工具和技术。该项目旨在显着扩大纠错码的范围,将其作为解决复杂性核心问题(以及算法中的一个基本问题)的有力工具。 )。纠错码是复杂性中一些最深刻结果的核心。该领域的最新进展揭示了取得进一步突破的可能途径。PI 将开展以下三个方向的研究:(1) 开发 Parvaresh-Vardy 代码的泛化,该代码具有一个关键特征——本地可解码性——通常在复杂性应用,包括去随机化和周围问题的应用; (2)设计一种纠错码的真实模拟,具有纠错码定义特征的近似版本——在一个坐标上不同的两个码字在大多数坐标上必定不同——并具体应用于证明电路下限复杂度等级 MA 的界限; (3)利用纠错码来弥合矩阵乘法的“近似”算法和精确算法之间的差距,目的是使用 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 }}

Christopher Umans其他文献

Pseudorandomness for Approximate Counting and Sampling
近似计数和采样的伪随机性
  • DOI:
  • 发表时间:
    2006
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Ronen Shaltiel;Christopher Umans
  • 通讯作者:
    Christopher Umans

Christopher Umans的其他文献

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

{{ truncateString('Christopher Umans', 18)}}的其他基金

AF: Small: Group Theory and Representation Theory in Matrix Multiplication and Generalized DFTs
AF:小:矩阵乘法和广义 DFT 中的群论和表示论
  • 批准号:
    1815607
  • 财政年份:
    2018
  • 资助金额:
    $ 37.5万
  • 项目类别:
    Standard Grant
AF: Small: Algorithms for Matrix Multiplication, Polynomial Factorization and Generalized Fourier Transform
AF:小:矩阵乘法、多项式分解和广义傅立叶变换算法
  • 批准号:
    1423544
  • 财政年份:
    2014
  • 资助金额:
    $ 37.5万
  • 项目类别:
    Standard Grant
AF: Small: Algebraic Methods for Core Problems in Algorithms and Complexity
AF:小:算法和复杂性核心问题的代数方法
  • 批准号:
    1116111
  • 财政年份:
    2011
  • 资助金额:
    $ 37.5万
  • 项目类别:
    Standard Grant
CAREER: Research in Complexity Theory with Applications
职业:复杂性理论及其应用研究
  • 批准号:
    0346991
  • 财政年份:
    2004
  • 资助金额:
    $ 37.5万
  • 项目类别:
    Continuing Grant

相似国自然基金

英文专著《FRACTIONAL INTEGRALS AND DERIVATIVES: Theory and Applications》的翻译
  • 批准号:
    12126512
  • 批准年份:
    2021
  • 资助金额:
    12.0 万元
  • 项目类别:
    数学天元基金项目
基于多源时空大数据驱动的广海域船联网数据传输算法研究
  • 批准号:
    61902367
  • 批准年份:
    2019
  • 资助金额:
    27.0 万元
  • 项目类别:
    青年科学基金项目
基于时空数据的多平台用户连接关键技术研究
  • 批准号:
    61902270
  • 批准年份:
    2019
  • 资助金额:
    25.0 万元
  • 项目类别:
    青年科学基金项目
超空间众包数据管理关键技术
  • 批准号:
    61902023
  • 批准年份:
    2019
  • 资助金额:
    28.0 万元
  • 项目类别:
    青年科学基金项目
空间约束的在线包组推荐优化与公平性研究
  • 批准号:
    61862013
  • 批准年份:
    2018
  • 资助金额:
    37.0 万元
  • 项目类别:
    地区科学基金项目

相似海外基金

Access for All in ALS (ALL ALS) West Clinical Coordinating Center
ALS 所有人 (ALL ALS) 西部临床协调中心
  • 批准号:
    10878596
  • 财政年份:
    2023
  • 资助金额:
    $ 37.5万
  • 项目类别:
New Theoretical Foundations of Tensor Applications: Clustering, Error Analysis, Global Convergence, and Robust Formulations
张量应用的新理论基础:聚类、误差分析、全局收敛和鲁棒公式
  • 批准号:
    0917274
  • 财政年份:
    2009
  • 资助金额:
    $ 37.5万
  • 项目类别:
    Standard Grant
Washington Obstetric-Fetal Pharmacology Research Unit
华盛顿产胎儿药理学研究单位
  • 批准号:
    7695403
  • 财政年份:
    2004
  • 资助金额:
    $ 37.5万
  • 项目类别:
New High-Resolution Semi-Discrete Central Schemes: Derivation, Applications and Local Error Analysis
新的高分辨率半离散中心方案:推导、应用和局部误差分析
  • 批准号:
    0196439
  • 财政年份:
    2001
  • 资助金额:
    $ 37.5万
  • 项目类别:
    Standard Grant
New High-Resolution Semi-Discrete Central Schemes: Derivation, Applications and Local Error Analysis
新的高分辨率半离散中心方案:推导、应用和局部误差分析
  • 批准号:
    0073631
  • 财政年份:
    2000
  • 资助金额:
    $ 37.5万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了