Clustering Via Crowdsourcing
  In recent years, crowdsourcing, aka human aided computation has emerged as an
effective platform for solving problems that are considered complex for
machines alone. Using human is time-consuming and costly due to monetary
compensations. Therefore, a crowd based algorithm must judiciously use any
information computed through an automated process, and ask minimum number of
questions to the crowd adaptively.
  One such problem which has received significant attention is {\em entity
resolution}. Formally, we are given a graph $G=(V,E)$ with unknown edge set $E$
where $G$ is a union of $k$ (again unknown, but typically large $O(n^\alpha)$,
for $\alpha>0$) disjoint cliques $G_i(V_i, E_i)$, $i =1, \dots, k$. The goal is
to retrieve the sets $V_i$s by making minimum number of pair-wise queries $V
\times V\to\{\pm1\}$ to an oracle (the crowd). When the answer to each query is
correct, e.g. via resampling, then this reduces to finding connected components
in a graph. On the other hand, when crowd answers may be incorrect, it
corresponds to clustering over minimum number of noisy inputs. Even, with
perfect answers, a simple lower and upper bound of $\Theta(nk)$ on query
complexity can be shown. A major contribution of this paper is to reduce the
query complexity to linear or even sublinear in $n$ when mild side information
is provided by a machine, and even in presence of crowd errors which are not
correctable via resampling. We develop new information theoretic lower bounds
on the query complexity of clustering with side information and errors, and our
upper bounds closely match with them. Our algorithms are naturally
parallelizable, and also give near-optimal bounds on the number of adaptive
rounds required to match the query complexity.
