New Codes on High Dimensional Expanders
New Codes on High Dimensional Expanders
复制标题
高维扩展器的新代码
DOI：
10.48550/arxiv.2308.15563
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
R. Zhang
中科院分区：
文献类型：
--
作者：
Irit Dinur;Siqi Liu;R. Zhang
描述了一类新的参数化低密度奇偶校验矩阵对称纠错码(LDPC)。我们的代码可以用两种看似不同的方式来描述。首先，关于Reed-Muller码：我们的码是$\mathbb{F}^n$的子集上的函数，它对给定的仿射直线集的限制是低次的。或者，它们是高维扩展器上的Tanner代码，其中码字的坐标对应于$2维扩展器的三角形，使得局部视图在每条边周围形成里德-所罗门码字。对于某些参数范围，我们的代码是可证明的局部可测试的，并且它们的维度是块长度的某个固定幂。对于另一范围的参数，我们的代码具有在块长度中线性的距离和尺寸，但我们不知道它们是否可局部测试。码还具有乘法特性：两个码字的坐标方向乘积是相关代码中的一个码字。码的定义依赖于构造一族特定的单纯复形，它是Kaufman和Oppenheim的陪集复形的一个微小变体。我们给出了一种新的方法来将这些复合体的三角形嵌入到$\mathbb{F}^n$中，利用边的连接作为仿射线嵌入到$\mathbb{F}^n$中的性质。我们依靠这种嵌入，以一种避免约束计数的方式来降低这些码的码率，从而即使当局部码本身具有任意小的码率，特别是低于$1/2$时，也能获得非平凡的码率。
We describe a new parameterized family of symmetric error-correcting codes with low-density parity-check matrices (LDPC). Our codes can be described in two seemingly different ways. First, in relation to Reed-Muller codes: our codes are functions on a subset of $\mathbb{F}^n$ whose restrictions to a prescribed set of affine lines has low degree. Alternatively, they are Tanner codes on high dimensional expanders, where the coordinates of the codeword correspond to triangles of a $2$-dimensional expander, such that around every edge the local view forms a Reed-Solomon codeword. For some range of parameters our codes are provably locally testable, and their dimension is some fixed power of the block length. For another range of parameters our codes have distance and dimension that are both linear in the block length, but we do not know if they are locally testable. The codes also have the multiplication property: the coordinate-wise product of two codewords is a codeword in a related code. The definition of the codes relies on the construction of a specific family of simplicial complexes which is a slight variant on the coset complexes of Kaufman and Oppenheim. We show a novel way to embed the triangles of these complexes into $\mathbb{F}^n$, with the property that links of edges embed as affine lines in $\mathbb{F}^n$. We rely on this embedding to lower bound the rate of these codes in a way that avoids constraint-counting and thereby achieves non-trivial rate even when the local codes themselves have arbitrarily small rate, and in particular below $1/2$.
通过高维扩展器进行本地可测试代码
DOI：
--
发表时间：
2020
期刊：
Electronic colloquium on computational complexity
影响因子：
--
作者：
Dikstein, Y;Dinur, I;Harsha, P;Ron-Zewi, N.
通讯作者：
Ron-Zewi, N.
通过部分提升代码的局部性
影响因子：
--
作者：
Frank-Fischer, S. Luna;Guruswami, Venkatesan;Wootters, Mary
通讯作者：
Wootters, Mary