2025/02/23 by Brânzei, Simina, Phillips, Reed, Recker, Nicholas · 1 citation
#Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2502.16679
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 Ω( \frack ⋅ log2nlogk ) for all n,k ≥ 2. This unifies and improves upon two prior results: a lower bound of Ω(log2n) from [EPRY 2019] and a lower bound of Ω( \frack ⋅ lognlogk) from [BPR 2024], respectively.