Amortized relaxed codes enable efficient data recovery with low probes
Amortized Relaxed Locally Decodable Codes
Information TheoryDiscrete Mathematics
Summary
Locally decodable codes let you recover parts of a message by checking only a few spots in the coded data, even if some parts got messed up, but making them work well for many parameters at once is hard. The authors worked on a new kind of code that combines two relaxations—decoding multiple message parts at once and allowing the decoder to say "I don’t know" sometimes instead of making mistakes. They built such codes that achieve good rates, tolerate errors, and require very few probes per symbol on average, without relying on assumptions about the communication channel or secret randomness. This advances the theoretical possibilities for error-correcting codes in noisy environments.
What this means in practice
- •For storage system engineers: Design error-correcting schemes that quickly recover multiple data symbols with fewer accesses per symbol on average, improving read efficiency under adversarial noise.
- •For distributed database developers: Implement coding strategies that tolerate data corruption while enabling fast retrieval of blocks of records with minimal probe queries.
Authors
Jeremiah Blocki, Justin Zhang
Abstract
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 $Ω(\mathrm{polylog}(k))$, our decoder achieves amortized locality $1+δ^{1 - o(1)}$, where $δ$ 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.