首页    期刊浏览 2024年12月11日 星期三
登录注册

文章基本信息

  • 标题:On Embeddings of k 1 from Locally Decodable Codes
  • 本地全文:下载
  • 作者:Jop Briet
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2015
  • 卷号:2015
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We show that any q -query locally decodable code (LDC) gives a copy of 1 k with small distortion in the Banach space of q -linear forms on N p 1 N p q , provided 1 p 1 + + 1 p q 1 and where k , N , and the distortion are simple functions of the code parameters. We exhibit the copies of 1 k by constructing a basis directly from "smooth" LDC decoders, thus bypassing a matching lemma often used in the LDC literature. Based on this, we give alternative proofs for known lower bounds on the length of 2-query LDCs. Using similar techniques, we reprove known lower bounds for larger q . We also discuss the relation with an alternative proof, due to Pisier, of a result of Naor, Regev, and the author on cotype properties of projective tensor products of p spaces.

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