{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:46:45Z","timestamp":1770994005624,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439470","type":"print"},{"value":"9783662439487","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_24","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"283-295","source":"Crossref","is-referenced-by-count":9,"title":["Testing Probability Distributions Underlying Aggregated Data"],"prefix":"10.1007","author":[{"given":"Cl\u00e9ment","family":"Canonne","sequence":"first","affiliation":[]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","unstructured":"Bar-Yossef, Z.: The Complexity of Massive Data Set Computations. Ph.D. thesis, UC Berkeley (2002), Christos Papadimitriou"},{"key":"24_CR2","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: Proceedings of FOCS, pp. 442\u2013451 (2001)","DOI":"10.1109\/SFCS.2001.959920"},{"key":"24_CR3","unstructured":"Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P.: Testing that distributions are close. In: Proceedings of FOCS, pp. 189\u2013197 (2000)"},{"key":"24_CR4","unstructured":"Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P.: Testing closeness of discrete distributions. Tech. Rep. abs\/1009.5397, ArXiv (2010), this is a long version of [3]"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Batu, T., Kumar, R., Rubinfeld, R.: Sublinear algorithms for testing monotone and unimodal distributions. In: Proceedings of STOC, pp. 381\u2013390 (2004)","DOI":"10.1145\/1007352.1007414"},{"issue":"1","key":"24_CR6","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 Journal on Computing\u00a035(1), 132\u2013150 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"24_CR7","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1214\/aos\/1176350489","volume":"15","author":"L. Birg\u00e9","year":"1987","unstructured":"Birg\u00e9, L.: On the risk of histograms for estimating decreasing densities. The Annals of Statistics\u00a015(3), 1013\u20131022 (1987)","journal-title":"The Annals of Statistics"},{"issue":"2","key":"24_CR8","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/2450142.2450148","volume":"60","author":"A. Blum","year":"2013","unstructured":"Blum, A., Ligett, K., Roth, A.: A learning theory approach to noninteractive database privacy. J. ACM\u00a060(2), 12 (2013)","journal-title":"J. ACM"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Canonne, C., Ron, D., Servedio, R.A.: Testing probability distributions using conditional samples. Tech. Rep. abs\/1211.2664, ArXiV (November 2012)","DOI":"10.1137\/1.9781611973402.87"},{"key":"24_CR10","doi-asserted-by":"crossref","unstructured":"Canonne, C., Ron, D., Servedio, R.A.: Testing equivalence between distributions using conditional samples. In: Proceedings of SODA (2014)","DOI":"10.1137\/1.9781611973402.87"},{"key":"24_CR11","first-page":"21","volume":"21","author":"C.L. Canonne","year":"2014","unstructured":"Canonne, C.L., Rubinfeld, R.: Testing probability distributions underlying aggregated data. Electronic Colloquium on Computational Complexity (ECCC)\u00a021, 21 (2014)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"24_CR12","first-page":"561","volume-title":"Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013","author":"S. Chakraborty","year":"2013","unstructured":"Chakraborty, S., Fischer, E., Goldhirsh, Y., Matsliah, A.: On the power of conditional samples in distribution testing. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013, pp. 561\u2013580. ACM, New York (2013)"},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"Chan, S.O., Diakonikolas, I., Valiant, G., Valiant, P.: Optimal Algorithms for Testing Closeness of Discrete Distributions. In: Proceedings of SODA (2014)","DOI":"10.1137\/1.9781611973402.88"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Diakonikolas, I., Servedio, R., Valiant, G., Valiant, P.: Testing k-modal distributions: Optimal algorithms via reductions. In: Proceedings of SODA (2013)","DOI":"10.1137\/1.9781611973105.131"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Dinur, I., Nissim, K.: Revealing information while preserving privacy. In: Proceedings of the Twenty-Second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 202\u2013210. ACM (2003)","DOI":"10.1145\/773153.773173"},{"key":"24_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-79228-4_1","volume-title":"Theory and Applications of Models of Computation","author":"C. Dwork","year":"2008","unstructured":"Dwork, C.: Differential privacy: A survey of results. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol.\u00a04978, pp. 1\u201319. Springer, Heidelberg (2008)"},{"key":"24_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1007\/978-3-540-28628-8_32","volume-title":"Advances in Cryptology \u2013 CRYPTO 2004","author":"C. Dwork","year":"2004","unstructured":"Dwork, C., Nissim, K.: Privacy-preserving datamining on vertically partitioned databases. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol.\u00a03152, pp. 528\u2013544. Springer, Heidelberg (2004)"},{"key":"24_CR18","unstructured":"Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. Tech. Rep. TR00-020, ECCC (2000)"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"Guha, S., McGregor, A., Venkatasubramanian, S.: Streaming and sublinear approximation of entropy and information distances. CoRR abs\/cs\/0508122 (2005)","DOI":"10.1145\/1109557.1109637"},{"key":"24_CR20","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":"2","key":"24_CR21","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF01013169","volume":"26","author":"S.K. Ma","year":"1981","unstructured":"Ma, S.K.: Calculation of entropy from data of motion. Journal of Statistical Physics\u00a026(2), 221\u2013240 (1981), http:\/\/dx.doi.org\/10.1007\/BF01013169","journal-title":"Journal of Statistical Physics"},{"issue":"10","key":"24_CR22","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-IT\u00a054(10), 4750\u20134755 (2008)","journal-title":"IEEE-IT"},{"issue":"6","key":"24_CR23","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1016\/j.jcss.2006.03.002","volume":"72","author":"M. Parnas","year":"2006","unstructured":"Parnas, M., Ron, D., Rubinfeld, R.: Tolerant property testing and distance approximation. J. Comput. Syst. Sci.\u00a072(6), 1012\u20131042 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"24_CR24","first-page":"24","volume":"34","author":"R. Rubinfeld","year":"2009","unstructured":"Rubinfeld, R., Servedio, R.A.: Testing monotone high-dimensional distributions. RSA\u00a034(1), 24\u201344 (2009)","journal-title":"RSA"},{"key":"24_CR25","unstructured":"Valiant, G., Valiant, P.: A CLT and tight lower bounds for estimating entropy. Tech. Rep. TR10-179, ECCC (2010)"},{"key":"24_CR26","doi-asserted-by":"crossref","unstructured":"Valiant, G., Valiant, P.: Estimating the unseen: A sublinear-sample canonical estimator of distributions. Tech. Rep. TR10-180, ECCC (2010)","DOI":"10.1145\/1993636.1993727"},{"key":"24_CR27","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 STOC, pp. 685\u2013694 (2011); see also [25] and [26]","DOI":"10.1145\/1993636.1993727"},{"issue":"6","key":"24_CR28","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. SICOMP\u00a040(6), 1927\u20131968 (2011)","journal-title":"SICOMP"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T06:05:45Z","timestamp":1689314745000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}