All reports by Author Sivakanth Gopi:

__
TR16-189
| 21st November 2016
__

Arnab Bhattacharyya, Sivakanth Gopi#### Lower bounds for 2-query LCCs over large alphabet

__
TR16-122
| 11th August 2016
__

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf#### Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound

__
TR15-185
| 24th November 2015
__

Arnab Bhattacharyya, Sivakanth Gopi#### Lower bounds for constant query affine-invariant LCCs and LTCs

__
TR14-094
| 24th July 2014
__

Zeev Dvir, Sivakanth Gopi#### 2-Server PIR with sub-polynomial communication

Arnab Bhattacharyya, Sivakanth Gopi

A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates.

We show that any zero-error $2$-query locally correctable code $\mathcal{C}: \{0,1\}^k \to \Sigma^n$ that can correct a constant fraction of corrupted symbols must ...
more >>>

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf

One of the most important open problems in the theory

of error-correcting codes is to determine the

tradeoff between the rate $R$ and minimum distance $\delta$ of a binary

code. The best known tradeoff is the Gilbert-Varshamov bound,

and says that for every $\delta \in (0, 1/2)$, there are ...
more >>>

Arnab Bhattacharyya, Sivakanth Gopi

Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A particularly appealing feature of affine-invariant codes is ... more >>>

Zeev Dvir, Sivakanth Gopi

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the $i$th bit of an $n$-bit database replicated among two servers (which do not communicate) while not revealing any information about $i$ to either server. In this work we construct a 1-round 2-server PIR with total communication cost ... more >>>