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

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

• 批准号: 1540634
• 负责人: Swastik Kopparty
• 金额: $ 4万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1540634&HistoricalAwards=false
• 关键词: BSF; 2014359; Invariance; error; correcting

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.

信息可以数字编码（AS 0和1），以便即使其中一些位丢失或修改，也可以恢复信息。 在理论计算机科学中探讨了这种基本思想，它是DVD和数字广播等常见技术的基础，在理论计算机科学中，它在概率可检查的证明和属性测试中起着关键作用。 在这些抽象环境中探索这个想法的局限性可能会带来新的理解，从而实现技术创新。长期以来，在数学上已经知道，研究对象的不变（对称性）在理解对象方面具有重要作用。近年来，对不变的研究导致了理论计算机科学的各种主题的一些重大进步，例如属性测试，错误纠正验证代码和复杂性理论。 例如，具有仿射不变性的代码和具有及传递不变性组的代码已显示在复杂性理论中具有重要的应用，例如构建PCP。 该项目将支持PIS及其学生与以色列合作者有关这些主题的研究合作。这项研究将加深我们对物体的理解，并在复杂性理论中发展该理论的新应用。