All reports by Author Sivakanth Gopi:

__
TR19-013
| 31st January 2019
__

Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami#### CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

__
TR17-183
| 28th November 2017
__

Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin#### On Maximally Recoverable Local Reconstruction Codes

__
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

Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo $M$, for various choices of the modulus $M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2SAT, HornSAT, ... more >>>

Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin

In recent years the explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Local Reconstruction Codes (LRCs) have emerged as the codes of choice for these applications. An $(n,r,h,a,q)$-LRC is a $q$-ary code, where encoding is as a ... more >>>

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