[talks] Sivakanth Gopi FPO Monday, June 11, 2018 10:00 am CS 402

[Barbara A. Mooring]

Sivakanth Gopi will present his FPO on Monday, June 11, 2018 at 10:00 am in room CS 402.

All are welcomed to attend.

Committee:

Zeev Dvir, Adviser - Princeton University
Ran Raz - Princeton University
Avi Wigderson - Institute for Advanced Study

Title:  Locality in Coding Theory


Abstract:  

Error correcting codes have been extremely successful in practice to build storage
and communication systems which are resilient to noise and corruptions. They also
found several theoretical applications in complexity theory, pseudorandomness, probabilistically
checkable proofs 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.

Much of the work in this thesis 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 several 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 additive combinatorics, information
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 which are locally correctable codes designed specifically for distributed data
storage applications.



Barbara A. Mooring
Interim Graduate Coordinator
Computer Science Department
Princeton University