Sorting and Selection in Rounds with Adversarial Comparisons

被引:0
作者
Trevisan, Christopher [1 ]
机构
[1] Univ Waterloo, Waterloo, ON, Canada
来源
PROCEEDINGS OF THE 2024 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA | 2024年
关键词
PARALLEL; COMPLEXITY; NETWORKS;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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(n log(2) n) 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(n log n) 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 Omega(n(1+epsilon)) 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(log d) 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 n(1+o(1)) comparisons and have constant accuracy for all d = omega(1), which still beats the deterministic lower bound of Omega(n(1+epsilon)).
引用
收藏
页码:1099 / 1119
页数:21
相关论文
共 59 条
  • [1] Acharya J, 2018, J MACH LEARN RES, V19
  • [2] Agarwal Arpit, 2017, C LEARNING THEORY, P39
  • [3] Ajtai M., 1983, S THEORY COMPUTING S, P1, DOI [10.1145/800061.808726, DOI 10.1145/800061.808726]
  • [4] Sorting and Selection with Imprecise Comparisons
    Ajtai, Miklos
    Feldman, Vitaly
    Hassidim, Avinatan
    Nelson, Jelani
    [J]. ACM TRANSACTIONS ON ALGORITHMS, 2016, 12 (02)
  • [5] THE AVERAGE COMPLEXITY OF DETERMINISTIC AND RANDOMIZED PARALLEL COMPARISON-SORTING ALGORITHMS
    ALON, N
    AZAR, Y
    [J]. SIAM JOURNAL ON COMPUTING, 1988, 17 (06) : 1178 - 1192
  • [6] Alon N., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P502, DOI 10.1109/SFCS.1986.57
  • [7] EIGENVALUES, GEOMETRIC EXPANDERS, SORTING IN ROUNDS, AND RAMSEY THEORY
    ALON, N
    [J]. COMBINATORICA, 1986, 6 (03) : 207 - 219
  • [8] [Anonymous], 1988, SIAM Journal on Discrete Mathematics
  • [9] Assaf S., 1990, Proceedings. 31st Annual Symposium on Foundations of Computer Science (Cat. No.90CH2925-6), P275, DOI 10.1109/FSCS.1990.89546
  • [10] TIGHT COMPARISON BOUNDS ON THE COMPLEXITY OF PARALLEL SORTING
    AZAR, Y
    VISHKIN, U
    [J]. SIAM JOURNAL ON COMPUTING, 1987, 16 (03) : 458 - 464