Unusual Error Correcting Codes

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

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.