Seminar • Algorithms and Complexity • Sorting and Selection in Rounds with Adversarial Comparisons

Please note: This seminar will take place in DC 1304 and online.

Chris Trevisan, Undergraduate student
David R. Cheriton School of Computer Science

We continue the study of selection and sorting of n numbers under the adversarial comparator model, where comparisons can be adversarially tampered with if the arguments are sufficiently close. We derive a randomized sorting algorithm that does O(nlog2n) comparisons and gives a correct answer with high probability, addressing an open problem of Ajtai, Feldman, Hassadim, and Nelson [AFHN15]. Our algorithm also implies a selection algorithm that does O(nlogn) comparisons and gives a correct answer with high probability. Both of these results are a log factor away from the naive lower bound. [AFHN15] shows an Ω(n1+ε) lower bound for both sorting and selection in the deterministic case, so our results also prove a discrepancy between what is possible with deterministic and randomized algorithms in this setting.

We also consider both sorting and selection in rounds, exploring the tradeoff between accuracy, number of comparisons, and number of rounds. Using results from sorting networks, we give general algorithms for sorting in d rounds where the number of comparisons increases with d and the accuracy decreases with d. Using these algorithms, we derive selection algorithms in d+O(logd) rounds that use the same number of comparisons as the corresponding sorting algorithm, but have a constant accuracy. Notably, this gives selection algorithms in d rounds that use n1+o(1) comparisons and have constant accuracy for all d=ω(1), which still beats the deterministic lower bound of Ω(n1+ε).

The paper is available at https://arxiv.org/abs/2310.09483 and has appeared in SODA 2024.

To attend this seminar in person, please go to DC 1304. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/98174762256.

If you require the passcode for this seminar, please email Joe Petrik.