{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T10:58:52Z","timestamp":1763809132890,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"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":[],"published-print":{"date-parts":[[2012,5,19]]},"DOI":"10.1145\/2213977.2214042","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"709-728","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Learning poisson binomial distributions"],"prefix":"10.1145","author":[{"given":"Constantinos","family":"Daskalakis","sequence":"first","affiliation":[{"name":"MIT, Boston, USA"}]},{"given":"Ilias","family":"Diakonikolas","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, USA"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1941-0003498-3"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198522355.001.0001","volume-title":"Poisson Approximation","author":"Barbour A.D.","year":"1992","unstructured":"A.D. Barbour , L. Holst , and S. Janson . Poisson Approximation . Oxford University Press , New York, NY , 1992 . A.D. Barbour, L. Holst, and S. Janson. Poisson Approximation. Oxford University Press, New York, NY, 1992."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176350488"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176350489"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1069362733"},{"key":"e_1_3_2_2_6_1","first-page":"19","article-title":"Translated poisson approximation for markov chains","author":"Barbour A. D.","year":"2006","unstructured":"A. D. Barbour and T. Lindvall . Translated poisson approximation for markov chains . Journal of Theoretical Probability , 19 , 2006 . A. D. Barbour and T. Lindvall. Translated poisson approximation for markov chains. Journal of Theoretical Probability, 19, 2006.","journal-title":"Journal of Theoretical Probability"},{"key":"e_1_3_2_2_7_1","first-page":"151","volume-title":"Multiple-precision zero-finding methods and the complexity of elementary function evaluation. Analytic Computational Complexity","author":"Brent R. P.","year":"1975","unstructured":"R. P. Brent . Multiple-precision zero-finding methods and the complexity of elementary function evaluation. Analytic Computational Complexity (J. F. Traub ed.), pages 151 -- 176 , 1975 . Academic Press , New York . R. P. Brent. Multiple-precision zero-finding methods and the complexity of elementary function evaluation. Analytic Computational Complexity (J. F. Traub ed.), pages 151--176, 1975. Academic Press, New York."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321944"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.16"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1960.10.1181"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996766"},{"key":"e_1_3_2_2_13_1","first-page":"875","article-title":"Statistical applications of the Poisson-Binomial and Conditional Bernoulli Distributions","volume":"7","author":"Chen S.X.","year":"1997","unstructured":"S.X. Chen and J.S. Liu . Statistical applications of the Poisson-Binomial and Conditional Bernoulli Distributions . Statistica Sinica , 7 : 875 -- 892 , 1997 . S.X. Chen and J.S. Liu. Statistical applications of the Poisson-Binomial and Conditional Bernoulli Distributions. Statistica Sinica, 7:875--892, 1997.","journal-title":"Statistica Sinica"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_26"},{"key":"e_1_3_2_2_15_1","volume-title":"Learning k-modal distributions via testing. To appear in SODA","author":"Daskalakis C.","year":"2012","unstructured":"C. Daskalakis , I. Diakonikolas , and R.A. Servedio . Learning k-modal distributions via testing. To appear in SODA , 2012 . C. Daskalakis, I. Diakonikolas, and R.A. Servedio. Learning k-modal distributions via testing. To appear in SODA, 2012."},{"key":"e_1_3_2_2_16_1","first-page":"2626","article-title":"Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes","volume":"25","author":"Devroye L.","year":"1996","unstructured":"L. Devroye and G. Lugosi . Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes . Annals of Statistics , 25 : 2626 -- 2637 , 1996 . L. Devroye and G. Lugosi. Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes. Annals of Statistics, 25:2626--2637, 1996.","journal-title":"Annals of Statistics"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1032181164"},{"key":"e_1_3_2_2_18_1","series-title":"Springer Series in Statistics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0125-7","volume-title":"Combinatorial methods in density estimation","author":"Devroye L.","year":"2001","unstructured":"L. Devroye and G. Lugosi . Combinatorial methods in density estimation . Springer Series in Statistics , Springer , 2001 . L. Devroye and G. Lugosi. Combinatorial methods in density estimation. Springer Series in Statistics, Springer, 2001."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176992536"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1568639"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536427"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-7152(91)90170-V"},{"key":"e_1_3_2_2_23_1","volume-title":"A:1--19","author":"Esseen Carl-Gustav","year":"1942","unstructured":"Carl-Gustav Esseen . On the liapunoff limit of error in the theory of probability. Arkiv f\u00f6r matematik, astronomi och fysik , A:1--19 , 1942 . Carl-Gustav Esseen. On the liapunoff limit of error in the theory of probability. Arkiv f\u00f6r matematik, astronomi och fysik, A:1--19, 1942."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90048-H"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177705799"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_2_2_27_1","volume-title":"Probability and Statistics for Computer Science","author":"Johnson J.L.","year":"2003","unstructured":"J.L. Johnson . Probability and Statistics for Computer Science . John Wiley & Sons, Inc. , New York, NY, USA , 2003 . J.L. Johnson. Probability and Statistics for Computer Science. John Wiley & Sons, Inc., New York, NY, USA, 2003."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1971.10482273"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195155"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806765"},{"key":"e_1_3_2_2_31_1","volume-title":"The Art of Computer Programming","author":"Knuth Donald E.","year":"1981","unstructured":"Donald E. Knuth . The Art of Computer Programming , Volume II : Seminumerical Algorithms, 2 nd Edition. Addison-Wesley , 1981 . Donald E. Knuth. The Art of Computer Programming, Volume II: Seminumerical Algorithms, 2nd Edition. Addison-Wesley, 1981.","edition":"2"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1138044"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.15"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"crossref","DOI":"10.1002\/0471715816","volume-title":"Univariate discrete distributions","author":"Johnson S. Kotz N.L.","year":"2005","unstructured":"S. Kotz N.L. Johnson , A.W. Kemp . Univariate discrete distributions . John Wiley & Sons, Inc. , New York, NY, USA , 2005 . S. Kotz N.L. Johnson, A.W. Kemp. Univariate discrete distributions. John Wiley & Sons, Inc., New York, NY, USA, 2005."},{"key":"e_1_3_2_2_35_1","volume-title":"Bachelier","author":"Poisson S.D.","year":"1837","unstructured":"S.D. Poisson . Recherches sur la Probabilit\u00e8 des jugements en mati\u00e9 criminelle et en mati\u00e9re civile . Bachelier , Paris , 1837 . S.D. Poisson. Recherches sur la Probabilit\u00e8 des jugements en mati\u00e9 criminelle et en mati\u00e9re civile. Bachelier, Paris, 1837."},{"key":"e_1_3_2_2_36_1","volume-title":"Personal communication","author":"Peres Y.","year":"2011","unstructured":"Y. Peres and S. Watson . Personal communication , 2011 . Y. Peres and S. Watson. Personal communication, 2011."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051607000000258"},{"key":"e_1_3_2_2_38_1","first-page":"328","article-title":"Binomial approximation to the Poisson binomial distribution: The Krawtchouk expansion","volume":"45","author":"Roos B.","year":"2000","unstructured":"B. Roos . Binomial approximation to the Poisson binomial distribution: The Krawtchouk expansion . Theory Probab. Appl. , 45 : 328 -- 344 , 2000 . B. Roos. Binomial approximation to the Poisson binomial distribution: The Krawtchouk expansion. Theory Probab. Appl., 45:328--344, 2000.","journal-title":"Theory Probab. Appl."},{"issue":"135","key":"e_1_3_2_2_39_1","first-page":"565","article-title":"Computation of pi using arithmetic-geometric mean","volume":"30","author":"Salamin Eugene","year":"1976","unstructured":"Eugene Salamin . Computation of pi using arithmetic-geometric mean . Mathematics of Computation , 30 ( 135 ): 565 -- 570 , 1976 . Eugene Salamin. Computation of pi using arithmetic-geometric mean. Mathematics of Computation, 30(135):565--570, 1976.","journal-title":"Mathematics of Computation"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989129"},{"key":"e_1_3_2_2_41_1","first-page":"703","article-title":"Binomial approximation for dependent indicators","volume":"6","author":"Soon S.Y.T.","year":"1996","unstructured":"S.Y.T. Soon . Binomial approximation for dependent indicators . Statist. Sinica , 6 : 703 -- 714 , 1996 . S.Y.T. Soon. Binomial approximation for dependent indicators. Statist. Sinica, 6:703--714, 1996.","journal-title":"Statist. Sinica"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242355"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1994.11996904"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1140093"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993727"},{"key":"e_1_3_2_2_46_1","first-page":"295","article-title":"On the number of successes in independent trials","volume":"3","author":"Wang Y.H.","year":"1993","unstructured":"Y.H. Wang . On the number of successes in independent trials . Statistica Sinica , 3 : 295 -- 312 , 1993 . Y.H. Wang. On the number of successes in independent trials. Statistica Sinica, 3:295--312, 1993.","journal-title":"Statistica Sinica"},{"key":"e_1_3_2_2_47_1","volume-title":"A course of modern analysis","author":"Whittaker E.T.","year":"1980","unstructured":"E.T. Whittaker . A course of modern analysis . Cambridge University Press , 1980 . E.T. Whittaker. A course of modern analysis. Cambridge University Press, 1980."},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349553"}],"event":{"name":"STOC'12: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"New York New York USA","acronym":"STOC'12"},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214042","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2214042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:54Z","timestamp":1750238454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":48,"alternative-id":["10.1145\/2213977.2214042","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2214042","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}