All reports by Author Sergey Yekhanin:

__
TR17-183
| 28th November 2017
__

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

__
TR14-172
| 12th December 2014
__

Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin#### Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity

__
TR13-104
| 20th July 2013
__

Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin#### Explicit Maximally Recoverable Codes with Locality

__
TR11-100
| 20th July 2011
__

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin#### On the Locality of Codeword Symbols

__
TR11-044
| 25th March 2011
__

Shubhangi Saraf, Sergey Yekhanin#### Noisy Interpolation of Sparse Polynomials, and Applications

__
TR10-148
| 23rd September 2010
__

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin#### High-rate codes with sublinear-time decoding

__
TR10-012
| 27th January 2010
__

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin#### Matching Vector Codes

Revisions: 1

__
TR08-065
| 11th July 2008
__

Noga Alon, Rina Panigrahy, Sergey Yekhanin#### Deterministic Approximation Algorithms for the Nearest Codeword Problem

__
TR07-040
| 12th April 2007
__

Kiran Kedlaya, Sergey Yekhanin#### Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers

__
TR06-127
| 7th October 2006
__

Sergey Yekhanin#### New Locally Decodable Codes and Private Information Retrieval Schemes

__
TR06-050
| 18th April 2006
__

Alexander Razborov, Sergey Yekhanin#### An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval

__
TR05-009
| 14th December 2004
__

David P. Woodruff, Sergey Yekhanin#### A Geometric Approach to Information-Theoretic Private Information Retrieval

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

Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin

A square matrix $V$ is called rigid if every matrix $V^\prime$ obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major ... more >>>

Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin

Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, while other (heavy) parity symbols may depend on all data symbols. Local parities allow to quickly recover any single symbol when it is erased, while heavy parities provide tolerance to a large number of simultaneous ... more >>>

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin

Consider a linear $[n,k,d]_q$ code $\mc{C}.$ We say that that $i$-th coordinate of $\mc{C}$ has locality $r,$ if the value at this coordinate can be recovered from accessing some other $r$ coordinates of $\mc{C}.$ Data storage applications require codes with small

redundancy, low locality for information coordinates, large distance, and ...
more >>>

Shubhangi Saraf, Sergey Yekhanin

Let $f\in F_q[x]$ be a polynomial of degree $d\leq q/2.$ It is well-known that $f$ can be uniquely recovered from its values at some $2d$ points even after some small fraction of the values are corrupted. In this paper we establish a similar result for sparse polynomials. We show that ... more >>>

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been ... more >>>

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin

An $(r,\delta,\epsilon)$-locally decodable code encodes a $k$-bit message $x$ to an $N$-bit codeword $C(x),$ such that for every $i\in [k],$ the $i$-th message bit can be recovered with probability $1-\epsilon,$ by a randomized decoding procedure that reads only $r$ bits, even if the codeword $C(x)$ is corrupted in up to ... more >>>

Noga Alon, Rina Panigrahy, Sergey Yekhanin

The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v in an n-dimensional space over F_2 and a linear subspace L in F_2^n of dimension k NCP asks to find a point l in L that minimizes the (Hamming) distance ... more >>>

Kiran Kedlaya, Sergey Yekhanin

A k-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only k bits of the codeword C(x), even after some constant fraction of codeword bits has been corrupted. The major ... more >>>

Sergey Yekhanin

A q-query Locally Decodable Code (LDC) encodes an n-bit message

x as an N-bit codeword C(x), such that one can

probabilistically recover any bit x_i of the message

by querying only q bits of the codeword C(x), even after

some constant fraction of codeword bits has been corrupted.

We give ... more >>>

Alexander Razborov, Sergey Yekhanin

A two server private information retrieval (PIR) scheme

allows a user U to retrieve the i-th bit of an

n-bit string x replicated between two servers while each

server individually learns no information about i. The main

parameter of interest in a PIR scheme is its communication

complexity, namely the ...
more >>>

David P. Woodruff, Sergey Yekhanin

A t-private private information retrieval (PIR) scheme allows a user to retrieve the i-th bit of an n-bit string x replicated among k servers, while any coalition of up to t servers learns no information about i. We present a new geometric approach to PIR, and obtain (1) A t-private ... more >>>