论文标题
改进的上限用于查找Tarski固定点
Improved Upper Bounds for Finding Tarski Fixed Points
论文作者
论文摘要
我们研究了在$ k $二维网格$ \ {1，\ ldots，n \}^k $上找到tarski固定点的查询复杂性。改进$ \ smash {o（\ log^{\ lceil 2k/3 \ rceil} n）} $ [fps20]的先前最佳上限，我们给出了一个新算法，具有查询复杂性$ \ smash {o（\ log log^{\ log^{\ lceil（k+1）/2）/2）/2 \ rceil} $} $这是基于关于塔斯基固定点问题较弱的变化的新颖分解定理，其中输入由单调函数$ f：[n]^k \ rightArow [n]^k $和单调符号函数$ b：[n]^k \ rightArrow \ rightArrow \ rightArrow \ rightAROW \ rightAROW \ right { - 1,1,0,1 $ $ k $ n $ n $ n $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x^in [ $ f（x）\ prepeq x $和$ b（x）\ le 0 $ $或$ $ f（x）\ succeq x $和$ b（x）\ ge 0 $。
We study the query complexity of finding a Tarski fixed point over the $k$-dimensional grid $\{1,\ldots,n\}^k$. Improving on the previous best upper bound of $\smash{O(\log^{\lceil 2k/3\rceil} n)}$ [FPS20], we give a new algorithm with query complexity $\smash{O(\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\rightarrow [n]^k$ and a monotone sign function $b:[n]^k\rightarrow \{-1,0,1\}$ and the goal is to find an $x\in [n]^k$ that satisfies $either$ $f(x)\preceq x$ and $b(x)\le 0$ $or$ $f(x)\succeq x$ and $b(x)\ge 0$.
