Sivakanth Gopi will present pre-FPO talk on March 1st, 2018 at 2pm in CS 302. The memebers of his committee are as follows: Zeev Dvir (advisor and examiner), Princeton University Ran Raz (examiner), Princeton University Avi Wigderson (examiner), IAS Mark Zhandry (reader), Princeton University Swastik Kopparty (reader), Rutgers University All are welcome to attend. =============== Title: Locality in coding theory Abstract: Error correcting codes have been extremely successful in practice to build storage/communication systems which are resilient to noise and corruptions. They also found several theoretical applications in complexity theory, pseudorandomness, hardness of approximation (PCPs) and cryptography. Each application requires codes with specific properties. One such property desirable in many applications is ‘locality’. Locality refers to the ability to perform operations like decoding/correction/testing in sublinear or sometimes constant time. For example, a constant query locally decodable code (LDC) allows decoding of any message bit in constant time given a corrupted encoding of the message. The goal of our research is to understand the power and limitations of codes with ‘locality’. We show that one can get non-trivial locality and still match the best known rate-distance tradeoffs of traditional error correcting codes (Gilbert-Varshamov bound). We prove some conditional lower bounds on codes with locality and give new directions for constructing such codes by showing an analytic characterization of LDCs. We also explore applications of such codes to privacy and data storage. We show how to use ideas from existing constructions of LDCs to design 2-server private information retrieval schemes where a user can efficiently and privately query a database replicated among two (non-communicating) servers without revealing any information about their query to either server. We also show limits and improved constructions of maximally recoverable local reconstruction codes (MR LRCs) which are local codes designed specifically for distributed data storage applications; these codes are already being deployed in practice, for example in Microsoft Azure storage. ================