首页    期刊浏览 2025年07月11日 星期五
登录注册

文章基本信息

  • 标题:From Irreducible Representations to Locally Decodable Codes
  • 本地全文:下载
  • 作者:Klim Efremenko
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2011
  • 卷号:2011
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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:V\FG.

    We show the potential of this approach by constructing constant query LDCs of sub-exponential length matching the parameters of the best known constructions

  • 关键词:Locally decodable codes; Private Information Retrival
国家哲学社会科学文献中心版权所有