Locally Decodable Code (LDC) is a code that encodes a message in a way that one can decode any particular symbol of the message by reading only a constant number of locations, even if a constant fraction of the encoded message is adversarially corrupted.In this paper we present a new approach for the construction of LDCs. We show that if there exists an irreducible representation (V) of G and q elements g1g2gq in G such that there exists a linear combination of matrices (gi) that is of rank one, then we can construct a q-query Locally Decodable CodeC:VFG.We show the potential of this approach by constructing constant query LDCs of sub-exponential length matching the parameters of the best known constructions
展开▼
机译：本地可解码代码（LDC）是一种以一种方式对消息进行编码的代码，即即使恒定比例的编码消息遭到了破坏，也可以通过读取恒定数量的位置来解码消息的任何特定符号。本文我们提出了一种最不发达国家的新建设方法。我们证明，如果存在G的不可约表示（V）和G中的q个元素g1g2gq使得存在第一级矩阵（gi）的线性组合，那么我们可以构造一个q查询局部可解码的CodeC： V FG。我们通过构造与最著名结构的参数匹配的次指数长度的常量查询LDC来展示这种方法的潜力
展开▼
