A Faster Algorithm for Finding Tarski Fixed Points

Fearnley, John, Pálvölgyi, Dömötör and Savani, Rahul ORCID: 0000-0003-1262-7831 (2022) A Faster Algorithm for Finding Tarski Fixed Points. ACM Transactions on Algorithms, 18 (3). pp. 1-23.

Text author_accepted_for_elements.pdf - Author Accepted Manuscript Download (822kB) | Preview

Abstract

<jats:p> Dang et al. have given an algorithm that can find a Tarski fixed point in a <jats:italic>k</jats:italic> -dimensional lattice of width <jats:italic>n</jats:italic> using <jats:italic>O</jats:italic> (log <jats:sup> <jats:italic>k</jats:italic> </jats:sup> <jats:italic>n</jats:italic> ) queries [ <jats:xref ref-type="bibr">2</jats:xref> ]. Multiple authors have conjectured that this algorithm is optimal [ <jats:xref ref-type="bibr">2</jats:xref> , <jats:xref ref-type="bibr">7</jats:xref> ], and indeed this has been proven for two-dimensional instances [ <jats:xref ref-type="bibr">7</jats:xref> ]. We show that these conjectures are false in dimension three or higher by giving an <jats:italic>O</jats:italic> (log <jats:sup>2</jats:sup> <jats:italic>n</jats:italic> ) query algorithm for the three-dimensional Tarski problem. We also give a new decomposition theorem for <jats:italic>k</jats:italic> -dimensional Tarski problems which, in combination with our new algorithm for three dimensions, gives an <jats:italic>O</jats:italic> (log <jats:sup>2</jats:sup> ⌈k/3⌉ <jats:italic>n</jats:italic> ) query algorithm for the <jats:italic>k</jats:italic> -dimensional problem. </jats:p>

Item Type:	Article
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	07 Mar 2022 08:48
Last Modified:	18 Jan 2023 21:11
DOI:	10.1145/3524044
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3150185