{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T17:45:24Z","timestamp":1742924724551,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030752415"},{"type":"electronic","value":"9783030752422"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-75242-2_10","type":"book-chapter","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T15:22:29Z","timestamp":1620141749000},"page":"144-157","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fragile Complexity of Adaptive Algorithms"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1825-0097","authenticated-orcid":false,"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4318-5282","authenticated-orcid":false,"given":"Pilar","family":"Cano","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1004-3314","authenticated-orcid":false,"given":"Rolf","family":"Fagerberg","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8885-8172","authenticated-orcid":false,"given":"John","family":"Iacono","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9470-1809","authenticated-orcid":false,"given":"Riko","family":"Jacob","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6999-3088","authenticated-orcid":false,"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,4]]},"reference":[{"key":"10_CR1","unstructured":"Afshani, P., et al.: Fragile complexity of comparison-based algorithms. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms, ESA 2019, 9\u201311 September 2019, Munich\/Garching, Germany. LIPIcs, vol. 144, pp. 2:1\u20132:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: An $$O(n \\log n)$$ sorting network. In: Proceedings of the 15th Symposium on Theory of Computation, STOC 1983, pp. 1\u20139. ACM (1983)","DOI":"10.1145\/800061.808726"},{"issue":"1","key":"10_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M Ajtai","year":"1983","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: Sorting in $$c \\log n$$ parallel steps. Combinatorica 3(1), 1\u201319 (1983)","journal-title":"Combinatorica"},{"issue":"5","key":"10_CR4","first-page":"99","volume":"5","author":"VE Alekseev","year":"1969","unstructured":"Alekseev, V.E.: Sorting algorithms with minimum memory. Kibernetika 5(5), 99\u2013103 (1969)","journal-title":"Kibernetika"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Batcher, K.E.: Sorting networks and their applications. In: Proceedings of AFIPS Spring Joint Computer Conference, pp. 307\u2013314 (1968)","DOI":"10.1145\/1468075.1468121"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Bose, P., Cano, P., Fagerberg, R., Iacono, J., Jacob, R., Langerman, S.: Fragile complexity of adaptive algorithms (2021). To appear in arXiv","DOI":"10.1007\/978-3-030-75242-2_10"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/BFb0054364","volume-title":"Algorithm Theory \u2014 SWAT\u201998","author":"GS Brodal","year":"1998","unstructured":"Brodal, G.S., Pinotti, M.C.: Comparator networks for binary heap construction. In: Arnborg, S., Ivansson, L. (eds.) SWAT 1998. LNCS, vol. 1432, pp. 158\u2013168. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0054364"},{"issue":"6","key":"10_CR8","doi-asserted-by":"publisher","first-page":"1765","DOI":"10.1137\/130907653","volume":"44","author":"J Bul\u00e1nek","year":"2015","unstructured":"Bul\u00e1nek, J., Kouck\u00fd, M., Saks, M.E.: Tight lower bounds for the online labeling problem. SIAM J. Comput. 44(6), 1765\u20131797 (2015)","journal-title":"SIAM J. Comput."},{"key":"10_CR9","unstructured":"Chv\u00e1tal, V.: Lecture notes on the new AKS sorting network. Technical report DCS-TR-294, Department of Computer Science, Rutgers University, New Brunswick, NJ, October 1992"},{"issue":"4","key":"10_CR10","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1145\/76359.76362","volume":"36","author":"M Dowd","year":"1989","unstructured":"Dowd, M., Perl, Y., Rudolph, L., Saks, M.: The periodic balanced sorting network. J. ACM 36(4), 738\u2013757 (1989)","journal-title":"J. ACM"},{"issue":"4","key":"10_CR11","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1145\/146370.146381","volume":"24","author":"V Estivill-Castro","year":"1992","unstructured":"Estivill-Castro, V., Wood, D.: A survey of adaptive sorting algorithms. ACM Comput. Surv. 24(4), 441\u2013476 (1992)","journal-title":"ACM Comput. Surv."},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Fredman, M.L.: Two applications of a probabilistic search technique: sorting x + y and building balanced search trees. In: Rounds, W.C., Martin, N., Carlyle, J.W., Harrison, M.A. (eds.) Proceedings of the 7th Annual ACM Symposium on Theory of Computing, Albuquerque, New Mexico, USA, 5\u20137 May 1975, pp. 240\u2013244. ACM (1975)","DOI":"10.1145\/800116.803774"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T.: Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in $$O(n \\log n)$$ time. In: Shmoys, D.B. (ed.) STOC 2014, pp. 684\u2013693. ACM (2014)","DOI":"10.1145\/2591796.2591830"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16\u201318 October 1978, pp. 8\u201321. IEEE Computer Society (1978)","DOI":"10.1109\/SFCS.1978.3"},{"key":"10_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/3-540-10843-2_34","volume-title":"Automata, Languages and Programming","author":"A Itai","year":"1981","unstructured":"Itai, A., Konheim, A.G., Rodeh, M.: A sparse table implementation of priority queues. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol. 115, pp. 417\u2013431. Springer, Heidelberg (1981). https:\/\/doi.org\/10.1007\/3-540-10843-2_34"},{"issue":"4","key":"10_CR16","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1137\/S0097539793248329","volume":"25","author":"S Jimbo","year":"1996","unstructured":"Jimbo, S., Maruoka, A.: A method of constructing selection networks with $${O}(\\log n)$$ depth. SIAM J. Comput. 25(4), 709\u2013739 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"10_CR17","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1142\/S0129626492000337","volume":"2","author":"I Parberry","year":"1992","unstructured":"Parberry, I.: The pairwise sorting network. Parallel Process. Lett. 2(2\u20133), 205\u2013211 (1992)","journal-title":"Parallel Process. Lett."},{"issue":"3","key":"10_CR18","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0020-0190(89)90196-8","volume":"33","author":"B Parker","year":"1989","unstructured":"Parker, B., Parberry, I.: Constructing sorting networks from $$k$$-sorters. Inf. Process. Lett. 33(3), 157\u2013162 (1989)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10_CR19","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF01840378","volume":"5","author":"MS Paterson","year":"1990","unstructured":"Paterson, M.S.: Improved sorting networks with $${O}(\\log {N})$$ depth. Algorithmica 5(1), 75\u201392 (1990)","journal-title":"Algorithmica"},{"issue":"5","key":"10_CR20","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1137\/0220054","volume":"20","author":"N Pippenger","year":"1991","unstructured":"Pippenger, N.: Selection networks. SIAM J. Comput. 20(5), 878\u2013887 (1991)","journal-title":"SIAM J. Comput."},{"key":"10_CR21","unstructured":"Pratt, V.R.: Shellsort and Sorting Networks. Outstanding Dissertations in the Computer Sciences, Garland Publishing, New York (1972)"},{"issue":"3","key":"10_CR22","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/s00453-007-9025-6","volume":"53","author":"JI Seiferas","year":"2009","unstructured":"Seiferas, J.I.: Sorting networks of logarithmic depth, further simplified. Algorithmica 53(3), 374\u2013384 (2009)","journal-title":"Algorithmica"},{"key":"10_CR23","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. BAMS Bull. Am. Math. Soc. 43, 439\u2013561 (2006)","journal-title":"BAMS Bull. Am. Math. Soc."},{"issue":"1\u20133","key":"10_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000010","volume":"7","author":"SP Vadhan","year":"2012","unstructured":"Vadhan, S.P.: Pseudorandomness. Found. Trends Theoret. Comput. Sci. 7(1\u20133), 1\u2013336 (2012)","journal-title":"Found. Trends Theoret. Comput. Sci."},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"Willard, D.E.: Good worst-case algorithms for inserting and deleting records in dense sequential files. In: Zaniolo, C. (ed.) Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, Washington, DC, USA, 28\u201330 May 1986, pp. 251\u2013260. ACM Press (1986)","DOI":"10.1145\/16856.16879"},{"issue":"2","key":"10_CR26","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0890-5401(92)90034-D","volume":"97","author":"DE Willard","year":"1992","unstructured":"Willard, D.E.: A density control algorithm for doing insertions and deletions in a sequentially ordered file in good worst-case time. Inf. Comput. 97(2), 150\u2013204 (1992)","journal-title":"Inf. Comput."},{"issue":"3","key":"10_CR27","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1145\/321958.321976","volume":"23","author":"A Yao","year":"1976","unstructured":"Yao, A., Yao, F.F.: Lower bounds on merging networks. J. ACM 23(3), 566\u2013571 (1976)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-75242-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T04:46:21Z","timestamp":1724993181000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-75242-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030752415","9783030752422"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-75242-2_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"4 May 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 May 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 May 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/easyconferences.eu\/ciac2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"78","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"27","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the Corona pandemic the conference was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}