PaperlayerView exact revision on arXiv

Source-linked AI summary

Amortized Relaxed Locally Decodable Codes

Jeremiah Blocki, Justin Zhang

arXiv:2609.16332v1cs.ITcs.DMmath.IT

TL;DR

Classical LDC lower bounds show the ideal regime is unattainable: for constant error tolerance δ=Ω(1) and locality ℓ≥2, codeword length n∈Ω(kℓ/(ℓ−1)). The paper combines amortized recovery of contiguous intervals with relaxed decoding and converts an amortized locally correctable code into an arLDC using bad-block filtering. A constant-rate, constant-error arLDC exists; for fixed ν<1, amortized locality 1+ν is below 2, and locality and rate approach 1 as ν approaches 0.

  • Problem

    Classical LDC lower bounds show the ideal regime is unattainable: for constant error tolerance δ=Ω(1) and locality ℓ≥2, codeword length n∈Ω(kℓ/(ℓ−1)).

    Source: §1 · p. 1

  • Method

    The paper combines amortized recovery of contiguous intervals with relaxed decoding and converts an amortized locally correctable code into an arLDC using bad-block filtering.

    Source: §1 · p. 2, §2.4 · p. 9

  • Results

    A constant-rate, constant-error arLDC exists; for fixed ν<1, amortized locality 1+ν is below 2, and locality and rate approach 1 as ν approaches 0.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Information-theoretic amortized relaxed decoding can attain constant rate, error tolerance, and amortized locality, unlike the unamortized relaxed setting’s known barriers [17, 18].

    Source: §1 · p. 2

    The generic arLCC-to-arLDC construction limits amortized locality to at least 1/(1−R).

    Source: §7.1 · p. 25

Abstract

from arXiv · show

Locally decodable codes (LDCs) enable recovery of any message symbol by probing only a small number of positions in a possibly corrupted codeword. The central parameters of an LDC are its rate, locality, and error tolerance. Ideally, one would like all three parameters to be constant. However, classical lower bounds show that such codes cannot exist. A recent line of work introduced amortized locally decodable codes (aLDCs), in which the decoder is tasked with recovering an entire block of consecutive message symbols rather than a single symbol. While prior work obtained ideal aLDCs with constant rate, constant error tolerance, and constant amortized locality, those constructions relied on either shared randomness hidden from the channel or computational assumptions restricting the channel. Another well-studied relaxation is the notion of a relaxed locally decodable code (RLDC), in which the decoder may output a special failure symbol $\bot$ rather than risk decoding incorrectly. In this work, we introduce the notion of an amortized relaxed locally decodable code (aRLDC), combining amortized decoding with the relaxed decoding paradigm. Unlike prior ideal aLDC constructions, our model is fully information-theoretic and makes no assumptions about shared randomness or computational limitations of the adversarial channel. We construct the first aRLDC with constant rate, constant error tolerance, and constant amortized locality. Moreover, for any block of length $\Omega(\mathrm{polylog}(k))$, our decoder achieves amortized locality $1+\delta^{1 - o(1)}$, where $\delta$ is the error tolerance parameter. Thus, asymptotically, recovering a long block requires essentially less than two codeword probe per message symbol recovered. By contrast, without amortization no RLDC can simultaneously achieve constant rate, constant error tolerance, and constant locality.

1 Introduction

LDCs recover requested message symbols with few codeword probes, but classical lower bounds rule out the ideal constant-parameter regime. This work combines amortized recovery with relaxed decoding to construct information-theoretic codes with constant rate, error tolerance, and amortized locality, including a regime below 2 that approaches 1.

1 Introduction

  • An LDC recovers a requested message symbol from a possibly corrupted codeword using few probes; its central parameters are rate, error tolerance, and locality.The decoder succeeds with constant probability while querying at most ℓ positions.Source: §1 · p. 1
  • Constant error tolerance and locality ℓ≥2 force codeword length n∈Ω(kℓ/(ℓ−1)), while locality below 2 is impossible regardless of rate.The cited lower bounds motivate relaxing the decoding model.Source: §1 · p. 1
  • Relaxed LDCs may return ⊥ when they detect corruption, but known constructions still fall short of constant locality and some face strong length lower bounds.The model remains information-theoretic and imposes no restrictions on the adversarial channel.Source: §1 · p. 2
  • Blocki and Zhang showed aLDCs with constant rate, constant error tolerance, and constant amortized locality against resource-bounded channels for contiguous requested intervals; no information-theoretic ideal construction was known.Other relaxations assuming a shared secret key or resource-bounded error channel achieved constant rate and error tolerance, but only polylogarithmic locality.Source: §1 · pp. 1–2
  • An (α, κ, δ, ε)-arLDC decodes every interval S of at least κ symbols using at most α|S| probes, outputting x[S] or ⊥ with probability at least 1−ε.The guarantee applies when the corrupted codeword differs from the encoded codeword in at most a δ fraction of positions.Source: §1 · p. 3
  • For constant ε<1, an informal theorem gives a constant-rate arLDC with α=O(1), δ=Ω(1), and κ=c(ε)(log n)^2 2^(log log log n)^4.This is the paper’s first information-theoretic arLDC with constant rate, error tolerance, and amortized locality.Source: §1 · pp. 2–3
  • For any ν>0, the construction achieves amortized locality 1+ν; fixed ν<1 gives locality below 2 with constant rate and error tolerance, and as ν approaches 0, locality and rate approach 1.The stated tolerated error fraction is δ=ν^(1−o(1)).Source: §1 · p. 3

