김정한

Archive of posts with tag '김정한'

  • (CS Colloquium) Jeong Han Kim, How to Find Counterfeit Coins? An Algorithmic Version

    FYI (CS Colloquium)

    How to Find Counterfeit Coins?
    An Algorithmic Version
    Jeong Han Kim
    KIAS
    2014/11/17 Monday 4PM – 5:30PM
    E3-1 CS Bldg. Room 1501
    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 \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.
    Tags:

  • Jeong-Han Kim (김정한), How to find counterfeit coins? An algorithmic version.
    How to find counterfeit coins? An algorithmic version.
    Jeong-Han Kim (김정한)
    Dept. of Mathematics, Yonsei University, Seoul, Korea.
    2012/05/03 Thu 4PM-5PM
    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 sets of coins (queries) 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≥2 and the weight w(c) of each counterfeit coin c satisfies α≤|w(c)|≤β for fixed constants α, β>0. The query complexity of the algorithm is O((m log n)/log m), which is optimal up to a constant factor. The algorithm uses, in part, random walks.
    We will also discuss the problem of finding edges of a hidden weighted graph using a certain type of queries.
    Tags:

  • Jeong-Han Kim (김정한), Optimal Query Complexity Bounds for Finding Graphs
    Optimal Query Complexity Bounds for Finding Graphs
    Jeong-Han Kim (김정한)
    Dept. of Mathematics, Yonsei University, Seoul, Korea.
    2008/05/16 Fri, 4PM-5PM

    We consider the problem of finding an unknown graph by using two types of queries with an additive property. Given a graph, an additive query asks the number of edges in a set of vertices while a cross-additive query asks the number of edges crossing between two disjoint sets of vertices. The queries ask sum of weights for the weighted graphs. These types of queries were partially motivated in DNA shotgun sequencing and linkage discovery problem of artificial intelligence.

    For a given unknown weighted graph G with n vertices, m edges, and a certain mild condition on weights, we prove that there exists a non-adaptive algorithm to find the edges of G using O((m log n)/log m) queries of both types provided that m≤ nε for any constant ε>0. For a graph, it is shown that the same bound holds for all range of m.

    This settles a conjecture of Grebinski for finding an unweighted graph using additive queries. We also consider the problem of finding the Fourier coefficients of a certain class of pseudo-Boolean functions. A similar coin weighing problem is also considered. (Joint work with S. Choi)

    Tags:

Monthly Archives