  In this work we consider the problem of recovering $n$ discrete random
variables $x_i\in \{0,\ldots,k-1\}, 1 \leq i \leq n$ (where $k$ is constant)
with the smallest possible number of queries to a noisy oracle that returns for
a given query pair $(x_i,x_j)$ a noisy measurement of their modulo $k$ pairwise
difference, i.e., $y_{ij} = (x_i-x_j) \mod k$. This is a joint discrete
alignment problem with important applications in computer vision, graph mining,
and spectroscopy imaging. Our main result is a polynomial time algorithm that
learns exactly with high probability the alignment (up to some unrecoverable
offset) using $O(n^{1+o(1)})$ queries.
