We study the group testing problem with non-adaptive randomized algorithms. Several models have been discussed in the literature to determine how to randomly choose the tests. For a model M, let m(M)(n, d) be the mini...
详细信息
ISBN:
(纸本)9783030389192;9783030389185
We study the group testing problem with non-adaptive randomized algorithms. Several models have been discussed in the literature to determine how to randomly choose the tests. For a model M, let m(M)(n, d) be the minimum number of tests required to detect at most d defectives within n items, with success probability at least 1 - delta, for some constant delta. In this paper, we study the measures c(M)(d) = lim(n ->infinity) m(M)(n, d)/ln n and c(M) = lim(d ->infinity) c(M)(d)/d. In the literature, the analyses of such models only give upper bounds for c(M)(d) and c(M), and for some of them, the bounds are not tight. We give new analyses that yield tight bounds for c(M)(d) and c(M) for all the known models M.
Efficiently counting or detecting defective items is a crucial task in various fields ranging from biological testing to quality control to streaming algorithms. The group testing estimation problem concerns estimatin...
详细信息
Efficiently counting or detecting defective items is a crucial task in various fields ranging from biological testing to quality control to streaming algorithms. The group testing estimation problem concerns estimating the number of defective elements d in a collection of n total within a given factor. We primarily consider the classical query model, in which a query reveals whether the selected group of elements contains a defective one. We show that any non-adaptive randomized algorithm that estimates the value ofd within a constant factor requires ohm(log n ) queries. This confirms that a known O (log n ) upper bound by Bshouty (2019) is tight and resolves a conjecture by Damaschke and Sheikh Muhammad (2010). Additionally, we prove similar matching upper and lower bounds in the threshold query model. Published by Elsevier B.V.
We consider the Conflict Resolution Problem in the context of a multiple-access system in which several stations can transmit their messages with success simultaneously. We assume that there are n stations and at most...
详细信息
We consider the Conflict Resolution Problem in the context of a multiple-access system in which several stations can transmit their messages with success simultaneously. We assume that there are n stations and at most k, k <= n, stations are active at the same time, i.e., are willing to transmit a message. If at most d, d <= k, active stations transmit simultaneously then their messages are successfully transmitted, whereas if more than d active stations transmit simultaneously then their messages are lost. The active stations receive a feedback from the channel that informs them on whether their messages have been successfully transmitted. The measure to optimize is the number of time slots needed to solve conflicts among all active stations, i.e., to make all active stations transmit their messages successfully. We prove that this measure decreases with the number d of messages that can be simultaneously transmitted with success by presenting a conflict resolution algorithm that uses a 1/d ratio of the number of time slots used by the optimal conflict resolution algorithm for the particular case d = 1 [26]. We give a lower bound which is only a log(k/d) factor away from the number of time slots used by the algorithm. The algorithm is obtained via a new kind of the selectors of [13], whereas the lower bound is implied by a non-existential result for a new generalization of the locally thin families of [1,12]. We present also a randomized algorithm that allows to generate the above combinatorial structures in expected polynomial time when k = O(1). (C) 2019 Elsevier B.V. All rights reserved.
In the Group Testing problem, the objective is to learn a subset K of some much larger domain N, using the shortest-possible sequence of queries Q. A feedback to a query provides some information about the intersectio...
详细信息
In the Group Testing problem, the objective is to learn a subset K of some much larger domain N, using the shortest-possible sequence of queries Q. A feedback to a query provides some information about the intersection between the query and subset K. Several specific feedbacks have been studied in the literature, often proving different formulas for the estimate of the query complexity of the problem, defined as the shortest length of queries' sequence solving Group Testing problem with specific feedback. In this paper we study what are the properties of the feedback that influence the query complexity of Group Testing and what is their measurable impact. We propose a generic framework that covers a vast majority of relevant settings considered in the literature, which depends on two fundamental parameters of the feedback: input capacity alpha and output expressiveness beta. They upper bound the logarithm of the size of the feedback function domain and image, respectively. To justify the value of the framework, we prove upper bounds on query complexity of non-adaptive, deterministic Group Testing under some "efficient" feedbacks, for minimum, maximum and general expressiveness, and complement them with a lower bound on all feedbacks with given parameters alpha, beta. Our upper bounds also hold if the feedback function could get an input twisted by a malicious adversary, in case the intersection of a query and the hidden set is bigger than the feedback capacitya. We also show that slight change in the feedback function may result in substantial worsening of the query complexity. Additionally, we analyze explicitly constructed randomized counterparts of the deterministic results. Our results provide some insights to what are the most useful bits of information an output-restricted feedback could provide, and open a number of challenging research directions. (C) 2022 Elsevier B.V. All rights reserved.
In the problem of classical group testing one aims to identify a small subset (of size d) of diseased individuals/defective items in a large population (of size n). This process is based on a minimal number of suitabl...
详细信息
In the problem of classical group testing one aims to identify a small subset (of size d) of diseased individuals/defective items in a large population (of size n). This process is based on a minimal number of suitably-designed group tests on subsets of items, where the test outcome is positive iff the given test contains at least one defective item. Motivated by physical considerations, such as scenarios with imperfect test apparatus, we consider a generalized setting that includes as special cases multiple other group-testing-like models in the literature. In our setting the test outcome is governed by an arbitrary monotonically increasing (stochastic) test function f (.), with the test outcome being positive with probability f (x), where x is the number of defectives tested in that pool. This formulation subsumes as special cases a variety of noiseless and noisy group-testing models in the literature. Our main contributions are as follows. Firstly, for any monotone test function f (.) we present a non-adaptive scheme that with probability 1 - 6 identifies all defective items. Our scheme requires at most O (?(f )d log (n )) tests, where ?(f ) e is a suitably defined "sensitivity parameter" of f (.), and is never larger than O (d1+o(1)), but indeed can be substantially smaller for a variety of f (.). Secondly, we argue that any non-adaptive group testing scheme needs at least O ((1 - 6)? (f )d log (n )) d tests to ensure high reliability recovery. Here ? (f ) is a suitably defined "concentration parameter" of f (.), and ? (f ) ? O(1). Thirdly, we prove that our sample-complexity bounds for generalized group testing are information-theoretically near-optimal for a variety of sparse-recovery group-testing models in the literature. That is, for any "noisy" test function f (.) (i.e., 0 < f (0) < f (d) < 1), and for a variety of "(one-sided) noiseless" test functions f (.) (i.e., either f (0) = 0, or f (d) = 1, or both) studied in the literature we show that ?(f ) ? (f
暂无评论