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.
|
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(\log^{k} n)$ queries. Multiple authors have conjectured that this algorithm is optimal [Dang et al., Etessami et al.], and indeed this has been proven for two-dimensional instances [Etessami et al.]. 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 \lceil k/3 \rceil} 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: | 14 Oct 2020 10:19 |
| Last Modified: | 26 Jan 2023 01:41 |
| DOI: | 10.4230/LIPIcs.STACS.2021.29 |
| Open Access URL: | https://drops.dagstuhl.de/opus/volltexte/2021/1367... |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3104190 |
Dimensions
Dimensions
