{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T18:21:15Z","timestamp":1758478875347,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["389-22"],"award-info":[{"award-number":["389-22"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018687"],"award-info":[{"award-number":["2018687"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585132","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"581-594","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["The Randomized \ud835\udc58-Server Conjecture Is False!"],"prefix":"10.1145","author":[{"given":"S\u00e9bastien","family":"Bubeck","sequence":"first","affiliation":[{"name":"Microsoft Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Coester","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Rabani","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"323","volume-title":"Proc.of the 52nd Ann. IEEE Symp. on Foundations of Computer Science","author":"Andoni A.","year":"2011","unstructured":"A. Andoni , M. S. Charikar , O. Neiman , and H. L. Nguyen . Near linear lower bound for dimension reduction in \u2113_1 . In Proc.of the 52nd Ann. IEEE Symp. on Foundations of Computer Science , pages 315\u2013 323 , 2011 . A. Andoni, M. S. Charikar, O. Neiman, and H. L. Nguyen. Near linear lower bound for dimension reduction in \u2113_1. In Proc.of the 52nd Ann. IEEE Symp. on Foundations of Computer Science, pages 315\u2013323, 2011."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366885"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.63"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.43"},{"key":"e_1_3_2_1_5_1","first-page":"55","volume-title":"Proc. of the 21st Ann. ACM-SIAM Symp. on Discrete Algorithms","author":"Bansal N.","year":"2010","unstructured":"N. Bansal , N. Buchbinder , and J. Naor . Towards the randomized k-server conjecture: A primal-dual approach . In Proc. of the 21st Ann. ACM-SIAM Symp. on Discrete Algorithms , pages 40\u2013 55 , 2010 . N. Bansal, N. Buchbinder, and J. Naor. Towards the randomized k-server conjecture: A primal-dual approach. In Proc. of the 21st Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 40\u201355, 2010."},{"key":"e_1_3_2_1_6_1","first-page":"13","volume-title":"Proc. of the 30th Ann. European Symp. on Algorithms","author":"Bansal N.","year":"2022","unstructured":"N. Bansal and C. Coester . Online metric allocation and time-varying regularization . In Proc. of the 30th Ann. European Symp. on Algorithms , pages 13:1\u201313: 13 , 2022 . N. Bansal and C. Coester. Online metric allocation and time-varying regularization. In Proc. of the 30th Ann. European Symp. on Algorithms, pages 13:1\u201313:13, 2022."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258667"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959914"},{"key":"e_1_3_2_1_9_1","first-page":"50","volume-title":"Proc. of the 24th Ann. ACM Symp. on Theory of Computing","author":"Bartal Y.","year":"1992","unstructured":"Y. Bartal , A. Fiat , and Y. Rabani . Competitive algorithms for distributed data management . In Proc. of the 24th Ann. ACM Symp. on Theory of Computing , pages 39\u2013 50 , 1992 . Y. Bartal, A. Fiat, and Y. Rabani. Competitive algorithms for distributed data management. In Proc. of the 24th Ann. ACM Symp. on Theory of Computing, pages 39\u201350, 1992."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780610"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00305-X"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384306"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267772"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28435"},{"key":"e_1_3_2_1_15_1","first-page":"523","volume-title":"Proc. of the 44th Ann. IEEE Symp. on Foundations of Computer Science","author":"Brinkman B.","year":"2003","unstructured":"B. Brinkman and M. Charikar . On the impossibility of dimension reduction in l_1 . In Proc. of the 44th Ann. IEEE Symp. on Foundations of Computer Science , pages 514\u2013 523 , 2003 . B. Brinkman and M. Charikar. On the impossibility of dimension reduction in l_1. In Proc. of the 44th Ann. IEEE Symp. on Foundations of Computer Science, pages 514\u2013523, 2003."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00036"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.6"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188798"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404017"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220008"},{"key":"e_1_3_2_1_21_1","volume-title":"Personal communication","author":"Coester C.","year":"2022","unstructured":"C. Coester . Personal communication , 2022 . C. Coester. Personal communication, 2022."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316370"},{"key":"e_1_3_2_1_23_1","first-page":"20","volume-title":"Proc. of the 48th Int\u2019l Colloq. on Automata, Languages, and Programming","author":"Coester C.","year":"2021","unstructured":"C. Coester and E. Koutsoupias . Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle . In Proc. of the 48th Int\u2019l Colloq. on Automata, Languages, and Programming , pages 57:1\u201357: 20 , 2021 . C. Coester and E. Koutsoupias. Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle. In Proc. of the 48th Int\u2019l Colloq. on Automata, Languages, and Programming, pages 57:1\u201357:20, 2021."},{"key":"e_1_3_2_1_24_1","first-page":"848","volume-title":"Proc. of the 32nd Conf. on Learning Theory","author":"Coester C.","year":"2019","unstructured":"C. Coester and J. R. Lee . Pure entropic regularization for metrical task systems . In Proc. of the 32nd Conf. on Learning Theory , pages 835\u2013 848 , 2019 . C. Coester and J. R. Lee. Pure entropic regularization for metrical task systems. In Proc. of the 32nd Conf. on Learning Theory, pages 835\u2013848, 2019."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185381"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335408"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89566"},{"key":"e_1_3_2_1_30_1","volume-title":"Deterministic 3-server on a circle and the limitation of canonical potentials","author":"Huang Z.","year":"2022","unstructured":"Z. Huang and H. Zhang . Deterministic 3-server on a circle and the limitation of canonical potentials , 2022 . Z. Huang and H. Zhang. Deterministic 3-server on a circle and the limitation of canonical potentials, 2022."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1108007"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404033"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60220-8_59"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189993"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103450"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2009.04.002"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195245"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00010-5"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00049"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-004-0473-8"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62243"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_18"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513412"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0035787"},{"key":"e_1_3_2_1_46_1","first-page":"421","volume-title":"Proc. of the 4th Ann. ACM-SIAM Symp. on Discrete Algorithms","author":"Ramesh H.","year":"1993","unstructured":"H. Ramesh . On traversing layered graphs on-line . In Proc. of the 4th Ann. ACM-SIAM Symp. on Discrete Algorithms , pages 412\u2013 421 , 1993 . H. Ramesh. On traversing layered graphs on-line. In Proc. of the 4th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 412\u2013421, 1993."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2744"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44676-1_7"},{"key":"e_1_3_2_1_49_1","volume-title":"Proc. of the 16th Ann. ACM Symp. on Theory of Computing","author":"Sleator D. D.","year":"1984","unstructured":"D. D. Sleator and R. E. Tarjan . Amortized efficiency of list update and paging rules . In Proc. of the 16th Ann. ACM Symp. on Theory of Computing , 1984 . D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. In Proc. of the 16th Ann. ACM Symp. on Theory of Computing, 1984."}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585132","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585132","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585132"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":48,"alternative-id":["10.1145\/3564246.3585132","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585132","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}