Parallel algorithms for select and partition with noisy comparisons

Mark Braverman; Jieming Mao; S. Matthew Weinberg

doi:10.1145/2897518.2897642

Parallel algorithms for select and partition with noisy comparisons

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider the problem of finding the k^th 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 language	English (US)
Title of host publication	STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
Editors	Yishay Mansour, Daniel Wichs
Publisher	Association for Computing Machinery
Pages	851-862
Number of pages	12
ISBN (Electronic)	9781450341325
DOIs	https://doi.org/10.1145/2897518.2897642
State	Published - Jun 19 2016
Event	48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States Duration: Jun 19 2016 → Jun 21 2016

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	19-21-June-2016
ISSN (Print)	0737-8017

Other

Other	48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
Country/Territory	United States
City	Cambridge
Period	6/19/16 → 6/21/16

All Science Journal Classification (ASJC) codes

Software

Keywords

Median finding
Noisy comparisons
Parallel algorithms
Rank aggregation
Top-k

Access to Document

10.1145/2897518.2897642

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

Braverman, Mark ; Mao, Jieming ; Weinberg, S. Matthew. / Parallel algorithms for select and partition with noisy comparisons. STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. editor / Yishay Mansour ; Daniel Wichs. Association for Computing Machinery, 2016. pp. 851-862 (Proceedings of the Annual ACM Symposium on Theory of Computing).

@inproceedings{b8f3df2db02944c3ada20821828f77da,

title = "Parallel algorithms for select and partition with noisy comparisons",

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.",

keywords = "Median finding, Noisy comparisons, Parallel algorithms, Rank aggregation, Top-k",

author = "Mark Braverman and Jieming Mao and Weinberg, \{S. Matthew\}",

note = "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.; 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 ; Conference date: 19-06-2016 Through 21-06-2016",

year = "2016",

month = jun,

day = "19",

doi = "10.1145/2897518.2897642",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "851--862",

editor = "Yishay Mansour and Daniel Wichs",

booktitle = "STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing",

}

Braverman, M, Mao, J & Weinberg, SM 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. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. 19-21-June-2016, Association for Computing Machinery, pp. 851-862, 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, United States, 6/19/16. https://doi.org/10.1145/2897518.2897642

Parallel algorithms for select and partition with noisy comparisons. / Braverman, Mark; Mao, Jieming; Weinberg, S. Matthew.
STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Yishay Mansour; Daniel Wichs. Association for Computing Machinery, 2016. p. 851-862 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 19-21-June-2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 - https://www.scopus.com/pages/publications/84979248409

UR - https://www.scopus.com/pages/publications/84979248409#tab=citedBy

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 -

Braverman M, Mao J, Weinberg SM. Parallel algorithms for select and partition with noisy comparisons. In Mansour Y, Wichs D, editors, STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2016. p. 851-862. (Proceedings of the Annual ACM Symposium on Theory of Computing). doi: 10.1145/2897518.2897642

Parallel algorithms for select and partition with noisy comparisons

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this