Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LOCALLY DECODABLE CODES:
Reports tagged with Locally decodable codes:
TR01-015 | 9th February 2001
Amos Beimel, Yuval Ishai

#### Information-Theoretic Private Information Retrieval: A Unified Construction

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

TR02-059 | 9th August 2002
Iordanis Kerenidis, Ronald de Wolf

#### Exponential Lower Bound for 2-Query Locally Decodable Codes

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

TR04-043 | 20th May 2004
Luca Trevisan

#### Some Applications of Coding Theory in Computational Complexity

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

TR05-014 | 30th January 2005
Oded Goldreich

#### Short Locally Testable Codes and Proofs (Survey)

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

TR05-044 | 6th April 2005
Zeev Dvir, Amir Shpilka

#### Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits

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

TR06-127 | 7th October 2006
Sergey Yekhanin

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

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

TR07-006 | 12th January 2007
David P. Woodruff

#### New Lower Bounds for General Locally Decodable Codes

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

TR07-016 | 13th February 2007

#### A Note on Yekhanin's Locally Decodable Codes

Revisions: 1

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 >>> TR07-021 | 5th March 2007 Brett Hemenway, Rafail Ostrovsky #### Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code Revisions: 3 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 >>> TR07-040 | 12th April 2007 Kiran Kedlaya, Sergey Yekhanin #### Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers 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 >>> TR07-060 | 11th July 2007 Tali Kaufman, Madhu Sudan #### Sparse Random Linear Codes are Locally Decodable and Testable 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 >>> TR08-069 | 5th August 2008 Klim Efremenko #### 3-Query Locally Decodable Codes of Subexponential Length 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 >>>

TR09-134 | 10th December 2009
Zeev Dvir

#### On matrix rigidity and locally self-correctable codes

Revisions: 1

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

TR10-004 | 6th January 2010
Eli Ben-Sasson, Michael Viderman

#### Low Rate Is Insufficient for Local Testability

Revisions: 3

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

TR10-047 | 23rd March 2010
Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

#### Local list decoding with a constant number of queries

Revisions: 1

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

TR10-130 | 18th August 2010
Tali Kaufman, Michael Viderman

#### Locally Testable vs. Locally Decodable Codes

Revisions: 1

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

TR10-134 | 23rd August 2010
Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

#### A Note on Amplifying the Error-Tolerance of Locally Decodable Codes

Revisions: 2

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

TR10-148 | 23rd September 2010
Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

#### High-rate codes with sublinear-time decoding

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

TR10-173 | 9th November 2010
Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng Zhang

#### Query-Efficient Locally Decodable Codes

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

TR10-200 | 14th December 2010
Eli Ben-Sasson, Michael Viderman

#### Towards lower bounds on locally testable codes via density arguments

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

TR11-030 | 9th March 2011
Anna Gal, Andrew Mills

#### Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length

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

TR11-044 | 25th March 2011
Shubhangi Saraf, Sergey Yekhanin

#### Noisy Interpolation of Sparse Polynomials, and Applications

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

TR11-118 | 6th September 2011
Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters

#### Public Key Locally Decodable Codes with Short Keys

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

TR11-154 | 17th November 2011
Klim Efremenko

#### From Irreducible Representations to Locally Decodable Codes

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

TR12-044 | 22nd April 2012
Swastik Kopparty

#### List-Decoding Multiplicity Codes

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

TR12-106 | 27th August 2012

#### New affine-invariant codes from lifting

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

TR12-148 | 7th November 2012
Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

#### A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Revisions: 1

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

TR12-172 | 8th December 2012
Mahdi Cheraghchi, Anna Gal, Andrew Mills

#### Correctness and Corruption of Locally Decodable Codes

Revisions: 1

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

TR13-061 | 17th April 2013
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 >>> TR14-025 | 25th February 2014 Oded Goldreich, Tom Gur, Ilan Komargodski #### Strong Locally Testable Codes with Relaxed Local Decoders 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 >>> 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 >>> TR15-068 | 21st April 2015 Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf #### High rate locally-correctable and locally-testable codes with sub-polynomial query complexity Revisions: 3 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 >>> TR15-086 | 28th May 2015 Jop Briet #### On Embeddings of$\ell_1^k$from Locally Decodable Codes 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 >>> TR15-110 | 8th July 2015 Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf #### High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity Revisions: 1 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 >>> TR16-042 | 19th March 2016 Oded Goldreich, Tom Gur #### Universal Locally Testable Codes Revisions: 2 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 >>>

TR17-126 | 7th August 2017
Swastik Kopparty, Shubhangi Saraf

#### Local Testing and Decoding of High-Rate Error-Correcting Codes

We survey the state of the art in constructions of locally testable
codes, locally decodable codes and locally correctable codes of high rate.

more >>>

TR18-099 | 19th May 2018
Scott Aaronson

#### PDQP/qpoly = ALL

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

TR19-056 | 11th April 2019
Tom Gur, Oded Lachish

#### A Lower Bound for Relaxed Locally Decodable Codes

Revisions: 1

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

TR20-084 | 31st May 2020
Gil Cohen, Tal Yankovitz

#### Rate Amplification and Query-Efficient Distance Amplification for Locally Decodable Codes

Revisions: 1

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

TR20-113 | 27th July 2020
Alessandro Chiesa, Tom Gur, Igor Shinkar

#### Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity

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

TR21-136 | 13th September 2021
Gil Cohen, Tal Yankovitz

#### LCC and LDC: Tailor-made distance amplification and a refined separation

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

TR22-101 | 15th July 2022
Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar

#### A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

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

ISSN 1433-8092 | Imprint