A Faster Algorithm for Finding Tarski Fixed Points

Fearnley, John, Palvolgyi, Domotor 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 note.pdf - Author Accepted Manuscript Download (650kB) | 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(log2 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(log2 [k/3]permil; n) query algorithm for the k-dimensional problem.

Item Type:	Article
Uncontrolled Keywords:	Query complexity, Tarski fixed points, total function problem
Depositing User:	Symplectic Admin
Date Deposited:	18 Jan 2021 09:40
Last Modified:	22 May 2026 16:17
DOI:	10.1145/3524044
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3113755
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.