{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,22]],"date-time":"2026-02-22T10:44:10Z","timestamp":1771757050902,"version":"3.50.1"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,7,31]],"date-time":"2022-07-31T00:00:00Z","timestamp":1659225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,7,31]]},"abstract":"<jats:p>\n            Dang et\u00a0al. have given an algorithm that can find a Tarski fixed point in a\n            <jats:italic>k<\/jats:italic>\n            -dimensional lattice of width\n            <jats:italic>n<\/jats:italic>\n            using\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) queries\u00a0[\n            <jats:xref ref-type=\"bibr\">2<\/jats:xref>\n            ]. Multiple authors have conjectured that this algorithm is optimal\u00a0[\n            <jats:xref ref-type=\"bibr\">2<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">7<\/jats:xref>\n            ], and indeed this has been proven for two-dimensional instances\u00a0[\n            <jats:xref ref-type=\"bibr\">7<\/jats:xref>\n            ]. We show that these conjectures are false in dimension three or higher by giving an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) query algorithm for the three-dimensional Tarski problem. We also give a new decomposition theorem for\n            <jats:italic>k<\/jats:italic>\n            -dimensional Tarski problems which, in combination with our new algorithm for three dimensions, gives an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            \u2308k\/3\u2309\n            <jats:italic>n<\/jats:italic>\n            ) query algorithm for the\n            <jats:italic>k<\/jats:italic>\n            -dimensional problem.\n          <\/jats:p>","DOI":"10.1145\/3524044","type":"journal-article","created":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T13:36:20Z","timestamp":1647524180000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A Faster Algorithm\u00a0for Finding Tarski Fixed Points"],"prefix":"10.1145","volume":"18","author":[{"given":"John","family":"Fearnley","sequence":"first","affiliation":[{"name":"University of Liverpool, Liverpool, Merseyside, United Kingdom"}]},{"given":"D\u00f6m\u00f6t\u00f6r","family":"P\u00e1lv\u00f6lgyi","sequence":"additional","affiliation":[{"name":"E\u00f6tv\u00f6s Lor\u00e1nd University (ELTE), Hungary"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1262-7831","authenticated-orcid":false,"given":"Rahul","family":"Savani","sequence":"additional","affiliation":[{"name":"University of Liverpool, Liverpool, Merseyside, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2022,10,11]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.05.005"},{"key":"e_1_3_2_3_2","article-title":"Computations and complexities of Tarski\u2019s fixed points and supermodular games","volume":"2005","author":"Dang Chuangyin","year":"2020","unstructured":"Chuangyin Dang, Qi Qi, and Yinyu Ye. 2020. Computations and complexities of Tarski\u2019s fixed points and supermodular games. CoRR abs\/2005.09836 (2020). Stanford Tech Report version appeared in 2012.","journal-title":"CoRR"},{"key":"e_1_3_2_4_2","volume-title":"On the Complexity of a Class of Discrete Fixed Point Problems Under the Lexicographic Ordering","author":"Dang Chuangyin","year":"2018","unstructured":"Chuangyin Dang and Yinyu Ye. 2018. On the Complexity of a Class of Discrete Fixed Point Problems Under the Lexicographic Ordering. Technical Report. City University of Hong Kong, CY2018-3, 17 pages."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.04.021"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.03.014"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2006.06.001"},{"key":"e_1_3_2_8_2","first-page":"18:1\u201318:19","volume-title":"Proc. of ITCS","author":"Etessami Kousha","year":"2020","unstructured":"Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis. 2020. Tarski\u2019s theorem, supermodular games, and the complexity of equilibria. In Proc. of ITCS, Vol. 151. 18:1\u201318:19."},{"key":"e_1_3_2_9_2","volume-title":"Proc. of STOC","author":"Fearnley John","year":"2021","unstructured":"John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani. 2021. The complexity of gradient descent: CLS = PPAD \\( \\cap \\) PLS. In Proc. of STOC. 46\u201359."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.05.007"},{"key":"e_1_3_2_11_2","first-page":"29:1\u201329:16","volume-title":"Proc. of STACS","author":"Fearnley John","year":"2021","unstructured":"John Fearnley and Rahul Savani. 2021. A faster algorithm for finding Tarski fixed points. In Proc. of STACS. 29:1\u201329:16."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.2307\/2938316"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1955.5.285"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0317054"},{"key":"e_1_3_2_15_2","volume-title":"Supermodularity and Complementarity","author":"Topkis Donald M.","year":"1998","unstructured":"Donald M. Topkis. 1998. Supermodularity and Complementarity. Princeton University Press."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3524044","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3524044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:37Z","timestamp":1750188637000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3524044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,31]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7,31]]}},"alternative-id":["10.1145\/3524044"],"URL":"https:\/\/doi.org\/10.1145\/3524044","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,31]]},"assertion":[{"value":"2021-06-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}