In this talk, we consider a well-known combinatorial search problem. Suppose that there are $n$ identical looking coins and some of them are counterfeit.
The weights of all authentic coins are the same and known a priori. The weights of counterfeit coins vary but different from the weight of an authentic coin.
Without loss of generality, we may assume the weight of authentic coins is $0$. The problem is to find all counterfeit coins by weighing (queries) sets of coins on a spring scale. Finding the optimal number of queries is difficult even when there are only 2 counterfeit coins.
We introduce a polynomial time randomized algorithm to find all counterfeit coins when the number of them is known to be at most $m 1$ and the weight $w(c)$ of each counterfeit coin $c$ satisfies
$a |w(c)| b$
for fixed constants $a, b0$. The query complexity of the algorithm is $O(\frac{m \log n }{\log m})$, which is optimal up to a constant factor. The algorithm uses, in part, random walks.
The algorithm may be generalized to find all edges of a hidden weighted graph using a similar type of queries. This graph finding algorithm has various applications including DNA sequencing.