2 Technical Overview

This section explains how nested locally testable codes motivate the constructions, why direct amortization falls short, and how block decoding and an amortization-preserving transformation address those limitations. It then outlines constructions of explicit amortized relaxed locally decodable codes from block-finder codes via relaxed local correction and filtering bad blocks, including variants with constant amortized locality or locality below 2 and approaching 1 under stated conditions.

2.1 Recalling the Nested LCC Construction

  • The prior nested rLCC decoder tests each block along the path to a symbol and outputs ⊥ if a test fails; passing the tests at a sufficiently small bottom block supports correct recovery.Linear rLCCs can be transformed into linear rLDCs with the same rate, distance, and locality, but that transformation need not preserve amortized locality.Source: §2.1 · pp. 3–4

2.2 Technical Challenges

  • Direct amortization fails because correctness requires small bottom blocks, while transforming an rLCC to an rLDC may leave consecutive message-symbol ranges unevenly distributed across codeword blocks.Increasing bottom-block size can sacrifice soundness; although message symbols can be permuted into consecutive order, some blocks may still contain too few message symbols to preserve amortized locality.Source: §2.2 · p. 5

2.3 Our Contributions

  • Constant-size bottom blocks yield an arLCC with constant rate, constant error tolerance, and constant amortized locality; filtering sparsely populated blocks then preserves constant rate and locality when converting it to an arLDC.The bottom-level decoder re-encodes a decoded block with an error-correcting code; the transformation ignores message symbols in blocks with too few symbols, leaving at least a constant fraction of the original message.Source: §2.3 · pp. 5–6
  • For any constant ε, the construction achieves amortized locality 1 + ε with constant error tolerance δ = δ(ε), while its locality can approach 1 as error tolerance approaches zero.The approach combines arLCC locality approaching 1 with a rate approaching 1, using a high-rate block code with sub-constant error tolerance.Source: §2.3 · p. 6

2.4 In-depth Overview

  • FBDCs enable amortization by decoding a requested codeword block either with a bounded error fraction or by returning ⊥; their soundness permits arbitrarily large blocks.Nested expander-code-based vicinity locally testable codes construct the FBDC, and its definition incorporates the error-fraction precondition that prior soundness analyses obtained by bounding block size.Source: §2.4 · pp. 7–8
  • A single top-level VLTC amplification raises FBDC error tolerance from δ′ to δ using ℓ=ℓFBDC+O(δ/δ′)ℓT queries.The block decoder repeats the tester O(δ/δ′) times and uses the original decoder only if all tests pass, while retaining block error tolerance δB.Source: §2.4 · p. 8
  • Applying a block code that corrects δB errors to each FBDC-recovered block yields an arLCC with α=O(ℓ/B) and κ=B.Setting B=ℓ gives constant amortized locality; recovering κ=hB symbols for h=ω(1) makes locality approach 1.Source: §2.4 · p. 9
  • Bad-block filtering retains at least (k−cn)/(1−c) message symbols and raises amortized locality by 1/c while lowering the arLDC rate.The construction defines c-good blocks as containing either zero or at least a c fraction of message symbols, then ignores c-bad blocks.Source: §2.4 · p. 9
  • An explicit arLDC achieves constant amortized locality, constant error tolerance, and constant rate, with κ=log(1/ε)(log n)^2 2^((log log log n)^4).Theorem 24 states α=O(1), δ=Ω(1), and rate 1−RarLDC≥Ω(1).Source: §2.4 · p. 10
  • With R(δ)<1−3(1+ν)/5, an explicit arLDC achieves amortized locality α=5/3.Here R(δ)=δ×2^(c0 log^3(log(1/δ))) for a universal constant c0; the result also specifies κ(ν)=log(1/ε)(log n)^2 2^((log log log n)^4).Source: §2.4 · p. 10
  • Under R(δ)=o(1), for n=2^r with r∈N, ε<1, ν>0, and δ∈(0,1), an explicit arLDC achieves α(δ,ν)=(1+ν)×(1+o(1)).Source: §2.4 · p. 10

