{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:51Z","timestamp":1740109311480,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T00:00:00Z","timestamp":1650585600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T00:00:00Z","timestamp":1650585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100013209","name":"Hellenic Foundation for Research and Innovation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100013209","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013209","name":"Hellenic Foundation for Research and Innovation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100013209","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s00453-022-00961-9","type":"journal-article","created":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T13:14:46Z","timestamp":1650633286000},"page":"2186-2221","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Parameter Estimation of Truncated Boolean Product Distributions"],"prefix":"10.1007","volume":"84","author":[{"given":"Dimitris","family":"Fotakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1479-5268","authenticated-orcid":false,"given":"Alkis","family":"Kalavasis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Tzamos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,22]]},"reference":[{"key":"961_CR1","doi-asserted-by":"crossref","unstructured":"Acharya, J., Canonne, C.L., Kamath, G.: Adaptive estimation in weighted group testing. In: Proceedings of the 2015 IEEE International Symposium on Information Theory, ISIT\u201915. IEEE Computer Society, pp. 2116\u20132120 (2015)","DOI":"10.1109\/ISIT.2015.7282829"},{"key":"961_CR2","unstructured":"Acharya, J., Canonne, C.L., Kamath, G.: A chasm between identity and equivalence testing with conditional queries. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, RANDOM\u201915, pp. 449\u2013466 (2015)"},{"key":"961_CR3","unstructured":"Acharya, J., Daskalakis, C., Kamath, G.: Optimal Testing for Properties of Distributions. In: Proceedings of the 28th International Conference on Neural Information Processing Systems (NIPS), pp. 3591\u20133599 (2015). arXiv:1507.05952"},{"key":"961_CR4","first-page":"53","volume":"12","author":"B Babington Smith","year":"1950","unstructured":"Babington Smith, B.: Discussion of Professor Ross\u2019s paper. J. R. Stat. Soc. B 12, 53\u201356 (1950)","journal-title":"J. R. Stat. Soc. B"},{"issue":"4","key":"961_CR5","first-page":"16:1","volume":"10","author":"R Bhattacharyya","year":"2018","unstructured":"Bhattacharyya, R., Chakraborty, S.: Property testing of joint distributions using conditional samples. Trans. Comput. Theory 10(4), 16:1-16:20 (2018)","journal-title":"Trans. Comput. Theory"},{"key":"961_CR6","first-page":"324","volume":"39","author":"R Bradley","year":"1952","unstructured":"Bradley, R., Terry, M.: Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika 39, 324 (1952)","journal-title":"Biometrika"},{"key":"961_CR7","unstructured":"Busa-Fekete, R., Fotakis, D., Sz\u00f6r\u00e9nyi, B., Zampetakis, M.: Optimal Learning of Mallows Block Model. CoRR arXiv:abs\/1906.01009 (2019)"},{"key":"961_CR8","doi-asserted-by":"crossref","unstructured":"Canonne, C.L.: Big Data on the rise? Testing monotonicity of distributions. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP\u201915, pp. 294\u2013305 (2015)","DOI":"10.1007\/978-3-662-47672-7_24"},{"key":"961_CR9","unstructured":"Canonne, C.L., Chen, X., Kamath, G., Levi, A., Waingarten, E.: Random restrictions of high-dimensional distributions and uniformity testing with subcube conditioning. CoRR arXiv:abs\/1911.07357 (2019)"},{"key":"961_CR10","doi-asserted-by":"crossref","unstructured":"Canonne, C.L., De, A., Servedio, R.A.: Learning from satisfying assignments under continuous distributions. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, pp. 82\u2013101 (2020)","DOI":"10.1137\/1.9781611975994.6"},{"key":"961_CR11","unstructured":"Canonne, C.L., Diakonikolas, I., Kane, D.M., Stewart, A.: Testing Bayesian networks. In: Proceedings of the 30th Annual Conference on Learning Theory, (COLT), pp. 370\u2013448 (2017). arXiv:1612.03156"},{"key":"961_CR12","unstructured":"Canonne, C.L., Kamath, G., McMillan, A., Ullman, J., Zakynthinou, L.: Private Identity Testing for High-Dimensional Distributions. arXiv preprint arXiv:1905.11947 (2019)"},{"key":"961_CR13","doi-asserted-by":"crossref","unstructured":"Canonne, C.L., Ron, D., Servedio, R.A.: Testing equivalence between distributions using conditional samples. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201914. SIAM, pp. 1174\u20131192 (2014)","DOI":"10.1137\/1.9781611973402.87"},{"issue":"3","key":"961_CR14","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. 44(3), 540\u2013616 (2015)","journal-title":"SIAM J. Comput."},{"key":"961_CR15","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Procaccia, A.D., Shah, N.: When do noisy votes reveal the truth? In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pp. 143\u2013160 (2013)","DOI":"10.1145\/2482540.2482570"},{"key":"961_CR16","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 the 4th Conference on Innovations in Theoretical Computer Science, ITCS\u201913. ACM, pp. 561\u2013580 (2013)","DOI":"10.1145\/2422436.2422497"},{"key":"961_CR17","doi-asserted-by":"crossref","unstructured":"Charikar, M., Steinhardt, J., Valiant, G.: Learning from untrusted data. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pp. 47\u201360 (2017)","DOI":"10.1145\/3055399.3055491"},{"key":"961_CR18","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Gouleakis, T., Tzamos, C., Zampetakis, M.: Efficient statistics, in high dimensions, from truncated samples. In: 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, pp. 639\u2013649 (2018). arXiv:1809.03986","DOI":"10.1109\/FOCS.2018.00067"},{"key":"961_CR19","unstructured":"Daskalakis, C., Gouleakis, T., Tzamos, C., Zampetakis, M.: Computationally and Statistically Efficient Truncated Regression. In: Conference on Learning Theory (COLT), pp. 955\u2013960 (2019)"},{"key":"961_CR20","doi-asserted-by":"crossref","unstructured":"De, A., Diakonikolas, I., Servedio, R.A.: Learning from satisfying assignments. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, pp. 478\u2013497 (2014)","DOI":"10.1137\/1.9781611973730.33"},{"key":"961_CR21","doi-asserted-by":"publisher","unstructured":"Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Moitra, A., Stewart, A.: Robust estimators in high dimensions without the computational intractability. In: IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pp. 655\u2013664 (2016). https:\/\/doi.org\/10.1109\/FOCS.2016.85","DOI":"10.1109\/FOCS.2016.85"},{"key":"961_CR22","unstructured":"Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Moitra, A., Stewart, A.: Being robust (in high dimensions) can be practical. In: Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6\u201311 August 2017, pp. 999\u20131008 (2017)"},{"key":"961_CR23","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Moitra, A., Stewart, A.: Robustly learning a Gaussian: getting optimal error, efficiently. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7\u201310, 2018, pp. 2683\u20132702 (2018)","DOI":"10.1137\/1.9781611975031.171"},{"key":"961_CR24","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Kane, D.M., Stewart, A.: Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, pp. 73\u201384 (2017)","DOI":"10.1109\/FOCS.2017.16"},{"key":"961_CR25","unstructured":"Falahatgar, M., Jafarpour, A., Orlitsky, A., Pichapati, V., Suresh, A.T.: Faster algorithms for testing under conditional sampling. In: Proceedings of the 28th Annual Conference on Learning Theory, COLT\u201915, pp. 607\u2013636 (2015)"},{"key":"961_CR26","first-page":"815","volume":"1","author":"R Fisher","year":"1931","unstructured":"Fisher, R.: Properties and applications of Hh functions. Math. Tables 1, 815\u2013852 (1931)","journal-title":"Math. Tables"},{"key":"961_CR27","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1111\/j.2517-6161.1986.tb01420.x","volume":"48","author":"MA Fligner","year":"1986","unstructured":"Fligner, M.A., Verducci, J.S.: Distance based ranking models. J. R. Stat. Soc. Ser. B (Methodological) 48, 359\u2013369 (1986)","journal-title":"J. R. Stat. Soc. Ser. B (Methodological)"},{"issue":"379\u2013387","key":"961_CR28","first-page":"310","volume":"62","author":"F Galton","year":"1897","unstructured":"Galton, F.: An examination into the registered speeds of American trotting horses, with remarks on their value as hereditary data. Proc. R. Soc. Lond. 62(379\u2013387), 310\u2013315 (1897)","journal-title":"Proc. R. Soc. Lond."},{"key":"961_CR29","doi-asserted-by":"crossref","unstructured":"Gouleakis, T., Tzamos, C., Zampetakis, M.: Faster sublinear algorithms using conditional sampling. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201917. SIAM, pp. 1743\u20131757 (2017)","DOI":"10.1137\/1.9781611974782.114"},{"key":"961_CR30","unstructured":"Hopkins, S.B., Li, J.: How hard is robust mean estimation? In: Conference on Learning Theory, pp. 1649\u20131682 (2019)"},{"key":"961_CR31","unstructured":"Kamath, G., Li, J., Singhal, V., Ullman, J.: Privately learning high-dimensional distributions. arXiv preprint arXiv:1805.00216 (2018)"},{"key":"961_CR32","doi-asserted-by":"crossref","unstructured":"Kamath, G., Tzamos, C.: Anaconda: a non-adaptive conditional sampling algorithm for distribution testing. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, pp. 679\u2013693 (2019)","DOI":"10.1137\/1.9781611975482.43"},{"key":"961_CR33","doi-asserted-by":"crossref","unstructured":"Kontonis, V., Tzamos, C., Zampetakis, M.: Efficient truncated statistics with unknown truncation. In: 260th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, pp. 1578\u20131595 (2019)","DOI":"10.1109\/FOCS.2019.00093"},{"key":"961_CR34","doi-asserted-by":"crossref","unstructured":"Lai, K.A., Rao, A.B., Vempala, S.: Agnostic estimation of mean and covariance. In: IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 665\u2013674 (2016)","DOI":"10.1109\/FOCS.2016.76"},{"issue":"2\/3","key":"961_CR35","doi-asserted-by":"publisher","first-page":"208","DOI":"10.2307\/2331782","volume":"10","author":"A Lee","year":"1914","unstructured":"Lee, A.: Table of the Gaussian \u201cTail\u2019\u2019 functions; when the \u201cTail\u2019\u2019 is larger than the body. Biometrika 10(2\/3), 208\u2013214 (1914)","journal-title":"Biometrika"},{"key":"961_CR36","volume-title":"Individual Choice Behavior","author":"R Luce","year":"1959","unstructured":"Luce, R.: Individual Choice Behavior. Wiley, New York (1959)"},{"issue":"1\/2","key":"961_CR37","doi-asserted-by":"publisher","first-page":"114","DOI":"10.2307\/2333244","volume":"44","author":"CL Mallows","year":"1957","unstructured":"Mallows, C.L.: Non-null ranking models. I. Biometrika 44(1\/2), 114\u2013130 (1957)","journal-title":"Biometrika"},{"key":"961_CR38","unstructured":"Nagarajan, S.G., Panageas, I.: On the analysis of EM for truncated mixtures of two Gaussians. In: 31st International Conference on Algorithmic Learning Theory (ALT), pp. 955\u2013960 (2019)"},{"issue":"1","key":"961_CR39","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1093\/biomet\/6.1.59","volume":"6","author":"K Pearson","year":"1908","unstructured":"Pearson, K., Lee, A.: On the generalised probable error in multiple normal correlation. Biometrika 6(1), 59\u201368 (1908)","journal-title":"Biometrika"},{"key":"961_CR40","doi-asserted-by":"publisher","first-page":"193","DOI":"10.2307\/2346567","volume":"24","author":"R Plackett","year":"1975","unstructured":"Plackett, R.: The analysis of permutations. Appl. Stat. 24, 193\u2013202 (1975)","journal-title":"Appl. Stat."},{"key":"961_CR41","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019","volume-title":"Understanding Machine Learning: From Theory to Algorithms","author":"S Shalev-Shwartz","year":"2014","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, Cambridge (2014)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00961-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00961-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00961-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,22]],"date-time":"2024-09-22T19:42:40Z","timestamp":1727034160000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00961-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,22]]},"references-count":41,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["961"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00961-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,4,22]]},"assertion":[{"value":"29 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}