论文标题
晶格（列表）在Minkowski的不平等附近解码
Lattice (List) Decoding Near Minkowski's Inequality
论文作者
论文摘要
Minkowski证明了单位确定剂的任何$ n $二维晶格最多都具有欧几里得Norm的非零矢量，最多$ \ sqrt {n} $;实际上，有$ 2^{ω（n）} $此类晶格向量。最小距离接近Minkowski的BOND的晶格提供了出色的球形包装和错误校正的代码。 这项工作的重点是由于Barnes和Sloane引起的某种有效构造的$ N $维晶格的家族，其最小距离在Minkowski绑定的$ O（\ sqrt {\ log n}）$中。我们的主要贡献是一种多项式时间算法，列表将该家族解码为接近最小距离的$ 1/\ sqrt {2} $的距离。主要技术是使用Guruswami-Sudan列表描述算法的koetter-vardy“软决策”变体来解码在欧几里得规范中测得的误差的芦苇 - 固体代码。
Minkowski proved that any $n$-dimensional lattice of unit determinant has a nonzero vector of Euclidean norm at most $\sqrt{n}$; in fact, there are $2^{Ω(n)}$ such lattice vectors. Lattices whose minimum distances come close to Minkowski's bound provide excellent sphere packings and error-correcting codes in $\mathbb{R}^{n}$. The focus of this work is a certain family of efficiently constructible $n$-dimensional lattices due to Barnes and Sloane, whose minimum distances are within an $O(\sqrt{\log n})$ factor of Minkowski's bound. Our primary contribution is a polynomial-time algorithm that list decodes this family to distances approaching $1/\sqrt{2}$ of the minimum distance. The main technique is to decode Reed-Solomon codes under error measured in the Euclidean norm, using the Koetter-Vardy "soft decision" variant of the Guruswami-Sudan list-decoding algorithm.
