Ph.D Thesis

Ph.D StudentBarkol Omer
SubjectLocally Decodable Codes and Their Applications
DepartmentDepartment of Computer Science
Supervisors PROF. Yuval Ishai
PROF. Ronny Roth
Full Thesis textFull thesis text - English Version


Locally Decodable Codes (LDCs) are error-correcting codes in which each symbol of the message can be retrieved by probabilistically probing a limited number of symbols from an adversarially corrupted encoding of the message. This thesis covers several questions that are related to LDCs.

A stronger and desirable property than local decodability is that of self-correction, allowing to efficiently recover not only symbols of the message but also arbitrary symbols of the encoded message. In contrast to the initial constructions of LDCs, the recent and most efficient constructions are not known to be self-correctable. The existence of self-correctable codes of comparable efficiency remains open. The best self-correctable codes known are based on multivariate polynomial representations over finite fields. We study the question of closing this current gap, and relate this question to a conjecture from the 1970s concerning the algebraic rank of combinatorial designs.

Closely related to LDCs is the cryptographic problem of Private Information  Retrieval (PIR). A PIR protocol allows a user to retrieve a data item from a database which is replicated amongst a number of servers, such that each individual server learns nothing about the identity of the item being retrieved. We use LDCs and self-correctable codes to construct better PIR protocols that offer privacy even against coalitions of several servers.

We then investigate a generalization of PIR, where the user privately searches a database, e.g., for partial match or nearest neighbor.  Motivated by the observation that many natural database search problems can be solved by constant-depth circuits, we present efficient distributed protocols for privately evaluating circuits from this class. To this end we extend previous techniques for representing constant-depth circuits by probabilistic low-degree polynomials.

Finally, inspired by techniques used for constructing LDCs, we consider a setting where different players get replicated copies of the same database which are partially erased, and should still allow a referee to compute a function of the database with no interaction and with minimum communication. This is applicable in different settings, such as sensors that measure the same phenomena in parallel, or a database that is locally changed after it was distributed. We present interesting connections between this problem and secret sharing. We use these connections to obtain nontrivial upper bounds and lower bounds using results and techniques from the domain of secret sharing.