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 ≤ relation. In this setting, there is an unknown monotone function f: {0,1,…, n-1}^k → {0,1,…, 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 Ω((k⋅log²n)/log k) for all n,k ≥ 2. This unifies and improves upon two prior results: a lower bound of Ω(log²n) from [Etessami et al., 2020] and a lower bound of Ω((k⋅log(n)/log(k)) from [Brânzei et al., 2024], respectively.

Local search is a powerful heuristic in optimization and computer science, the complexity of which has been studied in the white box and black box models. In the black box model, we are given a graph G = (V, E) and oracle access to a function f : V → ℝ. The local search problem is to find a vertex v that is a local minimum, i.e. with f(v) ≤ f (u) for all (u, v) ∈ E, using as few queries to the oracle as possible. The query complexity is well understood on the grid and the hypercube, but much less is known beyond.