A Faster Algorithm for Finding Tarski Fixed Points
A Faster Algorithm for Finding Tarski Fixed Points
复制标题
一种更快的找到 Tarski 不动点的算法
DOI：
10.1145/3524044
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Rahul Savani
中科院分区：
文献类型：
--
作者：
John Fearnley;Rahul Savani
党等人。给出了一种算法，可以使用 O(log k n) 查询在宽度为 n 的 k 维晶格中找到 Tarski 不动点 [2]。多位作者推测该算法是最优的 [2, 7]，并且事实上这已经针对二维实例得到了证明 [7]。我们通过给出三维 Tarski 问题的 O(log2 n) 查询算法来证明这些猜想在三维或更高维度上是错误的。我们还给出了 k 维 Tarski 问题的新分解定理，结合我们的三维新算法，给出了 k 维问题的 O(log2 ⌈k/3⌉ n) 查询算法。
Dang et al. have given an algorithm that can find a Tarski fixed point in a k-dimensional lattice of width n using O(log k n) queries [2]. Multiple authors have conjectured that this algorithm is optimal [2, 7], and indeed this has been proven for two-dimensional instances [7]. We show that these conjectures are false in dimension three or higher by giving an O(log2 n) query algorithm for the three-dimensional Tarski problem. We also give a new decomposition theorem for k-dimensional Tarski problems which, in combination with our new algorithm for three dimensions, gives an O(log2 ⌈k/3⌉ n) query algorithm for the k-dimensional problem.
塔斯基定理、超模博弈和均衡的复杂性
DOI：
10.4230/lipics.itcs.2020.18
发表时间：
2020
期刊：
11th Innovations in Theoretical Computer Science Conference
影响因子：
--
作者：
Etessami, Kousha;Papadimitriou, Christos H;Rubinstein, Aviad;Yannakakis, Mihalis
通讯作者：
Yannakakis, Mihalis
势线的独特末端
影响因子：
--
作者：
Fearnley, John;Gordon, Spencer;Mehta, Ruta;Savani, Rahul
通讯作者：
Savani, Rahul