Unusual Error Correcting Codes

Rutgers University New Brunswick, New Brunswick NJ

Investigators

Abstract

Error correcting codes were originally invented to increase the precision of retrieval, storage and communication of data. The investigator's goal is to study and develop codes with new features added on top of the error correcting property, such as checkability, identifiable parent property (IPP), or quantum-error correcting property. In spite of the importance of designing codes with added features, there has not ben a comprehensive study of them up to date, and each design is treated as an isolated case. The investigator wants to put the designs under one umbrella (whenever it is possible) so that their properties can be compared and further improved upon. Among the benefits such improvement can bring about are 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 to observe that constructs in the theory of probabilistically checkable proofs can be viewed as error correcting codes with added features. The best parameters for these codes and their kins are still not known, and they are the primary targets of the proposed investigation in the first year. The investigator also plans for a study that would 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 repetition theorem. A different thread of the the proposed research is motivated by questions about schemes that protect a multi-media publisher against piracy of electronic images. The publisher can use words of a code to mark electronic copies of an image. Then, if the code is appropriately designed, any image forged by combining pieces of two legally traded images, contains sufficient amount of information to trace the identity of at least one of the source (parent) images. Here the problem is to build efficient codes that can identify one of three or more source images. Other research targets include efficiently decodable quantum codes, and complexity lower bounds for dynamic problems via unusual codes. There is a general framework in which the investigator plans to do the research. This entails: 1. The study and exploration of the relation in between different unusual codes; 2. Their classification and axiomatization; 3. Search for novel applications of unusual codes in 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 match in between properties and applications. The methodology should embrace and extend classical coding theory.