[talks] Guangda Hu will present his Pre FPO on Friday, March 25, 2016 at 10:30am in CS 301.

[Nicki Gotsis]

Guangda Hu will present his Pre FPO on Friday, March 25, 2016 at 10:30am in CS 301.

The members of his committee are:  Zeev Dvir (adviser), Readers: Shubhangi Saraf (Rutgers), Sanjeev Arora; Non-readers: Mark Braverman, Elad Hazan.

Everyone is invited to attend his talk.  The talk title and abstract follow below:

Title: Results on the complexity of codes with nice recovering capabilities

Abstract: In both practice and theory, much research has been done on error correcting codes with nice recovering capabilities. In this thesis, we will discuss two types of such codes, namely Locally Decodable/Correctable Codes (LDCs/LCCs) and Maximally Recoverable (MR) Codes.

LDCs are error correcting codes that each symbol of the original message can be recovered by making a small number of queries even if a constant fraction of the codeword is corrupted. LCCs are similar to LDCs except that we can correct every symbol in the codeword and not just the original message. LDCs/LCCs play an important role in theoretical computer science but are still not well understood. For the case that the query number is very small (constant greater than 2 for example), the best known constructions are the Matching-Vector codes [DGY11] which have subexponential (but superpolynomial) code lengths, and the best lower bound is super quadratic for 3-LCC over reals [DSW14]. It is a great challenge to make this huge gap smaller. We will discuss two results towards better understandings about the lower bounds of constant query LDCs/LCCs. First, we consider codes over real numbers and discuss an approximate version of LDCs. The problem of approximate codes itself is interesting and it is also related to notion of [DSW14] which gives the first super quadratic lower bound for 3-LCCs. We obtain bounds for approximate codes that are similar to the best known ones for exact codes. Second, we consider a generalization of the Sylvester-Gallai theorem in geometry. Basically LCCs and the Sylvecter-Gallai theorem are both questions about configurations of points with many local dependencies, and the connection between them has been studied in several previous works. We give a subspace version of Sylvester-Gallai and generalize an important tool used in [DSW14].

In distributed data storage systems, one common practice is to partition data into local groups and there are both local checksums for each local group and global checksums that depend on all data. MR codes are systematic codes that have the information theoretically optimal erasure recovering capability. It is known that there are explicit constructions for MR codes in any common reasonable topology of group partitioning [GHJY14]. However, the problem is that all known constructions require the alphabet to be very large and this is inefficient for both storing and recovering. In practice, it is actually observed that there is a tradeoff between "efficiency" and "reliability", though there was no theoretical proof. We give the first lower bound for the alphabet size of MR codes of a common topology. This shows that a storage system that is maximally recoverable cannot be efficient and is the first proof of the tradeoff. We also give new constructions with new techniques of MR codes that improves the previous results for various parameters.

Based on joint works with Jop Briet, Zeev Dvir, Parikshit Gopalan, Swastik Kopparty, Shubhangi Saraf, Carol Wang, Sergey Yekhanin.