Randomized Lower Bounds for Tarski Fixed Points in High Dimensions
<|reference_start|>Randomized Lower Bounds for Tarski Fixed Points in High Dimensions: The Knaster-Tarski theorem, also known as Tarski's theorem, guarantees that every monotone function defined on a complete lattice 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 $\leq$ relation. Specifically, there is an unknown monotone function $f: \{0,1,\ldots, n-1\}^k \to \{0,1,\ldots, n-1\}^k$ and an algorithm must query a vertex $v$ to learn $f(v)$.   Our main result is a randomized lower bound of $\Omega\left( k + \frac{k \cdot \log{n}}{\log{k}} \right)$ for the $k$-dimensional grid of side length $n$, which is nearly optimal in high dimensions when $k$ is large relative to $n$. As a corollary, we characterize the randomized and deterministic query complexity on the Boolean hypercube $\{0,1\}^k$ as $\Theta(k)$.<|reference_end|>
@article{brânzei2024randomized,
    title={Randomized Lower Bounds for Tarski Fixed Points in High Dimensions},
    author={Simina Br^anzei and Reed Phillips and Nicholas Recker},
    journal={arXiv preprint arXiv:2409.03751},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.03751},
    primaryClass={cs.CC cs.GT}
}