A query efficient non‐adaptive long code test with perfect completeness
A query efficient non‐adaptive long code test with perfect completeness
复制标题
DOI：
10.1002/rsa.20549
复制
发表时间：
2010-09
影响因子：
1
通讯作者：
Suguru Tamaki;Yuichi Yoshida
中科院分区：
文献类型：
--
作者：
Suguru Tamaki;Yuichi Yoshida
长码测试是性能测试和逼近困难领域的一个基本问题。在本文中，我们研究如何小的可靠性长码测试完美的完整性可以通过使用非自适应q查询。我们证明了s =（2 q + 3）/2 q是可能的，其中对于任意整数k > 2，q的形式为2k−1。© 2014 Wiley Periodicals，Inc.随机结构算法，47，386-406，2015
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 2k−1 for any integer k > 2. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 386–406, 2015