Codes from Curves: Structure, Decoding, and Modern Applications

Virginia Polytechnic Institute And State University, Blacksburg VA

Investigators

Abstract

This award supports research into algebraic coding theory. The large volume of data generated today motivates the need for distributed storage systems which can provide long-term storage of data with highly reliable retrieval and availability of information to users. A distributed storage system consists of a network of storage nodes. A stored file may be retrieved by accessing these nodes. In such a system, individual nodes may be unreliable; for instance, they may become unavailable due to routine maintenance. For this reason, how information is stored across the network is highly relevant. The goal is to create a storage system that allows for recovery of lost data while limiting both network traffic and the number of disks accessed. This project addresses the problem by appealing to the underlying structure of a family of error-correcting codes defined using algebraic geometry. The codes have robust structure that yields powerful local properties and potential to balance storage overhead, reliability, network traffic, and repair bandwidth. This project considers the use of codes obtained via algebraic geometric constructions in highly relevant applications. The following problems will be studied: coding for distributed storage via algebraic geometric and combinatorial points of view, with the goals of minimizing node access and repair bandwidth; and explicit construction of locally correctable codes, quantum codes, and secret sharing schemes using algebraic geometric tools. Code structure will be explored, and decoding codes which are directs sum may be handled by decoding or repair within its factors. Full use will be made of the automorphism group of the code as well as natural nested structures inherited from the underlying algebraic geometry. Much of the work in this proposal is focused on algebraic geometric constructions utilized in situations where limiting network traffic in the decoding process is desirable; the aim is to accomplish this by capitalizing on the natural underlying structure of algebraic geometric codes rather than appealing exclusively to locality. In doing so, the performance guaranteed by the code construction is maintained (meaning code parameters do not suffer from local requirements) while making the codes more amenable to current applications. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.