期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：A distance estimator is a code together with a randomized algorithm. The algorithm approximates the distance of any word from the code by making a small number of queries to the word. One such example is the Reed-Muller code equipped with an appropriate algorithm. It has polynomial length, polylogarithmic alphabet size, and polylogarithmic number of queries. In our work we present two results. First, we construct a distance estimator with arbitrary small alphabet size, polynomial length, and polylogarithmic number of queries. Second, we construct a distance estimator with sublogarithmic number of queries, almost linear length, and polylogarithmic alphabet size.
Distance estimators are the coding theoretical analog of two-query low-error PCP. A recent work by Moshkovitz and Raz [FOCS'08]established two-query low-error PCP for the first time. In this work we examine whether we can construct a distance estimator via the new technique for PCP. Perhaps surprisingly, the new technique illuminates the difference between codes and PCP; there is an inherent problem with using the technique in the same way that was done for PCP. However, as we see in this work, the technique can be used to construct a distance estimator (up to a point).
To prove our results, we develop a general scheme for showing that a combinatorial operation preserves the distance estimator property.
