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(nlogn) weighings and detect the counterfeit coins. In this paper we give a non-adaptive polynomial time algorithm that does O(nlogn) weighings and detect the counterfeit coins even if nc of the answers of the weighings received are incorrect or missing for any constant c1.

When m is known we give an adaptive polynomial time algorithm that does O((mlogn)logm) weighings and detect the counterfeit coins even if mc of the answers of the weighings received are incorrect or missing for any constant c1.

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

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