This paper considers a generalized version of the coin weighing problem with a spring scale that lies at the intersection of group testing and compressed sensing problems. Given a collection of @math coins of total weight @math (for a known integer @math ), where the weight of each coin is an unknown integer in the range of @math (for a known integer @math ), the problem is to determine the weight of each coin by weighing subsets of coins in a spring scale. The goal is to minimize the average number of weighings over all possible weight configurations. For @math , an adaptive bisecting weighing strategy is known to be optimal. However, even the case of @math , which is the simplest non-trivial case of the problem, is still open. For this case, we propose and analyze a simple and effective adaptive weighing strategy. A numerical evaluation of the exact recursive formulas, derived for the analysis of the proposed strategy, shows that this strategy requires about @math weighings on average. To the best of our knowledge, this is the first non-trivial achievable upper bound on the minimum expected required number of weighings for the case of @math . As @math grows unbounded, the proposed strategy, when compared to an optimal strategy within the commonly-used class of nested strategies, requires about @math less number of weighings on average; and in comparison with the information-theoretic lower bound, it requires at most about @math extra number of weighings on average.
Suppose we are given n coins out of a collection of coins of two distinct weights w0 and w1, true and counterfeit coins, respectively, where d of them are counterfeit coins. Assume we are allowed to weigh subsets of coins in a spring scale. Determine the counterfeit coins in a minimal number of weighing. This problem is equivalent to the following learning problem: Given a linear function f = xi1 + xi2 + · · ·+ xid , where 1 ≤ i1 < i2 < · · · < id ≤ n and a substitution oracle of values in the domain 0, 1 n to f . Find f with minimal number of substitution queries. In this paper we give the first optimal1. (in the number of weighing or substitutions) polynomial time adaptive algorithm that determines the counterfeit coins. We then extend our algorithm to the following more general coin weighing problems with a spring scale: Suppose we are given n coins out of a collection of coins of unknown integer weights. Determine the weight of each coin in a minimal number of weighing. We give an optimal adaptive polynomial time algorithm for this problem. This algorithm is based on a new optimal adaptive algorithm for reconstructing bounded weight vectors in polynomial time. This solves the general problem of learning any linear function with bounded integer coefficient in polynomial time with optimal number of substitution queries. To the best of our knowledge all the algorithms in this paper are the first optimal polynomial time adaptive algorithms for the problem of coin weighing in a spring scale.  Abstract The determination of defective elemets in a population by a series of group tests has received considerable attention. In this paper, the following natural generalization to graphs is studied. Given a graph G with vertex-set V and edge-set E , and an unknown edge e ∗ ϵE . In order to find e ∗ we choose a sequence of tests-sets A ⊆ V where after every test we are told whether e ∗ has both end-vertices in A , one end-vertex, or lies outside. Find the minimum c ( G ) of tests required. c ( G ) is studied in detail for the complete graphs K n and the complete bipartite graphs K m , n . Remarks are made on optimal graphs which achieve the information-theoretic lower bound and on a previously studied binary variant. Abstract Consider a linearly ordered set L of cardinality n of which exactly d elements are defective. We want to determine the subset D of defective elements by a series of group tests. The possible test sets are all lower and upper intervals and after every test A we receive as answer | A ∩ D |, i.e. the exact number of defective elements in A . In this paper the minimum number D ( d , n ) of group tests necessary to specify D is determined for all d and n . We propose a novel group testing method, termed semiquantitative group testing (SQGT), motivated by a class of problems arising in genome screening experiments. The SQGT is a (possibly) nonbinary pooling scheme that may be viewed as a concatenation of an adder channel and an integer-valued quantizer. In its full generality, SQGT may be viewed as a unifying framework for group testing, in the sense that most group testing models are special instances of SQGT. For the new testing scheme, we define the notion of SQ-disjunct and SQ-separable codes, representing generalizations of classical disjunct and separable codes. We describe several combinatorial and probabilistic constructions for such codes. While for most of these constructions, we assume that the number of defectives is much smaller than total number of test subjects, we also consider the case in which there is no restriction on the number of defectives and they may be as large as the total number of subjects. For the codes constructed in this paper, we describe a number of efficient decoding algorithms. In addition, we describe a belief propagation decoder for sparse SQGT codes for which no other efficient decoder is currently known.  In this paper, we consider the problem of multi-level group testing, where the goal is to recover a set of K defective items in a set of n items by pooling groups of items and observing the result of each test. The main difference of multilevel group testing with the classical non-adaptive group testing problem is that the result of each test is an integer in the set [L] = 0,1, • • •, L : if there are i < L defective items in the pool, the result of the test is i, and if there are more than L items in the pool, the result of the test is L. We develop a multilevel group testing algorithm using sparse-graph codes that has low sample and computational complexity. More precisely, with high probability, our algorithm provably recovers (1 — ∊) fraction of the defective items using C(∊, L)K log(n) tests, where C(∊, L) is a constant that only depends on ∊ and the number of levels L, and it can be precisely characterized for arbitrary L and e. Furthermore, the computational complexity of our algorithm is O(K log(n)). As an example, our algorithm is able to recover (1 — 10−3) fraction of the defective items with only 13.8K log(n) measurements for L = 2. We also provide numerical results that show tight agreement with our theoretical results.   