{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T06:34:42Z","timestamp":1774679682574,"version":"3.50.1"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T00:00:00Z","timestamp":1497916800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T00:00:00Z","timestamp":1497916800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1115703"],"award-info":[{"award-number":["CCF-1115703"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1319788"],"award-info":[{"award-number":["CCF-1319788"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1652862"],"award-info":[{"award-number":["CCF-1652862"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00224-017-9785-6","type":"journal-article","created":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T06:12:04Z","timestamp":1497939124000},"page":"4-62","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Testing Shape Restrictions of Discrete Distributions"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7153-5211","authenticated-orcid":false,"given":"Cl\u00e9ment L.","family":"Canonne","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilias","family":"Diakonikolas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Themis","family":"Gouleakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,6,20]]},"reference":[{"key":"9785_CR1","unstructured":"Alon, N., Andoni, A., Kaufman, T., Matulef, K., Rubinfeld, R., Xie, N.: Testing k-wise and almost k-wise independence. In: Proceedings of the 39th ACM Symposium on Theory of Computing, STOC 2007, San Diego, California, USA, June 11\u201313, 2007, pp. 496\u2013505. New York (2007)"},{"key":"9785_CR2","unstructured":"Acharya, J., Daskalakis, C.: Testing Poisson binomial distributions. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4\u20136, 2015, pp. 1829\u20131840 (2015)"},{"key":"9785_CR3","unstructured":"Acharya, J., Daskalakis, C., Kamath, G.C.: Optimal testing for properties of distributions. In: Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M. Garnett, R., Garnett, R. (eds.) Advances in Neural Information Processing Systems 28, pp. 3577\u20133598. Curran Associates, Inc. (2015)"},{"key":"9785_CR4","unstructured":"Acharya, J., Diakonikolas, I., Li, J.Z., Schmidt, L.: Sample-optimal density estimation in nearly-linear time. CoRR, arXiv: 1506.00671 (2015)"},{"issue":"2","key":"9785_CR5","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0022-0000(03)00012-6","volume":"67","author":"S Arora","year":"2003","unstructured":"Arora, S., Khot, S.: Fitting algebraic curves to noisy data. J. Comput. Syst. Sci. 67(2), 325\u2013340 (2003). Special Issue on STOC 2002","journal-title":"J. Comput. Syst. Sci."},{"key":"9785_CR6","doi-asserted-by":"crossref","unstructured":"An, M.Y.: Log-concave probability distributions: theory and statistical testing. Technical report, Centre for Labour Market and Social Research, Denmark (1996)","DOI":"10.2139\/ssrn.1933"},{"issue":"2","key":"9785_CR7","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s00199-004-0514-4","volume":"26","author":"M Bagnoli","year":"2005","unstructured":"Bagnoli, M., Bergstrom, T.: Log-concave probability and its applications. Econ. Theory 26(2), 445\u2013469 (2005)","journal-title":"Econ. Theory"},{"key":"9785_CR8","unstructured":"Barlow, R.E., Bartholomew, D.J., Bremner, J.M., Brunk, H.D.: Statistical inference under order restrictions: the theory and application of isotonic regression. Wiley Series in Probability and Mathematical Statistics. Wiley, London, New York (1972)"},{"issue":"1","key":"9785_CR9","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1137\/S0097539702403645","volume":"35","author":"T Batu","year":"2005","unstructured":"Batu, T., Dasgupta, S., Kumar, R., Rubinfeld, R.: The complexity of approximating the entropy. SIAM J. Comput. 35(1), 132\u2013150 (2005)","journal-title":"SIAM J. Comput."},{"key":"9785_CR10","doi-asserted-by":"crossref","unstructured":"Batu, T., Fischer, E., Fortnow, L., Kumar, R., Rubinfeld, R., White, P.: Testing random variables for independence and identity. In: 42nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2001, Las Vegas, Nevada, USA, October 14\u201317 2001, pp. 442\u2013451 (2001)","DOI":"10.1109\/SFCS.2001.959920"},{"key":"9785_CR11","doi-asserted-by":"crossref","unstructured":"Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P.: Testing that distributions are close. In: 41st Annual IEEE Symposium on Foundations of Computer Science, FOCS 2000, Redondo Beach, California, USA, November 12\u201314 2000, pp. 259\u2013269 (2000)","DOI":"10.1109\/SFCS.2000.892113"},{"key":"9785_CR12","unstructured":"Batu, T., Kumar, R., Rubinfeld, R.: Sublinear algorithms for testing monotone and unimodal distributions. In: Proceedings of the 36th ACM Symposium on Theory of Computing, STOC 2004, Chicago, IL, June 13\u201316, 2004, pp. 381\u2013390. ACM, New York (2004)"},{"key":"9785_CR13","first-page":"63","volume":"22","author":"CL Canonne","year":"2015","unstructured":"Canonne, C.L.: A survey on distribution testing: your data is big. But is it blue? Electronic Colloquium on Computational Complexity (ECCC) 22, 63 (2015)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"9785_CR14","doi-asserted-by":"crossref","unstructured":"Canonne, C.L.: Are few bins enough: testing histogram distributions. In: Proceedings of PODS. Association for Computing Machinery (ACM) (2016)","DOI":"10.1145\/2902251.2902274"},{"key":"9785_CR15","unstructured":"Chan, S., Diakonikolas, I., Servedio, R.A., Sun, X.: Learning mixtures of structured distributions over discrete domains. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6\u20138, 2013, pp. 1380\u20131394 (2013)"},{"key":"9785_CR16","unstructured":"Chan, S., Diakonikolas, I., Servedio, R.A., Sun, X.: Efficient density estimation via piecewise polynomial approximation. In: Proceedings of the 45th ACM Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31\u2013June 03, 2014, pp. 604\u2013613. ACM (2014)"},{"key":"9785_CR17","unstructured":"Chan, S., Diakonikolas, I., Servedio, R.A., Sun, X.: Near-optimal density estimation in near-linear time using variable-width histograms. In: Annual Conference on Neural Information Processing Systems (NIPS), pp. 1844\u20131852 (2014)"},{"key":"9785_CR18","unstructured":"Chan, S., Diakonikolas, I., Valiant, G., Valiant, P.: Optimal algorithms for testing closeness of discrete distributions. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014, pp. 1193\u20131203 (2014)"},{"key":"9785_CR19","doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Fischer, E., Goldhirsh, Y., Matsliah, A.: On the power of conditional samples in distribution testing. In: Proceedings of ITCS, pages 561\u2013580, New York, NY, USA. ACM (2013)","DOI":"10.1145\/2422436.2422497"},{"issue":"3","key":"9785_CR20","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/130945508","volume":"44","author":"CL Canonne","year":"2015","unstructured":"Canonne, C.L., Ron, D., Servedio, R.A.: Testing probability distributions using conditional samples. SIAM J. Comput. (SICOMP) 44(3), 540\u2013616 (2015)","journal-title":"SIAM J. Comput. (SICOMP)"},{"key":"9785_CR21","unstructured":"Daskalakis, C., Diakonikolas, I., O\u2019Donnell, R., Servedio, R.A., Tan, L.-Y.: Learning sums of independent integer random variables. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, USA, October 26\u201329, 2013, pp. 217\u2013226. IEEE Computer Society (2013)"},{"key":"9785_CR22","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Diakonikolas, I., Servedio, r.A.: Learning k-modal distributions via testing. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17\u201319, 2012, pp. 1371\u20131385. Society for Industrial and Applied Mathematics (SIAM) (2012)","DOI":"10.1137\/1.9781611973099.108"},{"key":"9785_CR23","unstructured":"Daskalakis, C., Diakonikolas, I., Servedio, R.A.: Learning Poisson binomial distributions. In: Proceedings of the 44th ACM Symposium on Theory of Computing, STOC 2012 Conference, New York, NY, USA, May 19\u201322, 2012, STOC \u201912, New York, NY, pp. 709\u2013728. ACM (2012)"},{"key":"9785_CR24","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Diakonikolas, I., Servedio, r.A., Valiant, G., Valiant, P.: Testing k-modal distributions: Optimal algorithms via reductions. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6\u20138, 2013, pp. 1833\u20131852. Society for Industrial and Applied Mathematics (SIAM) (2013)","DOI":"10.1137\/1.9781611973105.131"},{"key":"9785_CR25","unstructured":"Diakonikolas, I.: Learning structured distributions. In: Handbook of Big Data. CRC Press (2016)"},{"key":"9785_CR26","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Kane, D.M.: A New Approach for Testing Properties of discrete distributions. IEEE Computer Society (2016)","DOI":"10.1109\/FOCS.2016.78"},{"key":"9785_CR27","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Kane, D.M., Nikishkin, V.: Optimal algorithms and lower bounds for testing closeness of structured distributions. In: 56th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 (2015)","DOI":"10.1109\/FOCS.2015.76"},{"key":"9785_CR28","unstructured":"Diakonikolas, I., Kane, D.M., Nikishkin, V.: Testing identity of structured distributions. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4\u20136, 2015 (2015)"},{"key":"9785_CR29","unstructured":"Diakonikolas, I., Kane, D.M., Stewart, A.: Nearly optimal learning and sparse covers for sums of independent integer random variables. CoRR, arXiv: 1505.00662 (2015)"},{"key":"9785_CR30","unstructured":"Diakonikolas, I., Kane, D.M., Stewart, A.: Efficient robust proper learning of log-concave distributions. CoRR, arXiv: 1606.03077 (2016)"},{"key":"9785_CR31","unstructured":"Diakonikolas, I., Kane, D.M., Stewart, A.: Optimal learning via the fourier transform for sums of independent integer random variables. In: COLT, volume 49 of JMLR Workshop and Conference Proceedings, pp. 831\u2013849. JMLR.org, 2016. Full version in [29]"},{"issue":"3","key":"9785_CR32","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1214\/aoms\/1177728174","volume":"27","author":"A Dvoretzky","year":"1956","unstructured":"Dvoretzky, A., Kiefer, J., Wolfowitz, J.: Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Ann. Math. Stat. 27(3), 642\u2013669 (1956)","journal-title":"Ann. Math. Stat."},{"key":"9785_CR33","unstructured":"Fischer, E., Lachish, O., Vasudev, Y.: Improving and extending the testing of distributions for shape-restricted properties. arXiv: 1609.06736 (2016)"},{"key":"9785_CR34","doi-asserted-by":"crossref","unstructured":"Guha, S., McGregor, A., Venkatasubramanian, S.: Streaming and sublinear approximation of entropy and information distances. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22\u201326, 2006, pp. 733\u2013742. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2006)","DOI":"10.1145\/1109557.1109637"},{"key":"9785_CR35","unstructured":"Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. Technical Report TR00-020. In: Electronic Colloquium on Computational Complexity (ECCC) (2000)"},{"key":"9785_CR36","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1093\/biomet\/73.2.397","volume":"73","author":"P Hougaard","year":"1986","unstructured":"Hougaard, P.: Survival models for heterogeneous populations derived from stable distributions. Biometrika 73, 397\u201396 (1986)","journal-title":"Biometrika"},{"key":"9785_CR37","doi-asserted-by":"crossref","unstructured":"Indyk, P., Levi, R., Rubinfeld, R.: Approximating and testing k-histogram distributions in sub-linear time. In: Proceedings of PODS, pp. 15\u201322 (2012)","DOI":"10.1145\/2213556.2213561"},{"issue":"334","key":"9785_CR38","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1080\/01621459.1971.10482273","volume":"66","author":"J Keilson","year":"1971","unstructured":"Keilson, J., Gerber, H.: Some results for discrete unimodality. J. Am. Stat. Assoc. 66(334), 386\u2013389 (1971)","journal-title":"J. Am. Stat. Assoc."},{"issue":"5","key":"9785_CR39","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1086\/258792","volume":"71","author":"B Mandelbrot","year":"1963","unstructured":"Mandelbrot, B.: New methods in statistical economics. J. Polit. Econ. 71(5), 421\u2013440 (1963)","journal-title":"J. Polit. Econ."},{"issue":"3","key":"9785_CR40","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1214\/aop\/1176990746","volume":"18","author":"P Massart","year":"1990","unstructured":"Massart, P.: The tight constant in the Dvoretzky\u2013Kiefer\u2013Wolfowitz inequality. Ann. Probab. 18(3), 1269\u20131283 (1990)","journal-title":"Ann. Probab."},{"key":"9785_CR41","doi-asserted-by":"crossref","unstructured":"Massart, P., Picard, J.: Concentration inequalities and model selection. Lecture Notes in Mathematics, 33, 2003, Saint-Flour, Cantal. Springer (2007)","DOI":"10.1007\/978-3-540-48503-2"},{"issue":"10","key":"9785_CR42","doi-asserted-by":"publisher","first-page":"4750","DOI":"10.1109\/TIT.2008.928987","volume":"54","author":"L Paninski","year":"2008","unstructured":"Paninski, L.: A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Trans. Inf. Theory 54(10), 4750\u20134755 (2008)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9785_CR43","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1561\/2200000004","volume":"1","author":"D Ron","year":"2008","unstructured":"Ron, D.: Property testing: a learning theory perspective. Found. Trends Mach. Learn. 1(3), 307\u2013402 (2008)","journal-title":"Found. Trends Mach. Learn."},{"key":"9785_CR44","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1561\/0400000029","volume":"5","author":"D Ron","year":"2010","unstructured":"Ron, D.: Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput. Sci. 5, 73\u2013205 (2010)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"1","key":"9785_CR45","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/2331042.2331052","volume":"19","author":"R Rubinfeld","year":"2012","unstructured":"Rubinfeld, R.: Taming big probability distributions. XRDS 19(1), 24\u201328 (2012)","journal-title":"XRDS"},{"issue":"4","key":"9785_CR46","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1002\/(SICI)1520-6750(199906)46:4<419::AID-NAV5>3.0.CO;2-B","volume":"46","author":"D Sengupta","year":"1999","unstructured":"Sengupta, D., Nanda, A.K.: Log-concave and concave distributions in reliability. Nav. Res. Logist. (NRL) 46(4), 419\u2013433 (1999)","journal-title":"Nav. Res. Logist. (NRL)"},{"key":"9785_CR47","doi-asserted-by":"publisher","DOI":"10.1002\/9781118165614","volume-title":"Constrained Statistical Inference","author":"MJ Silvapulle","year":"2001","unstructured":"Silvapulle, M.J., Sen, P.K.: Constrained Statistical Inference. Wiley, New York (2001)"},{"key":"9785_CR48","doi-asserted-by":"publisher","first-page":"3589","DOI":"10.1103\/PhysRevLett.75.3589","volume":"75","author":"C Tsallis","year":"1995","unstructured":"Tsallis, C., Levy, S.V.F, Souza, A.M.C., Maynard, R.: Statistical-mechanical foundation of the ubiquity of L\u00e9vy distributions in nature. Phys. Rev. Lett. 75, 3589\u20133593 (1995)","journal-title":"Phys. Rev. Lett."},{"issue":"6","key":"9785_CR49","doi-asserted-by":"publisher","first-page":"1927","DOI":"10.1137\/080734066","volume":"40","author":"P Valiant","year":"2011","unstructured":"Valiant, P.: Testing symmetric properties of distributions. SIAM J. Comput. 40(6), 1927\u20131968 (2011)","journal-title":"SIAM J. Comput."},{"key":"9785_CR50","first-page":"179","volume":"17","author":"G Valiant","year":"2010","unstructured":"Valiant, G., Valiant, P.: A CLT and tight lower bounds for estimating entropy. Electron. Colloq. Comput. Complex. (ECCC) 17, 179 (2010)","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"key":"9785_CR51","doi-asserted-by":"crossref","unstructured":"Valiant, G., Valiant, P.: Estimating the unseen: an $n\/\\log n$-sample estimator for entropy and support size, shown optimal via new clts. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6\u20138 June 2011, pp. 685\u2013694 (2011)","DOI":"10.1145\/1993636.1993727"},{"key":"9785_CR52","unstructured":"Valiant, G., Valiant, P.: The power of linear estimators. In: 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22\u201325, 2011, pp. 403\u2013412 (2011)"},{"key":"9785_CR53","unstructured":"Valiant, G., Valiant, P.: An automatic inequality prover and instance optimal identity testing. In: 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18\u201321, 2014 (2014)"},{"issue":"3","key":"9785_CR54","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1214\/09-STS303","volume":"24","author":"G Walther","year":"2009","unstructured":"Walther, G.: Inference and modeling with log-concave distributions. Stat. Sci. 24(3), 319\u2013327 (2009)","journal-title":"Stat. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9785-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9785-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9785-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T20:04:43Z","timestamp":1750363483000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9785-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,20]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["9785"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9785-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,20]]},"assertion":[{"value":"20 June 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}