Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Sivakanth Gopi:

TR16-189 | 21st November 2016
Arnab Bhattacharyya, Sivakanth Gopi

Lower bounds for 2-query LCCs over large alphabet

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 >>>

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

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 >>>

TR15-185 | 24th November 2015
Arnab Bhattacharyya, Sivakanth Gopi

Lower bounds for constant query affine-invariant LCCs and LTCs

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 >>>

TR14-094 | 24th July 2014
Zeev Dvir, Sivakanth Gopi

2-Server PIR with sub-polynomial communication

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 >>>

ISSN 1433-8092 | Imprint