{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T22:05:26Z","timestamp":1768687526579,"version":"3.49.0"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T00:00:00Z","timestamp":1575331200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T00:00:00Z","timestamp":1575331200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021 165524"],"award-info":[{"award-number":["200021 165524"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00224-019-09957-5","type":"journal-article","created":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T00:14:02Z","timestamp":1575332042000},"page":"508-521","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Optimal Dislocation with Persistent Errors in Subquadratic Time"],"prefix":"10.1007","volume":"64","author":[{"given":"Barbara","family":"Geissmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leucci","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chih-Hung","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5959-2421","authenticated-orcid":false,"given":"Paolo","family":"Penna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,3]]},"reference":[{"issue":"2","key":"9957_CR1","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/2701427","volume":"12","author":"M Ajtai","year":"2016","unstructured":"Ajtai, M., Feldman, V., Hassidim, A., Nelson, J.: Sorting and selection with imprecise comparisons. ACM Transactions on Algorithms 12(2), 19 (2016)","journal-title":"ACM Transactions on Algorithms"},{"issue":"4-5","key":"9957_CR2","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1017\/S0963548304006297","volume":"13","author":"L Alonso","year":"2004","unstructured":"Alonso, L., Chassaing, P., Gillet, F., Janson, S., Reingold, E.M., Schott, R.: Quicksort with unreliable comparisons: a probabilistic analysis. Comb. Probab. Comput. 13(4-5), 419\u2013449 (2004)","journal-title":"Comb. Probab. Comput."},{"key":"9957_CR3","unstructured":"Braverman, M., Mossel, E.: Noisy sorting without Resampling. In: Proceedings of the 19th annual symposium on discrete algorithms, pp. 268\u2013276 (2008)"},{"issue":"3","key":"9957_CR4","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0012-365X(79)90084-0","volume":"25","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: The tail of the hypergeometric distribution. Discret. Math. 25 (3), 285\u2013287 (1979)","journal-title":"Discret. Math."},{"key":"9957_CR5","doi-asserted-by":"crossref","unstructured":"Cicalese, F.: Fault-tolerant search algorithms - reliable computation with unreliable information. Monographs in Theoretical Computer Science. An EATCS Series Springer (2013)","DOI":"10.1007\/978-3-642-17327-1"},{"issue":"3","key":"9957_CR6","doi-asserted-by":"publisher","first-page":"55:1","DOI":"10.1145\/1798596.1798608","volume":"6","author":"D Coppersmith","year":"2010","unstructured":"Coppersmith, D., Fleischer, L.K., Rurda, A.: Ordering by weighted number of wins gives a good ranking for weighted tournaments. ACM Trans. Algorithms 6 (3), 55:1\u201355:13 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"9957_CR7","doi-asserted-by":"crossref","unstructured":"Damaschke, Peter: The solution space of sorting with recurring comparison faults. In: Combinatorial algorithms - 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016. Proceedings, pp. 397\u2013408 (2016)","DOI":"10.1007\/978-3-319-44543-4_31"},{"issue":"5","key":"9957_CR8","doi-asserted-by":"publisher","first-page":"1001","DOI":"10.1137\/S0097539791195877","volume":"23","author":"U Feige","year":"1994","unstructured":"Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput. 23(5), 1001\u20131018 (1994)","journal-title":"SIAM J. Comput."},{"key":"9957_CR9","unstructured":"Gavenciak, T., Geissmann, B., Lengler, J: Sorting by swaps with noisy comparisons. In: Proceedings of the genetic and evolutionary computation conference, GECCO Berlin, Germany, July 15-19, 2017, pp. 1375\u20131382, 2017 (2017)"},{"key":"9957_CR10","unstructured":"Geissmann, B., Leucci, S., Liu, C.-H., Penna, P.: Sorting with recurrent comparison errors. In: ISAAC, vol. 92 of LIPIcs, pp. 38:1\u201338:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"},{"key":"9957_CR11","doi-asserted-by":"publisher","first-page":"052108","DOI":"10.1103\/PhysRevE.97.052108","volume":"97","author":"B Geissmann","year":"2018","unstructured":"Geissmann, B., Penna, P.: Sorting processes with energy-constrained comparisons. Phys. Rev. E 97, 052108 (2018)","journal-title":"Phys. Rev. E"},{"issue":"14","key":"9957_CR12","doi-asserted-by":"publisher","first-page":"1398","DOI":"10.1016\/j.dam.2011.05.010","volume":"159","author":"P Hadjicostas","year":"2011","unstructured":"Hadjicostas, P., Lakshmanan, K.B.: Recursive merge sort with erroneous comparisons. Discret. Appl. Math. 159(14), 1398\u20131417 (2011)","journal-title":"Discret. Appl. Math."},{"key":"9957_CR13","doi-asserted-by":"crossref","unstructured":"Klein, R., Penninger, R., Sohler, C., Woodruff, D.P.: Tolerant algorithms. In: ESA, volume 6942 of lecture notes in computer science, pp. 736\u2013747. Springer (2011)","DOI":"10.1007\/978-3-642-23719-5_62"},{"issue":"1-2","key":"9957_CR14","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0304-3975(01)00303-6","volume":"270","author":"A Pelc","year":"2002","unstructured":"Pelc, A.: Searching games with errors - fifty years of coping with liars. Theor. Comput. Sci. 270(1-2), 71\u2013109 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9957_CR15","unstructured":"Rubinstein, A., Vardi, S.: Sorting from noisier samples. In: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA Barcelona, Spain, Hotel Porta Fira January 16-19, pp. 960\u2013972, 2017 (2017)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09957-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09957-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09957-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,1]],"date-time":"2020-12-01T19:10:38Z","timestamp":1606849838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09957-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,3]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["9957"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09957-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,3]]},"assertion":[{"value":"3 December 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}