Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-124 | 15th September 2011 11:20

Algorithms for the Coin Weighing Problems with the Presence of Noise

RSS-Feed




TR11-124
Authors: Nader Bshouty, Hanna Mazzawi
Publication: 16th September 2011 14:01
Downloads: 3486
Keywords: 


Abstract:

The coin weighing problem is the following: Given $n$ coins for which $m$ of them are counterfeit with the same weight. The problem is to detect the counterfeit coins with minimal number of weighings. This problem has many applications in compressed sensing, multiple access adder channels, etc. The problem was solved when $m$ is unknown. An old optimal non-adaptive polynomial time algorithm of Lindstrom does $O(n /\log n)$ weighings and detect the counterfeit coins. In this paper we give a non-adaptive polynomial time algorithm that does $O(n/log n)$ weighings and detect the counterfeit coins even if $n^c$ of the answers of the weighings received are incorrect or missing for any constant $c < 1$.

When $m$ is known we give an adaptive polynomial time algorithm that does $O((m\log n)/\log m)$ weighings and detect the counterfeit coins even if $m^c$ of the answers of the weighings received are incorrect or missing for any constant $c < 1$.

We then study the problem when $m$ is known
and the counterfeit coins have different weights. We show that there is an optimal non-adaptive algorithm for detecting the counterfeit coins with $O((m\log n)/\log m)$ weighing even if $11$ percent of the answers are incorrect or missing.

A simple information theoretical argument shows
that all the above algorithm are optimal.



ISSN 1433-8092 | Imprint