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

文章基本信息

  • 标题:Locally Testable Codes and Cayley Graphs
  • 本地全文:下载
  • 作者:Parikshit Gopalan ; Salil Vadhan ; Yuan Zhou
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2013
  • 卷号:2013
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We give two new characterizations of (smooth, \F2-linear) locally testable error-correcting codes in terms of Cayley graphs over \Fh2:

    \begin{enumerate}\item A locally testable code is equivalent to a Cayley graph over \Fh2 whose set of generators is significantly larger than h and has no short linear dependencies, but yields a shortest-path metric that embeds into 1 with constant distortion. This extends and gives a converse to a result of Khot and Naor (2006), which showed that codes with large dual distance imply Cayley graphs that have no low-distortion embeddings into 1.

    \item A locally testable code is equivalent to a Cayley graph over \Fh2 that has significantly more than h eigenvalues near 1, which have no short linear dependencies among them and which ``explain'' all of the large eigenvalues. This extends and gives a converse to a recent construction of Barak et al. (2012), which showed that locally testable codes imply Cayley graphs that are small-set expanders but have many large eigenvalues.

    \end{enumerate}

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