{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:48Z","timestamp":1740109308599,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,10,3]],"date-time":"2020-10-03T00:00:00Z","timestamp":1601683200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,10,3]],"date-time":"2020-10-03T00:00:00Z","timestamp":1601683200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"EU project QAP"},{"name":"BRICKS","award":["AFM1"],"award-info":[{"award-number":["AFM1"]}]},{"name":"NWO VICI","award":["639.023.302","639.023.302"],"award-info":[{"award-number":["639.023.302","639.023.302"]}]},{"name":"GA CR","award":["201\/07\/P276","201\/05\/0124"],"award-info":[{"award-number":["201\/07\/P276","201\/05\/0124"]}]},{"name":"Russian Academic Excellence Project \u20195-100\u2019"},{"DOI":"10.13039\/501100002261","name":"Russian Foundation for Basic Research","doi-asserted-by":"publisher","award":["19-01-00563"],"award-info":[{"award-number":["19-01-00563"]}],"id":[{"id":"10.13039\/501100002261","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,2]]},"DOI":"10.1007\/s00453-020-00770-y","type":"journal-article","created":{"date-parts":[[2020,10,3]],"date-time":"2020-10-03T16:02:24Z","timestamp":1601740944000},"page":"667-694","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["High Entropy Random Selection Protocols"],"prefix":"10.1007","volume":"83","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Christandl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Kouck\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zvi","family":"Lotker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boaz","family":"Patt-Shamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7386-979X","authenticated-orcid":false,"given":"Nikolay","family":"Vereshchagin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,10,3]]},"reference":[{"key":"770_CR1","unstructured":"Alon, N., Naor, M.: Coin-flipping games immune against linear-sized coalitions. In: Proc. 31st FOCS, (1990)"},{"key":"770_CR2","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N Alon","year":"2000","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Wiley, Hoboken (2000)","edition":"2"},{"key":"770_CR3","unstructured":"Ambainis, A., Buhrman, H., Dodis, Y., R\u00f6hrig, H.: Flipping, multiparty quantum coin. In: IEEE Conference on Computational Complexity 2004, pp. 250\u2013259 (2004)"},{"key":"770_CR4","unstructured":"Blum, M.: Coin flipping by telephone. In: IEEE Spring COMPCOM, (1982)"},{"key":"770_CR5","volume-title":"Randomness and Computation","author":"M Ben-Or","year":"1989","unstructured":"Ben-Or, M., Linial, N.: Collective coin-flipping. In: Micali, S. (ed.) Randomness and Computation. Academic Press, New York (1989)"},{"key":"770_CR6","unstructured":"Broughan, K.A.: The gcd-sum function. J. Integer Seq, 4, Article 01.2.2 (2001)"},{"key":"770_CR7","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Christandl, M., Kouck\u00fd, M., Lotker, Z., Patt-Shamir, B., Vereshchagin, N. K.: High Entropy Random Selection Protocols. In: Proceedings of 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20\u201322, 2007. Proceedings. Lecture Notes in Computer Science, volume 4627\/2007 pp. 366\u2013379","DOI":"10.1007\/978-3-540-74208-1_27"},{"key":"770_CR8","unstructured":"Cachin, C., Crepeau, C., Marcil, J.: Oblivious transfer with a memory-bounded receiver. In: Proc. 39th FOCS, (1998)"},{"key":"770_CR9","doi-asserted-by":"crossref","unstructured":"Damgard, I.: Interactive hashing can simplify zero-knowledge protocol design. In: Proc. CRYPTO \u201995, Springer LNCS 403, (1994)","DOI":"10.7146\/brics.v1i39.21604"},{"key":"770_CR10","doi-asserted-by":"crossref","unstructured":"Damgard, I., Goldreich, O., Wigderson, A.: Hashing functions can simplify zero-knowledge protocol design (too). TR RS-94-39. BRICS, (1994)","DOI":"10.7146\/brics.v1i39.21604"},{"key":"770_CR11","doi-asserted-by":"crossref","unstructured":"Ding, Y., Harnik, D., Rosen, A., Shaltiel, R.: Constant-round oblivious transfer in the bounded storage model. In: Proc. 1st TCC, Springer LNCS 2951, (2004)","DOI":"10.1007\/978-3-540-24638-1_25"},{"key":"770_CR12","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1090\/S0894-0347-08-00607-3","volume":"22","author":"Z Dvir","year":"2009","unstructured":"Dvir, Z.: On the size of Kakeya sets in finite fields. J. Am. Math. Soc. 22, 1093\u20131097 (2009)","journal-title":"J. Am. Math. Soc."},{"key":"770_CR13","doi-asserted-by":"crossref","unstructured":"Dvir, Z., Wigderson, A.: Kakeya sets, new mergers and old extractors. In: FOCS \u201908 Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 625-633. IEEE Computer Society, (2008)","DOI":"10.1109\/FOCS.2008.23"},{"key":"770_CR14","unstructured":"Feige, U.: Noncryptographic selection protocols. In: Proc. 40th FOCS, (1999)"},{"issue":"2","key":"770_CR15","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1137\/S0097539793246689","volume":"27","author":"O Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Linial, N.: Fault-tolerant computation in the full information model. SIAM J. Comput. 27(2), 506\u2013544 (1998)","journal-title":"SIAM J. Comput."},{"key":"770_CR16","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Sahai, A., Vadhan, S.: Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In: Proc. 30th STOC, (1998)","DOI":"10.1145\/276698.276852"},{"key":"770_CR17","doi-asserted-by":"crossref","unstructured":"Gradwohl, R., Vadhan, S., Zuckerman, D.: Random selection with an Adversarial Majority In: Dwork, C. (Eds) Advances in Cryptology\u2014CRYPTO \u201806, number 4117 in Lecture Notes in Computer Science, pp. 409\u2013426, 2006. Electronic Colloquium on Computational Complexity, Technical Report TR06-026, (2006)","DOI":"10.1007\/11818175_25"},{"key":"770_CR18","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1215\/S0012-7094-04-12112-8","volume":"121","author":"Gerd Mockenhaupt","year":"2004","unstructured":"Mockenhaupt, Gerd, Tao, Terence: Restriction and Kakeya phenomena for finite fields. Duke Math. J. 121, 35\u201374 (2004)","journal-title":"Duke Math. J."},{"key":"770_CR19","doi-asserted-by":"crossref","unstructured":"Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP can be based on general complexity assumptions. J. Cryptol. 11, (1998)","DOI":"10.1007\/s001459900037"},{"issue":"8","key":"770_CR20","doi-asserted-by":"publisher","first-page":"083037","DOI":"10.1088\/1367-2630\/10\/8\/083037","volume":"10","author":"AT Nguyen","year":"2008","unstructured":"Nguyen, A.T., Frison, J., Huy, K.P., Massar, S.: Experimental quantum tossing of a single coin. New J. Phys. 10(8), 083037 (2008)","journal-title":"New J. Phys."},{"key":"770_CR21","doi-asserted-by":"crossref","unstructured":"Muchnik, A., Vereshchagin, N.: Shannon entropy vs. Kolmogorov complexity. In: Computer Science\u2014Theory and Applications: First International Computer Science Symposium in Russia, CSR 2006. Proceedings. Editors: Dima, G., John, H., Hirsch, E. A. (Eds.), Lecture Notes in Computer Science, vol. 3967, 2006, pp. 281\u2013291","DOI":"10.1007\/11753728_29"},{"key":"770_CR22","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rajagopalan, S., Vazirani, U.: Simple and efficient leader election in the full information model. In: Proc. 26th STOC, (1994)","DOI":"10.1145\/195058.195141"},{"key":"770_CR23","unstructured":"Russell, A., Zuckerman, D.: Perfect information leader election in $$\\log ^* n+O(1)$$ rounds. In: Proc. 39th FOCS, (1998)"},{"issue":"2","key":"770_CR24","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/0402020","volume":"2","author":"M Saks","year":"1989","unstructured":"Saks, M.: A robust noncryptographic protocol for collective coin-flipping. SIAM J. Discret. Math 2(2), 240\u2013244 (1989)","journal-title":"SIAM J. Discret. Math"},{"key":"770_CR25","unstructured":"Sanghvi, S., Vadhan, S.: the round complexity of two-party random selection. In: Thirty-seventh Annual ACM Symposium on Theory of Computing. Baltimore, MD, USA. Proceedings, pp. 338\u2013347"},{"key":"770_CR26","doi-asserted-by":"crossref","unstructured":"Stepanov, T.: Random selection in few rounds. In: Proceedings of 8th International Computer Science Symposium in Russia, CSR 2013. Lecture Notes in Computer Science v. 7913, pp. 354\u2013365","DOI":"10.1007\/978-3-642-38536-0_31"},{"key":"770_CR27","volume-title":"Prospects in Mathematics","author":"T Wolff","year":"1999","unstructured":"Wolff, T.: Recent work connected with the Kakeya problem. In: Rossi, H. (ed.) Prospects in Mathematics. AMS, Providence (1999)"},{"key":"770_CR28","unstructured":"Zermelo, E.: \u00dcber eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In: Proceedings of the Fifth International Congress Mathematics pp. 501\u2013504 (1913)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00770-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00770-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00770-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,4]],"date-time":"2021-10-04T20:42:15Z","timestamp":1633380135000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00770-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,3]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["770"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00770-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,10,3]]},"assertion":[{"value":"18 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}