2024/09/05 by Brânzei, Simina, Phillips, Reed, Recker, Nicholas
#Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2409.03751
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 ≤ relation. Specifically, 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). A key special case of interest is the Boolean hypercube \0,1\k, which is isomorphic to the power set lattice--the original setting of the Knaster-Tarski theorem. We prove a lower bound that characterizes the randomized and deterministic query complexity of the Tarski search problem on the Boolean hypercube as Θ(k). More generally, we give a randomized lower bound of Ω( k + \frack lognlogk ) for the k-dimensional grid of side length n, which is asymptotically optimal in high dimensions when k is large relative to n.