  Motivated by many applications, we study clustering with a faulty oracle. In
this problem, there are $n$ items belonging to $k$ unknown clusters, and the
algorithm is allowed to ask the oracle whether two items belong to the same
cluster or not. However, the answer from the oracle is correct only with
probability $\frac{1}{2}+\frac{\delta}{2}$. The goal is to recover the hidden
clusters with minimum number of noisy queries. Previous works have shown that
the problem can be solved with $O(\frac{nk\log n}{\delta^2} +
\text{poly}(k,\frac{1}{\delta}, \log n))$ queries, while
$\Omega(\frac{nk}{\delta^2})$ queries is known to be necessary. So, for any
values of $k$ and $\delta$, there is still a non-trivial gap between upper and
lower bounds. In this work, we obtain the first matching upper and lower bounds
for a wide range of parameters. In particular, a new polynomial time algorithm
with $O(\frac{n(k+\log n)}{\delta^2} + \text{poly}(k,\frac{1}{\delta}, \log
n))$ queries is proposed. Moreover, we prove a new lower bound of
$\Omega(\frac{n\log n}{\delta^2})$, which, combined with the existing
$\Omega(\frac{nk}{\delta^2})$ bound, matches our upper bound up to an additive
$\text{poly}(k,\frac{1}{\delta},\log n)$ term. To obtain the new results, our
main ingredient is an interesting connection between our problem and
multi-armed bandit, which might provide useful insights for other similar
problems.
