列表可恢复编码：已知成果、局限性与未解之谜（但愿不丑陋） (List Recoverable Codes: The Good, the Bad, and the Unknown (hopefully not Ugly))

List recovery is a fundamental task for error-correcting codes, vastly generalizing unique decoding from worst-case errors and list decoding. Briefly, one is given ''soft information'' in the form of input lists S_1,...,S_n of bounded size, and one argues that there are not too many codewords that agree a lot with this soft information. This general problem appears in many guises, both within coding theory and in theoretical computer science more broadly. In this article we survey recent results on list recovery codes, introducing both the ''good'' (i.e., possibility results, showing that codes with certain list recoverability exist), the ''bad'' (impossibility results), and the ''unknown''. We additionally demonstrate that, while list recoverable codes were initially introduced as a component in list decoding concatenated codes, they have since found myriad applications to and connections with other topics in theoretical computer science.

翻译：列表恢复是纠错编码的一项基本任务，它极大地推广了最坏情况错误下的唯一解码和列表解码。简而言之，该任务接收以有界大小的输入列表S_1,...,S_n形式呈现的"软信息"，并论证与此软信息高度一致的码字数量不会过多。这一广义问题以多种形式出现，既存在于编码理论内部，也广泛存在于理论计算机科学的其他领域。本文综述了列表可恢复编码的最新研究成果，既介绍了"已知成果"（即可能性结果，证明具有特定列表可恢复性的编码存在），也阐述了"局限性"（不可能性结果）与"未解之谜"。此外，我们论证了尽管列表可恢复编码最初是作为级联码列表解码的组成部分被提出的，但此后已在理论计算机科学的其他领域发现了大量应用并建立了广泛联系。