License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.29
URN: urn:nbn:de:0030-drops-136741
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13674/
Go to the corresponding LIPIcs Volume Portal

Fearnley, John ; Savani, Rahul

A Faster Algorithm for Finding Tarski Fixed Points

pdf-format:
LIPIcs-STACS-2021-29.pdf (0.8 MB)

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 [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.

BibTeX - Entry

@InProceedings{fearnley_et_al:LIPIcs.STACS.2021.29,
  author =	{Fearnley, John and Savani, Rahul},
  title =	{{A Faster Algorithm for Finding Tarski Fixed Points}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13674},
  URN =		{urn:nbn:de:0030-drops-136741},
  doi =		{10.4230/LIPIcs.STACS.2021.29},
  annote =	{Keywords: query complexity, Tarski fixed points, total function problem}
}

Keywords: query complexity, Tarski fixed points, total function problem
Collection: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Issue Date: 2021
Date of publication: 10.03.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI