A query efficient non‐adaptive long code test with perfect completeness1. Issue 4 (3rd May 2014) - 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 = (2q + 3)/2q is possible, where q is of the form <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh21k9v7kh" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />2k−1</alternatives> for any integer k > 2. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 703–723, 2014