文章基本信息

标题：A Faster Algorithm for Finding Tarski Fixed Points
本地全文：下载
作者：John Fearnley ; Savani, Rahul
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：187
页码：29:1-29:16
DOI：10.4230/LIPIcs.STACS.2021.29
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 [Chuangyin Dang et al., 2020]. Multiple authors have conjectured that this algorithm is optimal [Chuangyin Dang et al., 2020; Kousha Etessami et al., 2020], and indeed this has been proven for two-dimensional instances [Kousha Etessami et al., 2020]. We show that these conjectures are false in dimension three or higher by giving an O(logÂ² n) query algorithm for the three-dimensional Tarski problem, which generalises to give an O(log^{k-1} n) query algorithm for the k-dimensional problem when k â¥ 3.
关键词：query complexity; Tarski fixed points; total function problem