{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,27]],"date-time":"2023-12-27T00:04:00Z","timestamp":1703635440867},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T00:00:00Z","timestamp":1698278400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T00:00:00Z","timestamp":1698278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s00037-023-00245-w","type":"journal-article","created":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T20:01:30Z","timestamp":1698350490000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Lower Bound on the Complexity of Testing Grained Distributions"],"prefix":"10.1007","volume":"32","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,26]]},"reference":[{"key":"245_CR1","unstructured":"Tugkan Batu (2001).Testing properties of distributions.Ph.D. thesis, Computer Science department, Cornell University."},{"key":"245_CR2","doi-asserted-by":"crossref","unstructured":"Tugkan Batu & Cl\u00e9ment L. Canonne (2017).Generalized Uniformity Testing. In Proceedings of the Fiftieth-Eighth Annual Symposium on Foundations of Computer Science (FOCS), 880\u2013889.","DOI":"10.1109\/FOCS.2017.86"},{"key":"245_CR3","doi-asserted-by":"crossref","unstructured":"Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld & Patrick White (2001). Testing Random Variables for Independence and Identity. In Proceedings of the Forty-Second Annual Symposium on Foundations of Computer Science (FOCS), 442\u2013451.","DOI":"10.1109\/SFCS.2001.959920"},{"key":"245_CR4","doi-asserted-by":"crossref","unstructured":"Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith & Patrick White (2000). Testing that distributions are close. In Proceedings of the Forty-First Annual Symposium on Foundations of Computer Science (FOCS), 259\u2013269. ISSN 0272-5428. The journal version of this paper appeared as ?.","DOI":"10.1109\/SFCS.2000.892113"},{"key":"245_CR5","unstructured":"Oded Goldreich (2016). The Uniform Distribution is Complete with respect to Testing Identity to a Fixed Distribution. Technical Report TR15-015, Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"245_CR6","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2017). Introduction to Property Testing. Cambridge University Press.","DOI":"10.1017\/9781108135252"},{"key":"245_CR7","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Shafi Goldwasser & Dana Ron (1998). Property testing and its connections to learning and approximation. Journal of the ACM 45, 653\u2013750.","DOI":"10.1145\/285055.285060"},{"key":"245_CR8","doi-asserted-by":"crossref","unstructured":"Sofya Raskhodnikova, Dana Ron, Amir Shpilka & Adam Smith (2009). Strong lower bonds for approximating distributions support size and the distinct elements problem. SIAM Journal on Computing 39(3), 813\u2013842.","DOI":"10.1137\/070701649"},{"key":"245_CR9","unstructured":"Steven Roman (2005). Advanced Linear Algebra. Springer. Graduate Texts in Mathematics, Vol. 135."},{"key":"245_CR10","doi-asserted-by":"crossref","unstructured":"Gregory Valiant & Paul Valiant (2017). Estimating the Unseen: Improved Estimators for Entropy and Other Properties. Journal of the ACM 64(6).","DOI":"10.1145\/3125643"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00245-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-023-00245-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00245-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,26]],"date-time":"2023-12-26T19:05:05Z","timestamp":1703617505000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-023-00245-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,26]]},"references-count":10,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["245"],"URL":"https:\/\/doi.org\/10.1007\/s00037-023-00245-w","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,26]]},"assertion":[{"value":"12 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"11"}}