{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T20:12:52Z","timestamp":1770754372762,"version":"3.50.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,9,28]],"date-time":"2021-09-28T00:00:00Z","timestamp":1632787200000},"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. Math. Softw."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>We present ShiftConvolvePoibin, a fast exact method to compute the tail of a Poisson-binomial distribution (PBD). Our method employs an exponential shift to retain its accuracy when computing a tail probability, and in practice we find that it is immune to the significant relative errors that other methods, exact or approximate, can suffer from when computing very small tail probabilities of the PBD. The accompanying R package is also competitive with the fastest implementations for computing the entire PBD.<\/jats:p>","DOI":"10.1145\/3460774","type":"journal-article","created":{"date-parts":[[2021,9,28]],"date-time":"2021-09-28T20:47:05Z","timestamp":1632862025000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Exactly Computing the Tail of the Poisson-Binomial Distribution"],"prefix":"10.1145","volume":"47","author":[{"given":"Noah","family":"Peres","sequence":"first","affiliation":[{"name":"University of Sydney, Sydney, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew Ray","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Sydney, Sydney, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3209-5011","authenticated-orcid":false,"given":"Uri","family":"Keich","sequence":"additional","affiliation":[{"name":"University of Sydney, Sydney, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,9,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2018.01.007"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368619"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840301"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2012.10.006"},{"key":"e_1_2_1_6_1","volume-title":"sFFT: A faster accurate computation of the -value of the entropy score.Journal of Computational Biology 12, 4 (May","author":"Keich Uri","year":"2005","unstructured":"Uri Keich . 2005. sFFT: A faster accurate computation of the -value of the entropy score.Journal of Computational Biology 12, 4 (May 2005 ), 416\u201330. DOI:https:\/\/doi.org\/10.1089\/cmb.2005.12.416 10.1089\/cmb.2005.12.416 Uri Keich. 2005. sFFT: A faster accurate computation of the -value of the entropy score.Journal of Computational Biology 12, 4 (May 2005), 416\u201330. DOI:https:\/\/doi.org\/10.1089\/cmb.2005.12.416"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1198\/106186006X159377"},{"key":"e_1_2_1_8_1","volume-title":"Jens Ledet Jensen, and Jakob Skou Pedersen","author":"Madsen Tobias","year":"2017","unstructured":"Tobias Madsen , Asger Hobolth , Jens Ledet Jensen, and Jakob Skou Pedersen . 2017 . Significance evaluation in factor graphs.BMC Bioinformatics 18, 1 (March 2017), 199. DOI:https:\/\/doi.org\/10.1186\/s12859-017-1614-z 10.1186\/s12859-017-1614-z Tobias Madsen, Asger Hobolth, Jens Ledet Jensen, and Jakob Skou Pedersen. 2017. Significance evaluation in factor graphs.BMC Bioinformatics 18, 1 (March 2017), 199. DOI:https:\/\/doi.org\/10.1186\/s12859-017-1614-z"},{"key":"e_1_2_1_9_1","unstructured":"Alexander Mukhin. 2019. minFFT: A Minimalist Fast Fourier Transform Library. Retrieved from https:\/\/github.com\/aimukhin\/minfft?files=1  Alexander Mukhin. 2019. minFFT: A Minimalist Fast Fourier Transform Library. Retrieved from https:\/\/github.com\/aimukhin\/minfft?files=1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00180-009-0148-x"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827593247023"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1464182.1464209"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2016.03.010"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2016.1276841"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/00949655.2018.1440294"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460774","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460774","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:28Z","timestamp":1750195468000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460774"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,28]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3460774"],"URL":"https:\/\/doi.org\/10.1145\/3460774","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,28]]},"assertion":[{"value":"2020-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}