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.