A Faster Algorithm for Finding Tarski Fixed Points

Fearnley, John and Savani, Rahul ORCID: 0000-0003-1262-7831 (2021) A Faster Algorithm for Finding Tarski Fixed Points 38TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2021), 187. ISSN 1868-8969

Access the full-text of this item by clicking on the Open Access link.

Text 2010.02618v1.pdf - Submitted version Download (604kB) | 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(logk 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, which generalises to give an O(logk-1 n) query algorithm for the k-dimensional problem when k ≥ 3.

Item Type:	Article
Uncontrolled Keywords:	query complexity, Tarski fixed points, total function problem
Depositing User:	Symplectic Admin
Date Deposited:	14 Oct 2020 10:19
Last Modified:	23 May 2026 05:10
DOI:	10.4230/LIPIcs.STACS.2021.29
Open Access URL:	https://drops.dagstuhl.de/opus/volltexte/2021/1367...
Related Websites:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3104190
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.