Locally Decodable Codes With 3 Queries

Locally decodable codes (LDCs) are a special type of error-correcting code that enable the extraction of individual message symbols by only querying a small subset of the encoded symbols. Unlike traditional decoding which requires reading the entire codeword, LDCs allow for localized decoding whereby each symbol can be recovered by looking at a few codeword positions dependent on the symbol index. This section covers the definition of LDCs, motivation behind them, and key properties that characterize their local decodability.

Definition: Enabling Extractions of Individual Symbols

Formally, a locally decodable code encodes a length $k$ message $x\; \backslash in\; \backslash Sigma^k$ over an alphabet $\backslash Sigma$ into a longer codeword $C(x)\; \backslash in\; \backslash Gamma^n$ over an alphabet $\backslash Gamma$. An LDC is said to be $(q,\; \backslash delta,\; \backslash epsilon)$-locally decodable if for all $i\; \backslash in\; [k]$ and $z\; \backslash in\; \backslash Gamma^n$ at Hamming distance $\backslash Delta(z,\; C(x))\; \backslash leq\; \backslash delta$ from a valid codeword $C(x)$, there exists a randomized decoding algorithm that makes only $q$ symbol queries to $z$ and outputs $x\_i$ with probability at least $1\; –\; \backslash epsilon$. Thus with just $q$ queries, individual message symbols can be recovered even if the codeword is corrupted.

Motivation: Retrieving Data Without Full Decoding

A key motivation behind LDCs is to enable selective access and extraction of specific encoded symbols without needing to decode the entire codeword. This capability allows for localized data retrieval that is especially useful in distributed storage systems where reading large blocks of data can be expensive. LDCs also facilitate private information retrieval by revealing little global information about the encoded message in the process of decoding any single symbol. Furthermore, the strict limits on query complexity make LDCs relevant for settings with restricted access.

Constructions: Building LDC Codes With 3 Queries

There are two main techniques for constructing LDCs – based on polynomials over finite fields and on algebraic surfaces. This article focuses on polynomials over prime fields $\backslash mathbb\{F\}\_p$ which can yield 3-query LDCs. The message symbols are viewed as specifying coefficients of a multivariate polynomial that is evaluated over randomly chosen field elements to encode each symbol. To decode, the polynomial is interpolated through its evaluations at 3 specially chosen points, using Lagrange interpolation. The interpolating polynomial allows recovering the required coefficient. As we will see, the security and locally decodability properties follow from the hardness of partial polynomial reconstruction and multivariate polynomial interpolation.

Query Complexity: Analyzing Efficiency of Query Schemes

A key metric for evaluating LDCs is their query complexity – the number of codeword symbol lookups needed to decode each message symbol. Query complexity directly impacts the decoding efficiency and accessibility of individual codeword elements. The focus on constant query LDCs, requiring only a small fixed number of queries per decoded symbol, arises because they offer the strongest form of local decodability. This section covers what 3-query LDCs represent: the minimum queries needed for non-trivially decodable codes. We analyze associated computational constraints and tradeoffs.

The 3-Query Threshold

It has been proven that no nontrivial LDCs exist with query complexity 1 or 2. Intuitively this holds because with a single query, all message symbols would map to the same codeword position, leaking no information. And with 2 queries invertible mappings could be found that reveal codeword elements not queried. Three queries represents the minimum requirement fordecoding success probability better than random guessing. Any smaller number of queries fails to provide enough unpredictability and information.

Implications on Computation Time

A decoding procedure making only 3 symbol lookups is highly efficient regarding accessible data. However, computational overhead is still a factor determining absolute speed. Known constructions of 3-query LDCs lead to fast decoding algorithms requiring low-degree polynomial interpolations over small finite fields. Using fast interpolation and Lagrange basis polynomials, each decoding runs in nearly linear arithmetic time in the code length. So while minimizing the number of probes is vital, the associated post-processing must also remain computationally light.

Examples: Sample 3-Query LDCs Based on Polynomials

