{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T09:43:03Z","timestamp":1737106983172,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540413486"},{"type":"electronic","value":"9783540444114"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44411-4_6","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T22:52:31Z","timestamp":1182207151000},"page":"71-87","source":"Crossref","is-referenced-by-count":2,"title":["Simplified Witness Tree Arguments"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Schickinger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelika","family":"Steger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,1,22]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, and Lars Rasmussen. Parallel randomized load balancing. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC-95), pages 238\u2013247. ACM Press, 1995. 72, 73","DOI":"10.1145\/225058.225131"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Yossi Azar, Andrej Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC-94), pages 593\u2013602, 1994. 71, 73, 79, 82","DOI":"10.1145\/195058.195412"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Petra Berenbrink, Artur Czumaj, Angelika Steger, and Berthold V\u00f6cking. Balanced allocation: the heavily loaded case. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC-00), pages 745\u2013754, 2000. 73","DOI":"10.1145\/335305.335411"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Richard Cole, Alan Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andr\u00e9a W. Richa, Ramesh K. Sitaraman, and Eli Upfal. On balls and bins with deletions. In Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 1998.","DOI":"10.1007\/3-540-49543-6_12"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Richard Cole, Bruce M. Maggs, Friedhelm Meyer auf der Heide, Michael Mitzenmacher, Andrea W. Richa, Klaus Schr\u00f6der, Ramesh K. Sitaraman, and Berthold V\u00f6cking. Randomized protocols for low-congestion circuit routing in multistage interconnection networks. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC-98), pages 378\u2013388, 1998.","DOI":"10.1145\/276698.276790"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Artur Czumaj, Friedhelm Meyer auf der Heide, and Volker Stemann. Improved optimal shared memory simulations, and the power of reconfiguration. In Proceedings of the 3rd Israel Symposium on Theory of Computing, pages 11\u201319, 1995.","DOI":"10.1109\/ISTCS.1995.377051"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Artur Czumaj and Volker Stemann. Randomized allocation processes. In Proceedings of the 38th IEEE Symposium on the Foundations of Computer Science (FOCS-97), pages 194\u2013203, 1997. 73","DOI":"10.1109\/SFCS.1997.646108"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. Simple, efficient shared memory simulations (extended abstract). In Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA-93), pages 110\u2013119, 1993.","DOI":"10.1145\/165231.165246"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Leslie Ann Goldberg, Yossi Matias, and Satish Rao. An optical simulation of shared memory. In Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA-94), pages 257\u2013267, New York, 1994. ACM Press.","DOI":"10.1145\/181014.181406"},{"issue":"2","key":"6_CR10","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/322248.322254","volume":"28","author":"G. H. Gonnet","year":"1981","unstructured":"Gaston H. Gonnet. Expected length of the longest probe sequence in hash code searching. Journal of the ACM, 28(2):289\u2013304, 1981. 71","journal-title":"Journal of the ACM"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Richard M. Karp, Michael Luby, and Friedhelm Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC-92), pages 318\u2013326. ACM Press, 1992.","DOI":"10.1145\/129712.129743"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Philip. D. MacKenzie, C. Greg Plaxton, and Rajmohan Rajaraman. On contention resolution protocols and associated probabilistic phenomena. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC-94), pages 153\u2013162, 1994.","DOI":"10.1145\/195058.195122"},{"key":"6_CR13","series-title":"Lect Notes Comput Sci","first-page":"267","volume-title":"Exploiting storage redundancy to speed up randomized shared memory simulations","author":"F. Meyer auf der Heide","year":"1995","unstructured":"Friedhelm Meyer auf der Heide, Christian Scheideler, and Volker Stemann. Exploiting storage redundancy to speed up randomized shared memory simulations. In Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS-95), volume LNCS 900, pages 267\u2013278. Springer-Verlag, 1995."},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher. Density dependent jump markov processes and applications to load balancing. In Proceedings of the 37th IEEE Symposium on Foundations (FOCS-96), pages 213\u2013223, 1996.","DOI":"10.1109\/SFCS.1996.548480"},{"key":"6_CR15","unstructured":"Michael Mitzenmacher. On the Power of Two Choices in Randomized Load Balancing. PhD thesis, 1996. 71"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher. On the analysis of randomized load balancing schemes. In Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Arrays (SPAA-97), pages 292\u2013301, 1997.","DOI":"10.1145\/258492.258521"},{"key":"6_CR17","series-title":"Lect Notes Comput Sci","first-page":"159","volume-title":"Balls into bins\u2014a simple and tight analysis","author":"M. Raaban","year":"1998","unstructured":"Martin Raaban and Angelika Steger. Balls into bins\u2014a simple and tight analysis. In Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM-98), volume LNCS 1518, pages 159\u2013170, 1998"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Volker Stemann. Parallel balanced allocations. In Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA-96), pages 261\u2013269, 1996.","DOI":"10.1145\/237502.237565"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Berthold V\u00f6cking. How asymmetry helps load balancing. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS-99), pages 131\u2013140, 1999.","DOI":"10.1109\/SFFCS.1999.814585"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2000: Theory and Practice of Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44411-4_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T09:01:12Z","timestamp":1737104472000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44411-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540413486","9783540444114"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-44411-4_6","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}