Sorted Top-k in Rounds
  We consider the sorted top-$k$ problem whose goal is to recover the top-$k$
items with the correct order out of $n$ items using pairwise comparisons. In
many applications, multiple rounds of interaction can be costly. We restrict
our attention to algorithms with a constant number of rounds $r$ and try to
minimize the sample complexity, i.e. the number of comparisons.
  When the comparisons are noiseless, we characterize how the optimal sample
complexity depends on the number of rounds (up to a polylogarithmic factor for
general $r$ and up to a constant factor for $r=1$ or 2). In particular, the
sample complexity is $\Theta(n^2)$ for $r=1$, $\Theta(n\sqrt{k} + n^{4/3})$ for
$r=2$ and $\tilde{\Theta}\left(n^{2/r} k^{(r-1)/r} + n\right)$ for $r \geq 3$.
  We extend our results of sorted top-$k$ to the noisy case where each
comparison is correct with probability $2/3$. When $r=1$ or 2, we show that the
sample complexity gets an extra $\Theta(\log(k))$ factor when we transition
from the noiseless case to the noisy case.
  We also prove new results for top-$k$ and sorting in the noisy case. We
believe our techniques can be generally useful for understanding the trade-off
between round complexities and sample complexities of rank aggregation
problems.
