Amos Beimel, Yuval Ishai

A Private Information Retrieval (PIR) protocol enables a user to

retrieve a data item from a database while hiding the identity of the

item being retrieved. In a $t$-private, $k$-server PIR protocol the

database is replicated among $k$ servers, and the user's privacy is

protected from any collusion of up ...
more >>>

Iordanis Kerenidis, Ronald de Wolf

We prove exponential lower bounds on the length of 2-query

locally decodable codes. Goldreich et al. recently proved such bounds

for the special case of linear locally decodable codes.

Our proof shows that a 2-query locally decodable code can be decoded

with only 1 quantum query, and then ...
more >>>

Luca Trevisan

Error-correcting codes and related combinatorial constructs

play an important role in several recent (and old) results

in computational complexity theory. In this paper we survey

results on locally-testable and locally-decodable error-correcting

codes, and their applications to complexity theory and to

cryptography.

Locally decodable codes are error-correcting codes ... more >>>

Oded Goldreich

We survey known results regarding locally testable codes

and locally testable proofs (known as PCPs),

with emphasis on the length of these constructs.

Locally testability refers to approximately testing

large objects based on a very small number of probes,

each retrieving a single bit in the ...
more >>>

Zeev Dvir, Amir Shpilka

In this work we study two seemingly unrelated notions. Locally Decodable Codes(LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing ... 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 >>>

David P. Woodruff

For any odd integer q > 1, we improve the lower bound for general q-query locally decodable codes C: {0,1}^n -> {0,1}^m from m = Omega(n/log n)^{(q+1)/(q-1)} to m = Omega(n^{(q+1)/(q-1)})/log n. For example, for q = 3 we improve the previous bound from Omega(n^2/log^2 n) to Omega(n^2/log n). For ... more >>>

Prasad Raghavendra

Locally Decodable codes(LDC) support decoding of any particular symbol of the input message by reading constant number of symbols of the codeword, even in presence of constant fraction of errors.

In a recent breakthrough, Yekhanin designed $3$-query LDCs that hugely improve over earlier constructions. Specifically, for a Mersenne prime $p ... more >>>

Brett Hemenway, Rafail Ostrovsky

In this paper, we introduce the notion of a Public-Key Encryption (PKE) Scheme that is also a Locally-Decodable Error-Correcting Code.

In particular, our construction simultaneously satisfies all of the following properties:

\begin{itemize}

\item

Our Public-Key Encryption is semantically secure under a certain number-theoretic hardness assumption

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

Tali Kaufman, Madhu Sudan

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many codewords. Our results are the first to show that local decodability and ... more >>>

Klim Efremenko

Locally Decodable Codes (LDC) allow one to decode any particular

symbol of the input message by making a constant number of queries

to a codeword, even if a constant fraction of the codeword is

damaged. In recent work ~\cite{Yekhanin08} Yekhanin constructs a

$3$-query LDC with sub-exponential length of size

$\exp(\exp(O(\frac{\log ...
more >>>

Zeev Dvir

We describe a new approach for the problem of finding {\rm rigid} matrices, as posed by Valiant [Val77], by connecting it to the, seemingly unrelated, problem of proving lower bounds for locally self-correctable codes. This approach, if successful, could lead to a non-natural property (in the sense of Razborov and ... more >>>

Eli Ben-Sasson, Michael Viderman

Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations.

Kaufman and Sudan \cite{KS07} proved that sparse, low-bias linear codes are locally testable (in particular sparse random codes are locally testable).

Kopparty ...
more >>>

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

Recently Efremenko showed locally-decodable codes of sub-exponential

length. That result showed that these codes can handle up to

$\frac{1}{3} $ fraction of errors. In this paper we show that the

same codes can be locally unique-decoded from error rate

$\half-\alpha$ for any $\alpha>0$ and locally list-decoded from

error rate $1-\alpha$ ...
more >>>

Tali Kaufman, Michael Viderman

We study the relation between locally testable and locally decodable codes.

Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. Locally decodable codes (LDCs) allow to recover each message entry with ...
more >>>

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

We show a generic, simple way to amplify the error-tolerance of locally decodable codes.

Specifically, we show how to transform a locally decodable code that can tolerate a constant fraction of errors

to a locally decodable code that can recover from a much higher error-rate. We also show how to ...
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 >>>

Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng Zhang

A $k$-query locally decodable code (LDC)

$\textbf{C}:\Sigma^{n}\rightarrow \Gamma^{N}$ encodes each message $x$ into

a codeword $\textbf{C}(x)$ such that each symbol of $x$ can be probabilistically

recovered by querying only $k$ coordinates of $\textbf{C}(x)$, even after a

constant fraction of the coordinates have been corrupted.

Yekhanin (2008)

constructed a $3$-query LDC ...
more >>>

Eli Ben-Sasson, Michael Viderman

The main open problem in the area of locally testable codes (LTCs) is whether there exists an asymptotically good family of LTCs and to resolve this question it suffices to consider the case of query complexity $3$. We argue that to refute the existence of such an asymptotically good family ... more >>>

Anna Gal, Andrew Mills

Locally decodable codes

are error correcting codes with the extra property that, in order

to retrieve the correct value of just one position of the input with

high probability, it is

sufficient to read a small number of

positions of the corresponding,

possibly corrupted ...
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 >>>

Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters

This work considers locally decodable codes in the computationally bounded channel model. The computationally bounded channel model, introduced by Lipton in 1994, views the channel as an adversary which is restricted to polynomial-time computation. Assuming the existence of IND-CPA secure public-key encryption, we present a construction of public-key locally decodable ... more >>>

Klim Efremenko

Locally Decodable Code (LDC) is a code that encodes a message in a way that one can decode any particular symbol of the message by reading only a constant number of locations, even if a constant fraction of the encoded message is adversarially

corrupted.

In this paper we ... more >>>

Swastik Kopparty

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

Alan Guo, Madhu Sudan

In this work we explore error-correcting codes derived from

the ``lifting'' of ``affine-invariant'' codes.

Affine-invariant codes are simply linear codes whose coordinates

are a vector space over a field and which are invariant under

affine-transformations of the coordinate space. Lifting takes codes

defined over a vector space of small dimension ...
more >>>

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) base-code of block-length $q$ to a lifted-code of block-length $q^m$, for arbitrary integer $m$. The construction generalizes the way degree-$d$, univariate polynomials evaluated over the $q$-element field (also known as Reed-Solomon codes) are "lifted" ... more >>>

Mahdi Cheraghchi, Anna Gal, Andrew Mills

Locally decodable codes (LDCs) are error correcting codes with the extra property that it is sufficient to read just a small number of positions of a possibly corrupted codeword in order to recover any one position of the input. To achieve this, it is necessary to use randomness in the ... more >>>

Zeev Dvir, Guangda Hu

We prove new upper bounds on the size of families of vectors in $\Z_m^n$ with restricted modular inner products, when $m$ is a large integer. More formally, if $\vec{u}_1,\ldots,\vec{u}_t \in \Z_m^n$ and $\vec{v}_1,\ldots,\vec{v}_t \in \Z_m^n$ satisfy $\langle\vec{u}_i,\vec{v}_i\rangle\equiv0\pmod m$ and $\langle\vec{u}_i,\vec{v}_j\rangle\not\equiv0\pmod m$ for all $i\neq j\in[t]$, we prove that $t \leq ... more >>>

Oded Goldreich, Tom Gur, Ilan Komargodski

Locally testable codes (LTCs) are error-correcting codes

that admit very efficient codeword tests. An LTC is said to

be strong if it has a proximity-oblivious tester;

that is, a tester that makes only a constant number of queries

and reject non-codewords with probability that depends solely

on their distance from ...
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 >>>

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>

Jop Briet

We show that any $q$-query locally decodable code (LDC) gives a copy of $\ell_1^k$ with small distortion in the Banach space of $q$-linear forms on $\ell_{p_1}^N\times\cdots\times\ell_{p_q}^N$, provided $1/p_1 + \cdots + 1/p_q \leq 1$ and where $k$, $N$, and the distortion are simple functions of the code parameters. We exhibit ... more >>>

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

An error correcting code is said to be \emph{locally testable} if

there is a test that checks whether a given string is a codeword,

or rather far from the code, by reading only a small number of symbols

of the string. Locally testable codes (LTCs) are both interesting

in their ...
more >>>

Oded Goldreich, Tom Gur

We initiate a study of ``universal locally testable codes" (universal-LTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a universal-LTC $C:\{0,1\}^k \to \{0,1\}^n$ for a family of functions $\mathcal{F} = \{ f_i : \{0,1\}^k \to \{0,1\} \}_{i ... more >>>

Swastik Kopparty, Shubhangi Saraf

We survey the state of the art in constructions of locally testable

codes, locally decodable codes and locally correctable codes of high rate.

Scott Aaronson

We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable ... more >>>

Tom Gur, Oded Lachish

A locally decodable code (LDC) C:{0,1}^k -> {0,1}^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to ... more >>>

Gil Cohen, Tal Yankovitz

In a seminal work, Kopparty et al. (J. ACM 2017) constructed asymptotically good $n$-bit locally decodable codes (LDC) with $2^{\widetilde{O}(\sqrt{\log{n}})}$ queries. A key ingredient in their construction is a distance amplification procedure by Alon et al. (FOCS 1995) which amplifies the distance $\delta$ of a code to a constant at ... more >>>

Alessandro Chiesa, Tom Gur, Igor Shinkar

Locally correctable codes (LCCs) are error correcting codes C : \Sigma^k \to \Sigma^n which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. This notion is stronger than that of locally decodable codes (LDCs), where the goal is to only recover ... more >>>

Gil Cohen, Tal Yankovitz

The Alon-Edmonds-Luby distance amplification procedure (FOCS 1995) is an algorithm that transforms a code with vanishing distance to a code with constant distance. AEL was invoked by Kopparty, Meir, Ron-Zewi, and Saraf (J. ACM 2017) for obtaining their state-of-the-art LDC, LCC and LTC. Cohen and Yankovitz (CCC 2021) devised a ... more >>>

Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar

A code $C \colon \{0,1\}^k \to \{0,1\}^n$ is a $q$-locally decodable code ($q$-LDC) if one can recover any chosen bit $b_i$ of the message $b \in \{0,1\}^k$ with good confidence by randomly querying the encoding $x = C(b)$ on at most $q$ coordinates. Existing constructions of $2$-LDCs achieve $n = ... more >>>

Guy Goldberg

Relaxed locally decodable codes (RLDCs) are error-correcting codes in which individual bits of the message can be recovered by querying only a few bits from a noisy codeword.

Unlike standard (non-relaxed) decoders, a relaxed one is allowed to output a ``rejection'' symbol, indicating that the decoding failed.

To prevent the ...
more >>>

Pravesh Kothari, Peter Manohar

We prove that the blocklength $n$ of a linear $3$-query locally correctable code (LCC) $\mathcal{L} \colon \mathbb{F}^k \to \mathbb{F}^n$ with distance $\delta$ must be at least $n \geq 2^{\Omega\left(\left(\frac{\delta^2 k}{(|\mathbb{F}|-1)^2}\right)^{1/8}\right)}$. In particular, the blocklength of a linear $3$-query LCC with constant distance over any small field grows exponentially with $k$. ... more >>>

Tal Yankovitz

A $q$-locally correctable code (LCC) $C:\{0,1\}^k \to \{0,1\}^n$ is a code in which it is possible to correct every bit of a (not too) corrupted codeword by making at most $q$ queries to the word. The cases in which $q$ is constant are of special interest, and so are the ... more >>>

Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi

A Matching Vector ($\mathbf{MV}$) family modulo a positive integer $m \ge 2$ is a pair of ordered lists $\mathcal{U} = (\mathbf{u}_1, \cdots, \mathbf{u}_K)$ and $\mathcal{V} = (\mathbf{v}_1, \cdots, \mathbf{v}_K)$ where $\mathbf{u}_i, \mathbf{v}_j \in \mathbb{Z}_m^n$ with the following property: for any $i \in [K]$, the inner product $\langle \mathbf{u}_i, \mathbf{v}_i \rangle ... more >>>

Pravesh Kothari, Peter Manohar

We give improved lower bounds for binary $3$-query locally correctable codes (3-LCCs) $C \colon \{0,1\}^k \rightarrow \{0,1\}^n$. Specifically, we prove:

(1) If $C$ is a linear design 3-LCC, then $n \geq 2^{(1 - o(1))\sqrt{k} }$. A design 3-LCC has the additional property that the correcting sets for every ...
more >>>