{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T00:25:53Z","timestamp":1768523153068,"version":"3.49.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,1,16]],"date-time":"2018-01-16T00:00:00Z","timestamp":1516060800000},"content-version":"vor","delay-in-days":567,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1228598"],"award-info":[{"award-number":["CNS-1228598"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2016,6,28]]},"abstract":"<jats:p>\n                    The analysis of several algorithms and data structures can be framed as a\n                    <jats:italic toggle=\"yes\">peeling process<\/jats:italic>\n                    on a random hypergraph: vertices with degree less than\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    are removed until there are no vertices of degree less than\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    left. The remaining hypergraph is known as the\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -core. In this article, we analyze parallel peeling processes, in which in each round, all vertices of degree less than\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    are removed. It is known that, below a specific edge-density threshold, the\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -core is empty with high probability. We show that, with high probability, below this threshold, only 1\/log((\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -1)(\n                    <jats:italic toggle=\"yes\">r<\/jats:italic>\n                    -1)) log log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    +\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (1) rounds of peeling are needed to obtain the empty\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -core for\n                    <jats:italic toggle=\"yes\">r<\/jats:italic>\n                    -uniform hypergraphs. This bound is tight up to an additive constant. Interestingly, we show that, above this threshold, \u03a9(log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) rounds of peeling are required to find the nonempty\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -core. Since most algorithms and data structures aim to peel to an empty\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -core, this asymmetry appears fortunate. We verify the theoretical results both with simulation and with a parallel implementation using graphics processing units (GPUs). Our implementation provides insights into how to structure parallel peeling algorithms for efficiency in practice.\n                  <\/jats:p>","DOI":"10.1145\/2938412","type":"journal-article","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T09:26:34Z","timestamp":1470302794000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Parallel Peeling Algorithms"],"prefix":"10.1145","volume":"3","author":[{"given":"Jiayang","family":"Jiang","sequence":"first","affiliation":[{"name":"Harvard University, School of Engineering and Applied Sciences, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[{"name":"Harvard University, School of Engineering and Applied Sciences, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Thaler","sequence":"additional","affiliation":[{"name":"Harvard University, School of Engineering and Applied Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,1,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20494"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313794"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/982792.982797"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129115"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20040"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_19"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2018436.2018462"},{"key":"e_1_2_1_9_1","unstructured":"Pu Gao. 2014. Analysis of the parallel peeling algorithm: a short proof. http:\/\/arxiv.org\/abs\/1402.7326."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2011.6120248"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Richard M. Karp Michael Luby and Friedhelm Meyer auf der Heide. 1996. Efficient PRAM simulation on a distributed memory machine. Algorithmica 16 4\/5 517--542. DOI:http:\/\/dx.doi.org\/10.1007\/BF01940878","DOI":"10.1007\/BF01940878"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/080728743"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1960.10.1181"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.910575"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.963420"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1076315"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2012.6284236"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 37th Annual Allerton Conference on Communication Control and Computing. 326--327","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and B. V\u00f6cking. 1999. The asymptotics of selecting the shortest of two, improved. In Proceedings of the 37th Annual Allerton Conference on Communication Control and Computing. 326--327."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20061"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792546"},{"key":"e_1_2_1_22_1","unstructured":"U. Voll. 2001. Threshold Phenomena in Branching Trees and Sparse Random Graphs. Ph.D. Dissertation. Techischen Universit\u00e4t M\u00fcnchen Munich Germany."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2938412","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2938412","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2938412","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:26:19Z","timestamp":1763457979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2938412"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,28]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,6,28]]}},"alternative-id":["10.1145\/2938412"],"URL":"https:\/\/doi.org\/10.1145\/2938412","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,28]]},"assertion":[{"value":"2014-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}