{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:07Z","timestamp":1750221007742,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>\n            A parallel algorithm for maximal independent set (MIS) in hypergraphs has been a long-standing algorithmic challenge, dating back nearly 30 years to a survey of Karp and Ramachandran (1990). The best randomized parallel algorithm for hypergraphs of fixed rank\n            <jats:italic>r<\/jats:italic>\n            was developed by Beame and Luby (1990) and Kelsen (1992), running in time roughly (log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>r<\/jats:italic>\n              <jats:sup>!<\/jats:sup>\n            <\/jats:sup>\n            .\n          <\/jats:p>\n          <jats:p>\n            We improve the randomized algorithm of Kelsen, reducing the runtime to roughly (log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>\n              2\n              <jats:sup>\n                <jats:italic>r<\/jats:italic>\n              <\/jats:sup>\n            <\/jats:sup>\n            and simplifying the analysis through the use of more-modern concentration inequalities. We also give a method for derandomizing concentration bounds for low-degree polynomials, which are the key technical tool used to analyze that algorithm. This leads to a deterministic PRAM algorithm also running in (log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>\n              2\n              <jats:sup>\n                <jats:italic>r<\/jats:italic>\n                +3\n              <\/jats:sup>\n            <\/jats:sup>\n            time and\n            <jats:italic>poly<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            ,\n            <jats:italic>n<\/jats:italic>\n            ) processors. This is the first deterministic algorithm with sub-polynomial runtime for hypergraphs of rank\n            <jats:italic>r<\/jats:italic>\n            &gt; 3.\n          <\/jats:p>\n          <jats:p>\n            Our analysis can also apply when\n            <jats:italic>r<\/jats:italic>\n            is slowly growing; using this in conjunction with a strategy of Bercea et al. (2015) gives a deterministic MIS algorithm running in time exp (\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>log<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            ) \/ log log (\n            <jats:italic>mn<\/jats:italic>\n            )).\n          <\/jats:p>","DOI":"10.1145\/3326171","type":"journal-article","created":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T12:39:01Z","timestamp":1563280741000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set"],"prefix":"10.1145","volume":"15","author":[{"given":"David G.","family":"Harris","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523683"},{"volume-title":"Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA\u201990)","author":"Beame P.","key":"e_1_2_1_2_1","unstructured":"P. Beame and M. Luby . 1990. Parallel search for maximal independence given minimal dependence . In Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA\u201990) . 212--218. P. Beame and M. Luby. 1990. Parallel search for maximal independence given minimal dependence. In Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA\u201990). 212--218."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2938436"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90228-N"},{"volume-title":"Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Fischer M.","key":"e_1_2_1_6_1","unstructured":"M. Fischer and A. Noever . 2018. Tight analysis of randomized greedy MIS . In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918) . 2152--2160. M. Fischer and A. Noever. 2018. Tight analysis of randomized greedy MIS. In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918). 2152--2160."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00040-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"R. Karp and V. Ramachandran. 1990. A survey of parallel algorithms for shared-memory machines. Handook of Theoretical Computer Science Volume A (1990). MIT Press Cambridge MA 869--941.   R. Karp and V. Ramachandran. 1990. A survey of parallel algorithms for shared-memory machines. Handook of Theoretical Computer Science Volume A (1990). MIT Press Cambridge MA 869--941.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"R. Karp E. Upfal and A. Wigderson. 1988. The complexity of parallel search. J. Comput. Syst. Sci. 36--2 (1988) 225--253.   R. Karp E. Upfal and A. Wigderson. 1988. The complexity of parallel search. J. Comput. Syst. Sci. 36--2 (1988) 225--253.","DOI":"10.1016\/0022-0000(88)90027-X"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129745"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"J. Kim and V. Vu. 2000. Concentration of multivariate polynomials and its applications. Combinatorica 20--3 (2000) 417--434.  J. Kim and V. Vu. 2000. Concentration of multivariate polynomials and its applications. Combinatorica 20--3 (2000) 417--434.","DOI":"10.1007\/s004930070014"},{"volume-title":"Proceedings of International Symposium on Distributed Computing (DISC'14)","author":"Kutten S.","key":"e_1_2_1_12_1","unstructured":"S. Kutten , D. Nanongkai , G. Pandurangan , and P. Robinson . 2014. Distributed symmetry breaking in hypergraphs . In Proceedings of International Symposium on Distributed Computing (DISC'14) . 469--483. S. Kutten, D. Nanongkai, G. Pandurangan, and P. Robinson. 2014. Distributed symmetry breaking in hypergraphs. In Proceedings of International Symposium on Distributed Computing (DISC'14). 469--483."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0884"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"volume-title":"Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912)","author":"Schudy W.","key":"e_1_2_1_16_1","unstructured":"W. Schudy and M. Sviridenko . 2012. Concentration and moment inequalities for polynomials of independent random variables . In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912) . 437--446. W. Schudy and M. Sviridenko. 2012. Concentration and moment inequalities for polynomials of independent random variables. In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912). 437--446."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509996"},{"key":"e_1_2_1_18_1","unstructured":"T. Syoudai and S. Miyano. 1993. An NC algorithm for computing a maximal independent set in a hypergraph of bounded valence. RIFIS Technical report 68 (1993) 1--7. Research Institute of Fundamental Information Science (RIFIS) Kyushu University.  T. Syoudai and S. Miyano. 1993. An NC algorithm for computing a maximal independent set in a hypergraph of bounded valence. RIFIS Technical report 68 (1993) 1--7. Research Institute of Fundamental Information Science (RIFIS) Kyushu University."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"V. Vu. 2000. On the concentration of multivariate polynomials with small expectation. Rand. Struct. 8 Alg. 16--4 (2000) 344--363.   V. Vu. 2000. On the concentration of multivariate polynomials with small expectation. Rand. Struct. 8 Alg. 16--4 (2000) 344--363.","DOI":"10.1002\/1098-2418(200007)16:4<344::AID-RSA4>3.0.CO;2-5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10032"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326171","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3326171","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:58Z","timestamp":1750206358000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326171"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3326171"],"URL":"https:\/\/doi.org\/10.1145\/3326171","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2019,7,16]]},"assertion":[{"value":"2017-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}