Short Locally Testable Codes and Proofs: A Survey in Two Parts
Short Locally Testable Codes and Proofs: A Survey in Two Parts
复制标题
简短的本地可测试代码和证明：分为两部分的调查
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Oded Goldreich
中科院分区：
文献类型：
--
作者：
Oded Goldreich
我们综述了有关局部可测码和局部可测证明（也称为概率可验证明，PCPs）的已知结果，重点关注这些构造的长度。局部可测性是指基于极少量的探测来近似测试大型对象，每次探测获取对象表示中的单个比特。这使得能够对相应的性质（即，是一个码字或一个有效证明）进行超快速的近似测试。我们还回顾了局部可解码的相关概念。
本综述由两个独立（即自成一体）的部分组成，它们在不同的严谨性和详细程度上涵盖了相同的材料。尽管存在重复，但阅读两个部分可能是有益的。
We survey known results regarding locally testable codes and locally testable proofs (known as PCPs), with emphasis on the length of these constructs. Local testability refers to approximately testing large objects based on a very small number of probes, each retrieving a single bit in the representation of the object. This yields super-fast approximatetesting of the corresponding property (i.e., be a codeword or a valid proof). We also review the related concept of local decodable codes.
The survey consists of two independent (i.e., self-contained) parts that cover the same material at different levels of rigor and detail. Still, in spite of the repetitions, there may be a benefit in reading both parts.