Tarski Lower Bounds from Multi-Dimensional Herringbones

Abstract

Tarski's theorem states that every monotone function from a complete lattice to itself has a fixed point. We analyze the query complexity of finding such a fixed point on the $k$-dimensional grid of side length $n$ under the $\le$ relation. In this setting, there is an unknown monotone function $f:\{0,1,\dots ,n-1{\}}^k\to \{0,1,\dots ,n-1{\}}^k$ and an algorithm must query a vertex $v$ to learn $f(v)$. The goal is to find a fixed point of $f$ using as few oracle queries as possible. We show that the randomized query complexity of this problem is $\hat{I}\text{c◯}\left(\frac{k\cdot {\log }^{2}n}{\log k}\right)$ for all $n,k\ge 2$. This unifies and improves upon two prior results: a lower bound of $\hat{I}\text{c◯}({\log }^{2}n)$ from [EPRY 2019] and a lower bound of $\hat{I}\text{c◯}\left(\frac{k\cdot \log n}{\log k}\right)$ from [BPR 2024], respectively.

Full version of the published paper. 32 pages, 6 figures