{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T18:13:49Z","timestamp":1759515229606,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"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":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316398","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"780-791","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Efficient profile maximum likelihood for universal symmetric property estimation"],"prefix":"10.1145","author":[{"given":"Moses","family":"Charikar","sequence":"first","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Kirankumar","family":"Shiragur","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2018.8437461"},{"volume-title":"2010 IEEE International Symposium on Information Theory. 1498\u20131502","author":"Acharya J.","key":"e_1_3_2_1_2_1","unstructured":"J. Acharya , H. Das , H. Mohimani , A. Orlitsky , and S. Pan . 2010. Exact calculation of pattern probabilities . In 2010 IEEE International Symposium on Information Theory. 1498\u20131502 . J. Acharya, H. Das, H. Mohimani, A. Orlitsky, and S. Pan. 2010. Exact calculation of pattern probabilities. In 2010 IEEE International Symposium on Information Theory. 1498\u20131502."},{"key":"e_1_3_2_1_3_1","unstructured":"Jayadev Acharya Hirakendu Das Alon Orlitsky and Ananda Theertha Suresh. 2016.  Jayadev Acharya Hirakendu Das Alon Orlitsky and Ananda Theertha Suresh. 2016."},{"key":"e_1_3_2_1_4_1","volume-title":"CoRR abs\/1611.02960","author":"Likelihood A Unified Maximum","year":"2016","unstructured":"A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation . CoRR abs\/1611.02960 ( 2016 ). arXiv: 1611.02960 http: \/\/arxiv.org\/abs\/1611.02960 A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation. CoRR abs\/1611.02960 (2016). arXiv: 1611.02960 http: \/\/arxiv.org\/abs\/1611.02960"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms.","author":"Acharya Jayadev","year":"2014","unstructured":"Jayadev Acharya , Alon Orlitsky , Ananda Theertha Suresh , and Himanshu Tyagi . 2014 . The Complexity of Estimating R\u00e9nyi Entropy . In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. 2014. The Complexity of Estimating R\u00e9nyi Entropy. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_3_2_1_6_1","unstructured":"D. P. Bhatia M. A. Prasad and D. Arora. 1997.  D. P. Bhatia M. A. Prasad and D. Arora. 1997."},{"key":"e_1_3_2_1_7_1","volume-title":"Journal of Physics A Mathematical General 30 (April","author":"Asymptotic","year":"1997","unstructured":"Asymptotic results for the number of multidimensional partitions of an integer and directed compact lattice animals. Journal of Physics A Mathematical General 30 (April 1997 ), 2281\u20132285. Asymptotic results for the number of multidimensional partitions of an integer and directed compact lattice animals. Journal of Physics A Mathematical General 30 (April 1997), 2281\u20132285."},{"volume-title":"2016 IEEE International Symposium on Information Theory (ISIT). 1118\u20131122","author":"Bu Y.","key":"e_1_3_2_1_8_1","unstructured":"Y. Bu , S. Zou , Y. Liang , and V. V. Veeravalli . 2016. Estimation of KL divergence between large-alphabet distributions . In 2016 IEEE International Symposium on Information Theory (ISIT). 1118\u20131122 . Y. Bu, S. Zou, Y. Liang, and V. V. Veeravalli. 2016. Estimation of KL divergence between large-alphabet distributions. In 2016 IEEE International Symposium on Information Theory (ISIT). 1118\u20131122."},{"key":"e_1_3_2_1_10_1","unstructured":"https:\/\/pqdtopen.proquest.com\/ doc\/1009080587.html?FMT=ABS.  https:\/\/pqdtopen.proquest.com\/ doc\/1009080587.html?FMT=ABS."},{"key":"e_1_3_2_1_11_1","first-page":"435","article-title":"Estimating the Number of Unsen Species: How Many Words Did Shakespeare Know","volume":"63","author":"Efron Bradley","year":"1976","unstructured":"Bradley Efron and Ronald Thisted . 1976 . Estimating the Number of Unsen Species: How Many Words Did Shakespeare Know ? Biometrika 63 , 3 (1976), 435 \u2013 447 . http:\/\/www.jstor.org\/stable\/2335721 Bradley Efron and Ronald Thisted. 1976. Estimating the Number of Unsen Species: How Many Words Did Shakespeare Know? Biometrika 63, 3 (1976), 435\u2013447. http:\/\/www.jstor.org\/stable\/2335721","journal-title":"Biometrika"},{"key":"e_1_3_2_1_12_1","volume-title":"Article arXiv:1710.03863 (Oct","author":"Han Yanjun","year":"2017","unstructured":"Yanjun Han , Jiantao Jiao , and Rajarshi Mukherjee . 2017. On Estimation of $L_{r}$-Norms in Gaussian White Noise Models. arXiv e-prints , Article arXiv:1710.03863 (Oct 2017 ), arXiv:1710.03863 pages. arXiv: math.ST\/1710.03863 Yanjun Han, Jiantao Jiao, and Rajarshi Mukherjee. 2017. On Estimation of $L_{r}$-Norms in Gaussian White Noise Models. arXiv e-prints, Article arXiv:1710.03863 (Oct 2017), arXiv:1710.03863 pages. arXiv: math.ST\/1710.03863"},{"key":"e_1_3_2_1_13_1","unstructured":"Yanjun Han Jiantao Jiao and Tsachy Weissman. 2016.  Yanjun Han Jiantao Jiao and Tsachy Weissman. 2016."},{"key":"e_1_3_2_1_14_1","volume-title":"CoRR abs\/1605.09124","author":"Discrete Distributions Minimax Estimation","year":"2016","unstructured":"Minimax Estimation of KL Divergence between Discrete Distributions . CoRR abs\/1605.09124 ( 2016 ). Minimax Estimation of KL Divergence between Discrete Distributions. CoRR abs\/1605.09124 (2016)."},{"key":"e_1_3_2_1_15_1","unstructured":"arXiv: 1605.09124 http:\/\/arxiv.org\/abs\/1605.09124  arXiv: 1605.09124 http:\/\/arxiv.org\/abs\/1605.09124"},{"key":"e_1_3_2_1_16_1","volume-title":"Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance. arXiv preprint arXiv:1802.08405","author":"Han Yanjun","year":"2018","unstructured":"Yanjun Han , Jiantao Jiao , and Tsachy Weissman . 2018. Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance. arXiv preprint arXiv:1802.08405 ( 2018 ). Yanjun Han, Jiantao Jiao, and Tsachy Weissman. 2018. Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance. arXiv preprint arXiv:1802.08405 (2018)."},{"key":"e_1_3_2_1_17_1","volume-title":"Article arXiv:1711.02141 (Nov","author":"Han Yanjun","year":"2017","unstructured":"Yanjun Han , Jiantao Jiao , Tsachy Weissman , and Yihong Wu. 2017. Optimal rates of entropy estimation over Lipschitz balls. arXiv e-prints , Article arXiv:1711.02141 (Nov 2017 ), arXiv:1711.02141 pages. arXiv: math.ST\/1711.02141 Yanjun Han, Jiantao Jiao, Tsachy Weissman, and Yihong Wu. 2017. Optimal rates of entropy estimation over Lipschitz balls. arXiv e-prints, Article arXiv:1711.02141 (Nov 2017), arXiv:1711.02141 pages. arXiv: math.ST\/1711.02141"},{"key":"e_1_3_2_1_18_1","unstructured":"G. H. Hardy and S. Ramanujan. 1918.  G. H. Hardy and S. Ramanujan. 1918."},{"key":"e_1_3_2_1_19_1","volume-title":"Formula\u00e6 in Combinatory Analysis. Proceedings of the London Mathematical Society s2-17","author":"Asymptotic","year":"1918","unstructured":"Asymptotic Formula\u00e6 in Combinatory Analysis. Proceedings of the London Mathematical Society s2-17 , 1 ( 1918 ), 75\u2013115. 17.1.75 Asymptotic Formula\u00e6 in Combinatory Analysis. Proceedings of the London Mathematical Society s2-17, 1 (1918), 75\u2013115. 17.1.75"},{"volume-title":"2016 IEEE International Symposium on Information Theory (ISIT). 750\u2013754","author":"Jiao J.","key":"e_1_3_2_1_20_1","unstructured":"J. Jiao , Y. Han , and T. Weissman . 2016. Minimax estimation of the L1 distance . In 2016 IEEE International Symposium on Information Theory (ISIT). 750\u2013754 . J. Jiao, Y. Han, and T. Weissman. 2016. Minimax estimation of the L1 distance. In 2016 IEEE International Symposium on Information Theory (ISIT). 750\u2013754."},{"key":"e_1_3_2_1_21_1","first-page":"5","article-title":"Minimax Estimation of Functionals of Discrete Distributions","volume":"61","author":"Jiao J.","year":"2015","unstructured":"J. Jiao , K. Venkat , Y. Han , and T. Weissman . 2015 . Minimax Estimation of Functionals of Discrete Distributions . IEEE Transactions on Information Theory 61 , 5 (May 2015), 2835\u20132885. J. Jiao, K. Venkat, Y. Han, and T. Weissman. 2015. Minimax Estimation of Functionals of Discrete Distributions. IEEE Transactions on Information Theory 61, 5 (May 2015), 2835\u20132885.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_2_1_22_1","unstructured":"Yin Tat Lee Aaron Sidford and Sam Chiu-wai Wong. 2015.  Yin Tat Lee Aaron Sidford and Sam Chiu-wai Wong. 2015."},{"key":"e_1_3_2_1_23_1","volume-title":"CoRR abs\/1508.04874","author":"Plane Method A Faster Cutting","year":"2015","unstructured":"A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization . CoRR abs\/1508.04874 ( 2015 ). arXiv: 1508.04874 http:\/\/arxiv.org\/abs\/1508.04874 A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization. CoRR abs\/1508.04874 (2015). arXiv: 1508.04874 http:\/\/arxiv.org\/abs\/1508.04874"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2004.1365341"},{"key":"e_1_3_2_1_25_1","volume-title":"On Modeling Profiles instead of Values. CoRR abs\/1207.4175","author":"Orlitsky Alon","year":"2012","unstructured":"Alon Orlitsky , Narayana P. Santhanam , Krishnamurthy Viswanathan , and Junan Zhang . 2012. On Modeling Profiles instead of Values. CoRR abs\/1207.4175 ( 2012 ). Alon Orlitsky, Narayana P. Santhanam, Krishnamurthy Viswanathan, and Junan Zhang. 2012. On Modeling Profiles instead of Values. CoRR abs\/1207.4175 (2012)."},{"key":"e_1_3_2_1_26_1","unstructured":"arXiv: 1207.4175 http:\/\/arxiv.org\/abs\/1207.4175  arXiv: 1207.4175 http:\/\/arxiv.org\/abs\/1207.4175"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1607774113"},{"key":"e_1_3_2_1_28_1","unstructured":"arXiv: http:\/\/www.pnas.org\/content\/113\/47\/13283.full.pdf  arXiv: http:\/\/www.pnas.org\/content\/113\/47\/13283.full.pdf"},{"key":"e_1_3_2_1_29_1","volume-title":"Estimating the unseen from multiple populations. CoRR abs\/1707.03854","author":"Raghunathan Aditi","year":"2017","unstructured":"Aditi Raghunathan , Gregory Valiant , and James Zou . 2017. Estimating the unseen from multiple populations. CoRR abs\/1707.03854 ( 2017 ). arXiv: 1707.03854 http: \/\/arxiv.org\/abs\/1707.03854 Aditi Raghunathan, Gregory Valiant, and James Zou. 2017. Estimating the unseen from multiple populations. CoRR abs\/1707.03854 (2017). arXiv: 1707.03854 http: \/\/arxiv.org\/abs\/1707.03854"},{"volume-title":"Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201907)","author":"Raskhodnikova S.","key":"e_1_3_2_1_30_1","unstructured":"S. Raskhodnikova , D. Ron , A. Shpilka , and A. Smith . 2007 . Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201907) . 559\u2013569. S. Raskhodnikova, D. Ron, A. Shpilka, and A. Smith. 2007. Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201907). 559\u2013569."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993727"},{"key":"e_1_3_2_1_32_1","unstructured":"1993727  1993727"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.81"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2012.6283654"},{"key":"e_1_3_2_1_35_1","unstructured":"P. O. Vontobel. 2014.  P. O. Vontobel. 2014."},{"volume-title":"2014 Information Theory and Applications Workshop (ITA). 1\u201310","author":"Bethe The","key":"e_1_3_2_1_36_1","unstructured":"The Bethe and Sinkhorn approximations of the pattern maximum likelihood estimate and their connections to the Valiant-Valiant estimate . In 2014 Information Theory and Applications Workshop (ITA). 1\u201310 . The Bethe and Sinkhorn approximations of the pattern maximum likelihood estimate and their connections to the Valiant-Valiant estimate. In 2014 Information Theory and Applications Workshop (ITA). 1\u201310."},{"key":"e_1_3_2_1_37_1","unstructured":"Y. Wu and P. Yang. 2015. Chebyshev polynomials moment matching and optimal estimation of the unseen. ArXiv e-prints (April 2015). arXiv: math.ST\/1504.01227  Y. Wu and P. Yang. 2015. Chebyshev polynomials moment matching and optimal estimation of the unseen. ArXiv e-prints (April 2015). arXiv: math.ST\/1504.01227"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2548468"},{"key":"e_1_3_2_1_39_1","unstructured":"Yihong Wu and Pengkun Yang. 2016.  Yihong Wu and Pengkun Yang. 2016."},{"key":"e_1_3_2_1_40_1","volume-title":"Article arXiv:1612.03375 (Dec","author":"Sample","year":"2016","unstructured":"Sample complexity of the distinct elements problem. arXiv e-prints , Article arXiv:1612.03375 (Dec 2016 ), arXiv:1612.03375 pages. arXiv: math.ST\/1612.03375 Sample complexity of the distinct elements problem. arXiv e-prints, Article arXiv:1612.03375 (Dec 2016), arXiv:1612.03375 pages. arXiv: math.ST\/1612.03375"},{"key":"e_1_3_2_1_41_1","volume-title":"Kaitlin Samocha, Monkol Lek, Shamil Sunyaev, Mark Daly, and Daniel G. MacArthur.","author":"Zou James","year":"2016","unstructured":"James Zou , Gregory Valiant , Paul Valiant , Konrad Karczewski , Siu On Chan , Kaitlin Samocha, Monkol Lek, Shamil Sunyaev, Mark Daly, and Daniel G. MacArthur. 2016 . James Zou, Gregory Valiant, Paul Valiant, Konrad Karczewski, Siu On Chan, Kaitlin Samocha, Monkol Lek, Shamil Sunyaev, Mark Daly, and Daniel G. MacArthur. 2016."}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316398","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316398","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":40,"alternative-id":["10.1145\/3313276.3316398","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316398","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}