BSF:2014359:Invariance in error correcting codes and computational complexity

BSF:2014359:纠错码和计算复杂度的不变性

基本信息

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

项目摘要

Information can be digitally encoded (as 0s and 1s) so that even if some of these bits are lost or modified, the information can be recovered. This foundational idea, which is the basis for such commonplace technologies as DVDs and digital broadcast, is explored in theoretical computer science, where it plays a key role in probabilistically checkable proofs and property testing. Exploring the limits of this idea in these abstract settings can lead to new understanding, which enables technological innovation. It has been long known in mathematics that studying the invariances (symmetries) of an object has an important role in understanding the object. In recent years, the study of invariances has led to some significant advances in various topics in theoretical computer science, such as property testing, error-correcting codes and complexity theory. For example, codes with affine invariance and codes with a transitive invariance group have been shown to have important applications in complexity theory, such as constructing PCPs. This project will support the travel of the PIs and their students for research collaborations on these topics with collaborators in Israel. This research will deepen our understanding of objects with invariances, and develop new applications of this theory in complexity theory.
信息可以进行数字编码(如 0 和 1),这样即使其中一些位丢失或修改,信息也可以恢复。 这一基本思想是 DVD 和数字广播等常见技术的基础,在理论计算机科学中得到了探索,在概率可检查证明和属性测试中发挥着关键作用。 在这些抽象环境中探索这个想法的局限性可以带来新的理解,从而实现技术创新。数学界早已知道,研究对象的不变性(对称性)对于理解该对象具有重要作用。近年来,不变性的研究在理论计算机科学的各个主题中取得了一些重大进展,例如属性测试、纠错码和复杂性理论。 例如,具有仿射不变性的代码和具有传递不变性群的代码已被证明在复杂性理论中具有重要的应用,例如构造 PCP。 该项目将支持 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 }}

Swastik Kopparty其他文献

Guest Column: Local Testing and Decoding of High-Rate Error-Correcting Codes
嘉宾专栏:高速率纠错码的本地测试与解码
  • DOI:
    10.1145/2993749.2993761
  • 发表时间:
    2016
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Swastik Kopparty;Shubhangi Saraf
  • 通讯作者:
    Shubhangi Saraf
Robust positioning patterns
稳健的定位模式
  • DOI:
    10.1137/1.9781611974331.ch136
  • 发表时间:
    2016
  • 期刊:
  • 影响因子:
    0
  • 作者:
    R. Berkowitz;Swastik Kopparty
  • 通讯作者:
    Swastik Kopparty
Lecture 4 : AC 0 lower bounds and pseudorandomness
第 4 讲:AC 0 下界和伪随机性
  • DOI:
  • 发表时间:
    2013
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Swastik Kopparty;B. Garnett
  • 通讯作者:
    B. Garnett
Tolerant Linearity Testing and Locally Testable Codes
公差线性测试和本地可测试代码
High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
具有次多项式查询复杂度的高速本地可校正和本地可测试代码
  • DOI:
    10.1145/3051093
  • 发表时间:
    2017
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Swastik Kopparty;Or Meir;Noga Ron;Shubhangi Saraf
  • 通讯作者:
    Shubhangi Saraf

Swastik Kopparty的其他文献

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

{{ truncateString('Swastik Kopparty', 18)}}的其他基金

CAREER: Error-Correcting Codes, Complexity Theory and Pseudorandomness
职业:纠错码、复杂性理论和伪随机性
  • 批准号:
    1253886
  • 财政年份:
    2013
  • 资助金额:
    $ 4万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了