TY - GEN
T1 - Parallel algorithms for select and partition with noisy comparisons
AU - Braverman, Mark
AU - Mao, Jieming
AU - Weinberg, S. Matthew
N1 - Funding Information:
Research supported in part by an NSF CAREER award (CCF-1149888), NSF CCF-1215990, NSF CCF-1525342, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. Research completed in part while the author was a Microsoft Research Fellow at the Simons Institute for the Theory of Computing.
PY - 2016/6/19
Y1 - 2016/6/19
N2 - 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.
AB - 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.
KW - Median finding
KW - Noisy comparisons
KW - Parallel algorithms
KW - Rank aggregation
KW - Top-k
UR - http://www.scopus.com/inward/record.url?scp=84979248409&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84979248409&partnerID=8YFLogxK
U2 - 10.1145/2897518.2897642
DO - 10.1145/2897518.2897642
M3 - Conference contribution
AN - SCOPUS:84979248409
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 851
EP - 862
BT - STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Mansour, Yishay
A2 - Wichs, Daniel
PB - Association for Computing Machinery
T2 - 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
Y2 - 19 June 2016 through 21 June 2016
ER -