This section constructs an explicit family of 3-query LDCs based on low-degree multivariate polynomial encodings and decodings. We analyze parameters, properties, and capabilities of these codes. The goal is to both demonstrate 3-query LDCs in action and characterize their strengths through a concrete scheme. Key facets like alphabet sizes, encoding field sizes, and error tolerance illustrate inherent constraints and tradeoffs.

A Linear Length Construction

Let message $x\; \backslash in\; \backslash mathbb\{F\}\_p^k$ have $k$ field elements. The encoder randomly selects a quadratic polynomial over $k+1$ variables $Q(y\_0,\; \backslash ldots,\; y\_k)\; \backslash in\; \backslash mathbb\{F\}\_p[y\_0,\; \backslash ldots,\; y\_k]$ where $y\_0$ is constant 1. Each $x\_i$ sets coefficient of $y\_i$. Encode each $x\_i$ by the evaluations of $Q$ over $n=3k$ random points in $\backslash mathbb\{F\}\_p^\{k+1\}$. To decode $x\_i$, interpolate $Q$ given 3 evaluations using Lagrange basis polynomials. The free coefficient is $x\_i$. This builds a $(3,\; \backslash delta,\; \backslash frac\{1\}\{p\})$-LDC handling a $\delta$ fraction of errors.

Analysis of Parameters

The LDC operates over alphabet size |Σ|=p. Its length is n=3k, decoded symbols are from Σ^k, and each decoding makes 3 queries. The error tolerance δ depends on n and the field size p. Larger p reduces the error probability. There is a tradeoff between length, alphabet size, and error handling. This demonstrates interactions between code parameters that satisfy the local decodability properties.

Applications: When Limited Access LDCs Are Useful

The strict access constraints of LDCs allow them to provide functionality not feasible with traditional erasure and error correction codes in certain domains. A few example application areas that leverage locally decodable aspects are covered here. These demonstrate the advantage of selective decoding without full codeword reconstruction across different settings.

Private Stream Retrieval

LDCs enhance privacy for selective accesses of encoded data. For example, with video streams encoded via LDCs, a user can retrieve a specific frame while hiding which frame is decoded and without needing to process the entire stream. Only small portions of the encoded stream are revealed while retaining on-demand frame access. Such fine-grained control is possible due to localized decoding and low query complexity.

Distributed Storage

In large-scale distributed storage spanning multiple nodes, reading an entire file or database can require aggregated bandwidth across nodes. LDCs allow specific parts of encoded data to be recovered by accessing just a few storage nodes based on the decoding queries. So they reduce communication overhead of selective data retrieval in distributed systems without downloading full files.

Secure Processors

Secure processors with encrypted memory can allow third parties to run algorithms without exposing raw private data. Queries output by algorithms are revealed on encoded data. LDCs only require few queries to implement common tasks. So secure computation tasks become feasible while data remains encrypted with just small decryptions for each query.

Open Problems: Frontiers in Local Decodability

While LDCs are a vibrant research field with far-reaching applications, many open questions remain. This concluding section highlights a few active problem areas being pursued regarding local decodability.

Tight Query Complexity Bounds

The minimum query complexity for nontrivially decoding LDCs is known to be 3. However, tighter lower bounds depending on code length, alphabet size, and error tolerance are not fully characterized. Improved bounds taking into account different code parameters remain active targets to pin down optimality for locally decoding given sets of constraints.

Query-Efficient Decoding Algorithms

Constructing explicit code Families with provable bounds is also a direction being actively explored. While randomized constructions like the earlier polynomial scheme often suffice, deterministic encodings and encodings over smaller fields could unlock further applications. These remain challenging to realize within tight query complexities.

Relating LDCs to Areas Like Coding Theory

Lastly, better understanding connections of LDCs to established fields like traditional coding and complexity theory could yield further progress. Pursuing unified ways to discuss error correction, random access codes, and other areas with LDCs may lead to unexpected query complexity and decoding algorithm improvements through translating known techniques.