Date: 11:00-12:00, Dec 4, 2015
Speaker: Jeong Han Kim, Korea Institute for Advanced Study (KIAS)
https://en.wikipedia.org/wiki/Jeong_Han_Kim
Title: How to find counterfeit coins?  An algorithmic version.
Abstract:
 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, b>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.
 No prior knowledge of graph theory is needed in this talk.
host: Ken-ichi Kawarabayashi（NII, A02)