A query efficient non‐adaptive long code test with perfect completeness1. Issue 2 (8th January 2015) - Tamaki, Suguru; Yoshida, Yuichi
Abstract: Long Code testing is a fundamental problem in the area of property testing and hardness of approximation. In this paper, we study how small the soundness s of the Long Code test with perfect completeness can be by using non‐adaptive q queries. We show that s = (2 q + 3)/2 q is possible, where q is of the form 2 k − 1 for any integer k > 2. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 386–406, 2015