3 Preliminaries

The preliminaries define relaxed local decoding and its amortized interval-decoding variant, then introduce expander-based testing and nested codes used in the construction.

3 Preliminaries

  • A linear code is a dimension-k subspace of Σ^n, equivalently described by an injective encoding map from messages to codewords.Its rate is k/n, and its relative distance is the minimum distance between distinct codewords.Source: §3 · p. 11
  • An arLDC recovers the message symbols in a requested consecutive interval, or outputs ⊥; amortized locality bounds queries per recovered symbol.An arLCC instead recovers codeword symbols over an interval.Source: §3 · pp. 11–12

3.1 Expander Codes and VLTCs

  • Expander codes are locally testable within a prescribed distance of a codeword, and unique expanders yield nontrivial vicinity testing.The tester has perfect completeness and bounded query complexity.Source: §3.1 · pp. 13–14

3.2 Nested Codes

  • A nested code combines constraints from two codes, while recursive nesting applies this operation through a sequence of codes.The nested-code results bound rate loss and characterize relative distance.Source: §3.2 · pp. 14–15

4 Fuzzy Block Decoding Codes

The section develops fuzzy block decoding codes (FBDCs), which relax recovery of predefined codeword blocks, and outlines their construction from nested expander codes and their use as a step toward amortized local correction.

4 Fuzzy Block Decoding Codes

  • FBDCs let a block decoder return a block with up to a specified fraction of errors or output ⊥ when it detects corruption.The block decoder has a verbatim property: a non-⊥ output is the queried block without modifications.Source: §4 · pp. 15–16
  • The construction recursively nests expander codes and applies their vicinity-testers to decode blocks.The encoding is described as a recursively nested code, with tester calls at successive levels.Source: §4 · pp. 16–17
  • The block decoder is complete on codewords, and its soundness analysis bounds the chance that tester invocations fail to detect corruption.Its query count includes the tester queries and the queries needed to recover the final block.Source: §4 · p. 17
  • Top-level amplification raises the FBDC error tolerance by nesting a suitable vicinity-testable code over the base FBDC.The resulting code has the stated rate bound in the theorem.Source: §4 · p. 18
  • The section uses an additional nesting step with a block error-correcting code to transform an FBDC into an amortized relaxed locally correctable code.The transformation's parameters depend on the FBDC and block-code parameters.Source: §4 · p. 18

5 Amortized Correctability to Amortized Decodability

The section converts amortized local correction into amortized local decoding by making message-bearing blocks sufficiently dense, at the cost of reducing rate.

5 Amortized Correctability to Amortized Decodability

  • Uneven message-symbol distribution across blocks can increase amortized locality when many consecutive blocks contain few message symbols.The filtering transformation discards bad blocks, lowering rate so each remaining message-bearing block has a high message-symbol proportion.Source: §5 · p. 20
  • A recursively nested systematic code can be made c-message smooth by removing lowest-level blocks with too few message symbols.The smoothing transformation retains the same lowest-level block size and incurs rate loss.Source: §5 · pp. 20–21
  • Smoothing ensures each recovered block contains a c fraction of message symbols, trading rate for an amortized-locality increase by a factor of 1/c.This converts the block-recovery guarantee into recovery of message symbols.Source: §5 · p. 21

6 All Together: Instantiating the Ideal Construction

The construction combines nested expander codes, top-level amplification, block-code nesting, and message smoothing to obtain an explicit ideal arLDC.

6 All Together: Instantiating the Ideal Construction

  • The construction instantiates the FBDC with explicit expanders, converts it to an arLCC using a block code, then smooths it to obtain an arLDC.The explicit expander family is used to build the nested FBDC.Source: §6 · pp. 21–22
  • α = O(1), δ = Ω(1), and rate 1 − R_arLDC ≥ Ω(1) for an explicit arLDC with κ = log(1/ε) × (log n)^2 × 2^(log log log n)^4.Theorem 24 states these parameters for n = 2^r and ε < 1.Source: §6 · p. 22
  • Finally, taking c = (1−RarLCC)/2 yields a (α = O(2α′/(1−RarLCC)) = O(1), κ = B, δ, ε)-arLDC with rate 1 −RarLDC ≥1−RarLCC.Source: §6 · p. 23

7 Amortized Locality Less Than 2

The section refines the amortized relaxed locally decodable code construction to achieve amortized locality below 2, and, with a different parameter regime, locality approaching 1. It also presents an efficient binary code construction used in the refinement.

