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. ISSN 1549-6325, 1549-6333

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

Abstract

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

Item Type:	Article
Divisions:	Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	07 Mar 2022 08:48
Last Modified:	06 Dec 2024 20:55
DOI:	10.1145/3524044
Related Websites:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3150185
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.