Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01ng451m268
 Title: Locality in coding theory Authors: Gopi, Sivakanth Advisors: Dvir, Zeev Contributors: Computer Science Department Keywords: additive combinatoricsCoding theorydistributed storageLocalitylocally decodable codesprivate information retrieval Subjects: Computer scienceMathematics Issue Date: 2018 Publisher: Princeton, NJ : Princeton University 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. URI: http://arks.princeton.edu/ark:/88435/dsp01ng451m268 Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: catalog.princeton.edu Type of Material: Academic dissertations (Ph.D.) Language: en Appears in Collections: Computer Science

Files in This Item:
File Description SizeFormat