Maximum Selection and Sorting with Adversarial Comparators and an Application to Density Estimation

Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour +2

We study maximum selection and sorting of $n$ numbers using pairwise comparators that output the larger of their two inputs if the inputs are more than a given threshold apart, and…