{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T05:34:56Z","timestamp":1772516096061,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["321171"],"award-info":[{"award-number":["321171"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","award":["200021 165522"],"award-info":[{"award-number":["200021 165522"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316334","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"638-649","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["The complexity of splitting necklaces and bisecting ham sandwiches"],"prefix":"10.1145","author":[{"given":"Aris","family":"Filos-Ratsikas","sequence":"first","affiliation":[{"name":"EPFL, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul W.","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"TR15-163","author":"Aisenberg J.","year":"2015","unstructured":"J. Aisenberg , M.L. Bonet , and S. Buss . 2-D Tucker is PPA complete. Electronic Colloquium on Computational Complexity , TR15-163 ( 2015 ). J. Aisenberg, M.L. Bonet, and S. Buss. 2-D Tucker is PPA complete. Electronic Colloquium on Computational Complexity, TR15-163 (2015)."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(87)90055-7"},{"key":"e_1_3_2_1_3_1","first-page":"12","volume-title":"Some recent Combinatorial Applications of Borsuk-type Theorems","author":"Alon N.","year":"1986","unstructured":"N. Alon . Some recent Combinatorial Applications of Borsuk-type Theorems . London Mathematical Society Lecture Notes Series 131, Algebraic, Extremal and Metric Combinatorics 1986 , pp. 1\u2013 12 . CUP (1988). N. Alon. Some recent Combinatorial Applications of Borsuk-type Theorems. London Mathematical Society Lecture Notes Series 131, Algebraic, Extremal and Metric Combinatorics 1986, pp. 1\u201312. CUP (1988)."},{"key":"e_1_3_2_1_4_1","first-page":"1429","volume-title":"Proceedings of International Congress of Mathematicians","author":"Alon N.","year":"1990","unstructured":"N. Alon . Non-Constructive Proofs in Combinatorics . Proceedings of International Congress of Mathematicians 1990 , pp. 1421\u2013 1429 . Tokyo, Springer-Verlag (1991). N. Alon. Non-Constructive Proofs in Combinatorics. Proceedings of International Congress of Mathematicians 1990, pp. 1421\u20131429. Tokyo, Springer-Verlag (1991)."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1986-0861764-9"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1575"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3135595.3135625"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802179"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms.12109"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1144327.1705286"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.29"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.052"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746571"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064810"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.007"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_3_2_1_18_1","first-page":"25","volume-title":"Understanding PPAcompleteness. 31st Conference on Computational Complexity, article no. 23","author":"Deng X.","year":"2016","unstructured":"X. Deng , J.R. Edmonds , Z. Feng , Z. Liu , Q. Qi , and Z. Xu . Understanding PPAcompleteness. 31st Conference on Computational Complexity, article no. 23 , pp. 23: 1\u201323: 25 ( 2016 ). X. Deng, J.R. Edmonds, Z. Feng, Z. Liu, Q. Qi, and Z. Xu. Understanding PPAcompleteness. 31st Conference on Computational Complexity, article no. 23, pp. 23:1\u201323:25 (2016)."},{"key":"e_1_3_2_1_20_1","volume-title":"On the Complexity of Envy-Free Cake Cutting. CoRR, arXiv:0907.1334","author":"Deng X.","year":"2009","unstructured":"X. Deng , Q. Qi , and A. Saberi . On the Complexity of Envy-Free Cake Cutting. CoRR, arXiv:0907.1334 ( 2009 ). X. Deng, Q. Qi, and A. Saberi. On the Complexity of Envy-Free Cake Cutting. CoRR, arXiv:0907.1334 (2009)."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(86)80020-7"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134719"},{"key":"e_1_3_2_1_23_1","first-page":"16","volume-title":"Hardness Results for Consensus-Halving. Proceedings of the 43rd MFCS Symposium (MFCS 2018","author":"Filos-Ratsikas A.","year":"2018","unstructured":"A. Filos-Ratsikas , S. K. S. Frederiksen , P.W. Goldberg , and J. Zhang . Hardness Results for Consensus-Halving. Proceedings of the 43rd MFCS Symposium (MFCS 2018 ), pp. 24:1\u201324: 16 ( 2018 ). A. Filos-Ratsikas, S. K. S. Frederiksen, P.W. Goldberg, and J. Zhang. Hardness Results for Consensus-Halving. Proceedings of the 43rd MFCS Symposium (MFCS 2018), pp. 24:1\u201324:16 (2018)."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188880"},{"key":"e_1_3_2_1_25_1","volume-title":"The Complexity of Splitting Neckclaces and Bisecting Ham Sandwiches. Full Version, arXiv preprint arXiv:1805.12559","author":"Filos-Ratsikas A.","year":"2019","unstructured":"A. Filos-Ratsikas and P.W. Goldberg . The Complexity of Splitting Neckclaces and Bisecting Ham Sandwiches. Full Version, arXiv preprint arXiv:1805.12559 ( 2019 ). A. Filos-Ratsikas and P.W. Goldberg. The Complexity of Splitting Neckclaces and Bisecting Ham Sandwiches. Full Version, arXiv preprint arXiv:1805.12559 (2019)."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.12.003"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0606010"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0703-7"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00152-6"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1983.11971254"},{"key":"e_1_3_2_1_31_1","first-page":"670","volume-title":"Proceedings of the American Mathematical Society 16(4)","author":"Hobby C.R.","year":"1965","unstructured":"C.R. Hobby and J.R. Rice , A Moment Problem in L 1 Approximation . Proceedings of the American Mathematical Society 16(4) pp.665\u2013 670 ( 1965 ). C.R. Hobby and J.R. Rice, A Moment Problem in L 1 Approximation. Proceedings of the American Mathematical Society 16(4) pp.665\u2013670 (1965)."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.08.001"},{"key":"e_1_3_2_1_33_1","first-page":"15","volume-title":"Symposium on Computational Geometry","author":"Karthik C.S.","year":"2017","unstructured":"C.S. Karthik and A. Saha . Ham Sandwich is Equivalent to Borsuk-Ulam . Symposium on Computational Geometry pp. 24:1\u201324: 15 ( 2017 ). C.S. Karthik and A. Saha. Ham Sandwich is Equivalent to Borsuk-Ulam. Symposium on Computational Geometry pp. 24:1\u201324:15 (2017)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/120874655"},{"key":"e_1_3_2_1_35_1","first-page":"660","volume-title":"Proceedings of STACS","author":"Knauer C.","year":"2011","unstructured":"C. Knauer , H.R. Tiwary , D. Werner . On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems . Proceedings of STACS pp. 649\u2013 660 ( 2011 ). C. Knauer, H.R. Tiwary, D. Werner. On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems. Proceedings of STACS pp. 649\u2013660 (2011)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129765"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116647.2830453"},{"key":"e_1_3_2_1_38_1","volume-title":"Helly, Sperner, Tucker, and Tverberg. CoRR, arXiv:1706.05975","author":"De Loera J.A.","year":"2017","unstructured":"J.A. De Loera , X. Goaoc , F. Meunier , and N. Mustafa . The discrete yet ubiquitous theorems of Carath\u00e9odory , Helly, Sperner, Tucker, and Tverberg. CoRR, arXiv:1706.05975 ( 2017 ). J.A. De Loera, X. Goaoc, F. Meunier, and N. Mustafa. The discrete yet ubiquitous theorems of Carath\u00e9odory, Helly, Sperner, Tucker, and Tverberg. CoRR, arXiv:1706.05975 (2017)."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2005.08.002"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/197405.197408"},{"key":"e_1_3_2_1_41_1","volume-title":"Lectures on discrete geometry","year":"2002","unstructured":"Matou\u0161ek, Ji\u0159\u00ed. Lectures on discrete geometry . Vol. 212 . New York : Springer , 2002 . Matou\u0161ek, Ji\u0159\u00ed. Lectures on discrete geometry. Vol. 212. New York: Springer, 2002."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0311"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2012.01.014"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.06.017"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2014.01.008"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591835"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/2715092.2715148"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746578"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.35"},{"key":"e_1_3_2_1_52_1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science (ITCS) Conference","author":"Schuldenzucker S.","year":"2017","unstructured":"S. Schuldenzucker , S. Seuken , and S. Battiston . Finding clearing payments in financial networks with credit default swaps is PPAD-complete . Proceedings of the 8th Innovations in Theoretical Computer Science (ITCS) Conference , Berkeley, USA , ( 2017 ). S. Schuldenzucker, S. Seuken, and S. Battiston. Finding clearing payments in financial networks with credit default swaps is PPAD-complete. Proceedings of the 8th Innovations in Theoretical Computer Science (ITCS) Conference, Berkeley, USA, (2017)."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0165-4896(02)00087-2"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-42-00925-6"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970394"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316334","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":54,"alternative-id":["10.1145\/3313276.3316334","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316334","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}