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.