In this work we consider the problem of recovering n discrete random variables xi∈{0,…,k−1},1≤i≤n (where k is constant) with the smallest possible number of queries to a noisy oracle that returns for a given query pair (xi,xj) a noisy measurement of their modulo k pairwise difference, i.e., yij=(xi−xj)modk. 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(n1+o(1)) queries.