A query efficient non‐adaptive long code test with perfect completeness. Issue 2 (8th January 2015)

• Record Type: Journal Article
• Authors: Tamaki, Suguru; Yoshida, Yuichi
• Is Part Of: Random structures & algorithms. Volume 47:Issue 2(2015)
• Page Start: 386
• Page End: 406
• Publication Date: 2015-01-08
• Subjects: long code test -- dictatorship test -- influence of variables -- amortized query complexity; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20549
• Languages: English
• ISSNs: 1042-9832

Abstract

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