FYI (CS Colloquium)

An Algorithmic Version

KIAS

E3-1 CS Bldg. Room 1501

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 \geq 2\) and the weight \(w(c)\) of each counterfeit coin c satisfies \(\alpha \leq |w(c)| \leq \beta\) for fixed constants \(\alpha, \beta>0\). 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.