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

文章基本信息

  • 标题:Lower Bounds for Approximate LDCs
  • 本地全文:下载
  • 作者:Jop Briet ; Zeev Dvir ; Guangda Hu
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We study an approximate version of q-query LDCs (Locally Decodable Codes) over the real numbers and prove lower bounds on the encoding length of such codes. A q-query () -approximate LDC is a set V of n points in Rd so that, for each i[d] there are (n) disjoint q-tuples (u1uq) in V so that span(u1uq) contains a unit vector whose i'th coordinate is at least . We prove exponential lower bounds of the form n2(d) for the case q=2 and, in some cases, stronger bounds (exponential in d).

国家哲学社会科学文献中心版权所有