Unusual Error Correcting Codes

异常纠错码

• 批准号: 0105692
• 负责人: Mario Szegedy
• 金额: $ 26.05万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-07-01 至 2006-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0105692&HistoricalAwards=false
• 关键词: Unusual; Error; Correcting; Codes

Error correcting codes were originally invented to increase theprecision of retrieval, storage and communication of data.The investigator's goal is to study and develop codeswith new features added on top of the error correcting property,such as checkability, identifiable parent property (IPP), orquantum-error correcting property. In spite of theimportance of designing codes with added features,there has not ben a comprehensive study of them up to date, and eachdesign is treated as an isolated case. The investigatorwants to put the designs under one umbrella (wheneverit is possible) so that their propertiescan be compared and further improved upon.Among the benefits such improvement can bring aboutare better non-approximability results in complexity theory,better means to trace pirates of electronic images,and new algorithms for quantum computers.The investigator was the first toobserve that constructs in the theory of probabilistically checkableproofs can be viewed as error correcting codes with added features.The best parameters for these codes and their kins arestill not known, and they are the primarytargets of the proposed investigation in the first year.The investigator also plans for a study thatwould lead to a general checkability theorem for product codes,with a surprise application in circuit complexity,and recommends a simplified look at Raz's parallel repetitiontheorem. A different thread of the the proposed researchis motivated by questions about schemesthat protect a multi-media publisher against piracy ofelectronic images. The publisher can use words of a codeto mark electronic copies of an image. Then, if the code isappropriately designed, any image forged by combining pieces of two legallytraded images, contains sufficient amount of information to tracethe identity of at least one of the source (parent) images.Here the problem is to build efficient codes that can identify one ofthree or more source images. Other research targets includeefficiently decodable quantum codes, andcomplexity lower bounds for dynamic problems via unusual codes.There is a general framework in whichthe investigator plans to do the research. This entails:1. The study and exploration of the relation inbetween different unusual codes;2. Their classification and axiomatization;3. Search for novel applications of unusual codesin the theories of lower bounds and pseudo-randomness,and in other walks of computer science;4. Building a 'family tree' of code properties, and finding a matchin between properties and applications.The methodology should embrace and extend classical coding theory.

纠错码最初是为了提高数据的检索、存储和通信的精度而发明的，研究者的目标是研究和开发在纠错特性之上添加新特性的码，如可校验性、可识别父属性（IPP）或量子纠错特性。尽管设计具有附加功能的代码的重要性，但迄今为止还没有对它们进行全面的研究，并且每个设计都被视为孤立的情况。设计师想把这些设计放在一个保护伞下（只要有可能），以便它们的性质可以进行比较和进一步改进。这种改进可以带来的好处包括复杂性理论中更好的非近似性结果，更好的追踪电子图像盗版的手段，以及量子计算机的新算法。研究者是第一个观察到概率可检验证明理论中的结构可以被视为作为具有附加功能的纠错码。这些码及其同类的最佳参数仍然未知，它们是第一年拟议调查的主要目标。调查员还计划进行一项研究，该研究将导致乘积码的一般可检查性定理，在电路复杂性方面有令人惊讶的应用，并建议简化Raz的并行重复定理。一个不同的线程的拟议研究的动机是有关计划的问题，保护多媒体出版商对盗版的电子图像。出版商可以使用代码的单词来标记图像的电子副本。然后，如果代码设计得当，任何由两张合法交易的图像组合而成的图像都包含足够的信息来追踪至少一张源图像（父图像）的身份。这里的问题是构建能够识别三张或更多源图像之一的有效代码。其他的研究目标包括有效的可解码的量子码，以及通过不寻常的代码来解决动态问题的复杂性下限。这需要：1.对不同非常用码之间关系的研究和探索;2.它们的分类和公理化;3.在下界和伪随机理论以及计算机科学的其他领域中寻找不寻常代码的新应用;4.建立代码属性的“家谱”，并找到属性和应用程序之间的匹配。该方法应包含并扩展经典编码理论。