7 Amortized Locality Less Than 2

  • The construction modifies the prior one by using a higher-rate, lower-error-tolerance code for lowest-level blocks, increasing κ, and carefully choosing c in bad-block filtering.These changes are used to obtain amortized locality below 2.Source: §7 · p. 24

7.1 Refining the arLDC Amortized Locality

  • The explicit construction achieves amortized locality α=5/3 with constant rate and constant error tolerance under the stated parameter conditions.The section also gives a general bound below 2 for the refined construction.Source: §7 · p. 23, §7.1 · p. 25
  • When R(δ)=o(1), an alternate parameter choice gives amortized locality and rate approaching 1.For fixed ν, the corollary gives α(δ,ν)=(1+ν)×(1+o(1)); an example gives rate 1−o(1) and locality at most 1+ν′ for sufficiently large n.Source: §7.1 · p. 25
  • A generic arLCC-to-arLDC filtering step imposes α≥1/(1−R), so this construction approaches locality 1 only as error tolerance approaches 0.Achieving locality approaching 1 with both constant rate and constant error tolerance is left as future work for a direct construction.Source: §7.1 · p. 25

7.2 An Explicit Binary Code with Rate Approaching 1

  • The section presents an efficient binary-code construction with rate 1−o(1), computable in time max{n^ε,O(n)}.The construction uses concatenation of a Reed–Solomon outer code and a binary inner code chosen near the GV-bound.Source: §7.2 · pp. 25–26

A Finding GV-Bound Codes

This appendix gives a deterministic algorithm for finding binary linear codes meeting the GV-bound. It uses exhaustive search over Toeplitz matrices and bounds the search time.

Finding GV-Bound Codes

  • The algorithm exhaustively searches Toeplitz matrices and finds a generator reaching the GV-bound.The proof bounds the probability that a randomly chosen Toeplitz matrix fails, then applies a union bound over nonzero messages.Source: A Finding GV-Bound Codes · pp. 29–30
  • For every 1/2<R≤1, the stated binary-code family has rate at least R and relative distance H^-1(1−R).The passage gives an explicit search-time bound of 2^d(n+k), with d≤3/2.Source: A Finding GV-Bound Codes · p. 30
  • The exhaustive search checks at most 2^(k+n−1) Toeplitz matrices and tests their nonzero message vectors.The resulting running-time bound is at most 2^(3/2)(n+k).Source: A Finding GV-Bound Codes · p. 30

B Impossibility of One-Query Relaxed Decoding with Perfect Completeness

The appendix proves that a one-query relaxed locally decodable code with perfect completeness cannot use the failure output. It then applies the Katz–Trevisan impossibility argument to rule out such one-query codes.

Impossibility of One-Query Relaxed Decoding with Perfect Completeness

  • The impossibility proof extracts many good codeword indices for each message index, then uses averaging and pigeonholing to obtain a single-symbol encoding for many message indices.An information-theoretic bound then limits how many such indices there can be.Source: B Impossibility of One-Query Relaxed… · pp. 30–32
  • The proof adapts the Katz–Trevisan argument for one-query LDCs to relaxed decoding by first showing that the decoder cannot use ⊥.The passage identifies the original argument as Katz and Trevisan.Source: B Impossibility of One-Query Relaxed… · pp. 30–31
  • Perfect completeness forces a one-query rLDC decoder never to output ⊥, making it an LDC decoder.The proof fixes a query and contrasts codewords whose target message symbols differ.Source: B Impossibility of One-Query Relaxed… · pp. 30–31

C Additional Discussion of Related Work

The discussion contrasts the paper’s amortized relaxed-decoding approach with prior amortized decoding, multipoint recovery, and batch-code work. It identifies open questions about ideal amortized codes and extensions to insertion and deletion errors.

Additional Discussion of Related Work

  • Prior ideal aLDC constructions relied on shared randomness or resource-bounded channels, while this work uses a decoder relaxation for an information-theoretic construction.The discussion leaves open whether ideal aLDCs can be built without relaxation or non-information-theoretic assumptions.Source: C Additional Discussion of Related Work · p. 32
  • Reed–Muller multipoint recovery gives constant amortized locality at constant alphabet size but has sub-constant rate; increasing alphabet size raises amortized locality.The discussion says ideal aLDC existence remains open even over non-constant-size alphabets.Source: C Additional Discussion of Related Work · p. 32
  • The cited erasure-tolerant batch-code result assumes κ=ℓ, and whether similar bounds hold when κ≠ℓ remains open.In that setting, the repetition code has optimal codeword length even for large request sets.Source: C Additional Discussion of Related Work · pp. 32–33
Loading 2609.16332v1…