Title: Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes Show Chinese title

Title: 概率保证到显式构造：线性码的局部性质

Abstract: We present a general framework for derandomizing random linear codes with respect to a broad class of permutation-invariant properties, known as local properties, which encompass several standard notions such as distance, list-decoding, list-recovery, and perfect hashing. Our approach extends the classical Alon-Edmonds-Luby (AEL) construction through a modified formalism of local coordinate-wise linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (2025). The main theorem demonstrates that if random linear codes satisfy the complement of an LCL property $\mathcal{P}$ with high probability, then one can construct explicit codes satisfying the complement of $\mathcal{P}$ as well, with an enlarged yet constant alphabet size. This gives the first explicit constructions for list recovery, as well as special cases (e.g., list recovery with erasures, zero-error list recovery, perfect hash matrices), with parameters matching those of random linear codes. More broadly, our constructions realize the full range of parameters associated with these properties at the same level of optimality as in the random setting, thereby offering a systematic pathway from probabilistic guarantees to explicit codes that attain them. Furthermore, our derandomization of random linear codes also admits efficient (list) decoding via recently developed expander-based decoders. Show Chinese abstract

Abstract: 我们提出了一种通用框架，用于对与广义的排列不变性质（称为局部性质）相关的随机线性码进行去随机化，这些性质包括距离、列表解码、列表恢复和完美哈希等几个标准概念。 我们的方法通过一种由Levi、Mosheiff和Shagrithaya（2025）引入的局部坐标线性（LCL）性质的修改形式，扩展了经典的Alon-Edmonds-Luby（AEL）构造。 主定理表明，如果随机线性码以高概率满足LCL性质$\mathcal{P}$的补集，则可以构造出满足$\mathcal{P}$补集的显式码，且字母表大小扩大但保持常数。 这给出了列表恢复的第一个显式构造，以及一些特殊情况（例如，带有删除的列表恢复、零错误列表恢复、完美哈希矩阵），其参数与随机线性码相匹配。 更广泛地说，我们的构造实现了这些性质相关参数的完整范围，在最优性水平上与随机情况相同，从而提供了一条从概率保证到达到这些保证的显式码的系统路径。 此外，我们的随机线性码的去随机化也通过最近开发的基于扩展器的解码器实现了高效的（列表）解码。