Parallel algorithms for select and partition with noisy comparisons

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

Abstract

We consider the problem of finding the kth highest element in a totally ordered set of n elements (SELECT), and partitioning a totally ordered set into the top k and bottom n - k elements (PARTITION) using pairwise comparisons. Motivated by settings like peer grading or crowdsourcing, where multiple rounds of interaction are costly and queried comparisons may be inconsistent with the ground truth, we evaluate algorithms based both on their total runtime and the number of interactive rounds in three comparison models: noiseless (where the comparisons are correct), erasure (where comparisons are erased with probability 1 - γ), and noisy (where comparisons are correct with probability 1/2 + γ/2 and incorrect otherwise). We provide numerous matching upper and lower bounds in all three models. Even our results in the noiseless model, which is quite well-studied in the TCS literature on parallel algorithms, are novel.

Original languageEnglish (US)
Title of host publicationSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
EditorsYishay Mansour, Daniel Wichs
PublisherAssociation for Computing Machinery
Pages851-862
Number of pages12
ISBN (Electronic)9781450341325
DOIs
StatePublished - Jun 19 2016
Event48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States
Duration: Jun 19 2016Jun 21 2016

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume19-21-June-2016
ISSN (Print)0737-8017

Other

Other48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
CountryUnited States
CityCambridge
Period6/19/166/21/16

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Median finding
  • Noisy comparisons
  • Parallel algorithms
  • Rank aggregation
  • Top-k

Fingerprint Dive into the research topics of 'Parallel algorithms for select and partition with noisy comparisons'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Mao, J., & Weinberg, S. M. (2016). Parallel algorithms for select and partition with noisy comparisons. In Y. Mansour, & D. Wichs (Eds.), STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (pp. 851-862). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 19-21-June-2016). Association for Computing Machinery. https://doi.org/10.1145/2897518.2897642