{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T09:49:14Z","timestamp":1745488154953,"version":"3.37.0"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/X039862\/1"],"award-info":[{"award-number":["EP\/X039862\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/W014750\/1"],"award-info":[{"award-number":["EP\/W014750\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"name":"University of Munich"},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,2,28]]},"DOI":"10.1137\/22m1536613","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T09:40:16Z","timestamp":1739266816000},"page":"163-192","source":"Crossref","is-referenced-by-count":1,"title":["Constant Inapproximability for PPA"],"prefix":"10.1137","volume":"54","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6513-6748","authenticated-orcid":true,"given":"Argyrios","family":"Deligkas","sequence":"first","affiliation":[{"name":"Royal Holloway, Egham TW20 0EX, UK."}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0791-4342","authenticated-orcid":true,"given":"John","family":"Fearnley","sequence":"additional","affiliation":[{"name":"University of Liverpool, Liverpool L69 7ZX, UK."}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5255-9349","authenticated-orcid":true,"given":"Alexandros","family":"Hollender","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford OX1 4AL, UK."}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9867-6257","authenticated-orcid":true,"given":"Themistoklis","family":"Melissourgos","sequence":"additional","affiliation":[{"name":"University of Essex, Colchester CO4 3SQ, UK."}]}],"member":"351","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44479-6_2"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.09.002"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.37236\/7079"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(87)90055-7"},{"key":"ref5","first-page":"14","author":"Alon N.","year":"2021","journal-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP)"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1986-0861764-9"},{"key":"ref8","first-page":"24","author":"Batziou E.","year":"2021","journal-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP)"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-020-1980-5"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/3678166"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i5.20426"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.10.006"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.11.002"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2022.103784"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/080720826"},{"key":"ref19","first-page":"24","author":"Filos-Ratsikas A.","year":"2018","journal-title":"Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS)"},{"key":"ref20","first-page":"51","author":"Filos-Ratsikas A.","year":"2018","journal-title":"Proceedings of the 50th ACM Symposium on Theory of Computing (STOC)"},{"key":"ref21","first-page":"638","author":"Filos-Ratsikas A.","year":"2019","journal-title":"Proceedings of the 51st ACM Symposium on Theory of Computing (STOC)"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/20M1312678"},{"key":"ref23","first-page":"2615","author":"Filos-Ratsikas A.","year":"2021","journal-title":"Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA)"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/20M1387493"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/0606010"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1249"},{"key":"ref27","first-page":"4","author":"Haviv I.","year":"2021","journal-title":"Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS)"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-022-00233-6"},{"key":"ref29","first-page":"665","volume":"16","author":"Hobby C. R.","year":"1965","journal-title":"Proc. Amer. Math. Soc."},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.06.016"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004119000380"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-016-1303-z"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1137\/15M1039274"},{"key":"ref36","first-page":"4","volume":"1","author":"Schnider P.","year":"2022","journal-title":"Comput. Geom. Topol."},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1016\/S0165-4896(02)00087-2"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T09:40:25Z","timestamp":1739266825000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1536613"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,11]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,28]]}},"alternative-id":["10.1137\/22M1536613"],"URL":"https:\/\/doi.org\/10.1137\/22m1536613","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,11]]}}}