2022/02/11 by Chen, Xi, Li, Yuhao · 1 citation
#Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2202.05913
We study the query complexity of finding a Tarski fixed point over the k-dimensional grid \1,…,n\k. Improving on the previous best upper bound of \smashO(log\lceil 2k/3\rceil n) [FPS20], we give a new algorithm with query complexity \smashO(log\lceil (k+1)/2\rceil n). This is based on a novel decomposition theorem about a weaker variant of the Tarski fixed point problem, where the input consists of a monotone function f:[n]k→ [n]k and a monotone sign function b:[n]k→ \-1,0,1\ and the goal is to find an x∈ [n]k that satisfies either f(x)\preceq x and b(x)≤ 0 or f(x)\succeq x and b(x)≥ 0.