Improved Upper Bounds for Finding Tarski Fixed Points
Improved Upper Bounds for Finding Tarski Fixed Points
复制标题
改进了查找 Tarski 不动点的上限
DOI：
10.1145/3490486.3538297
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Li, Yuhao
中科院分区：
文献类型：
--
作者：
Chen, Xi;Li, Yuhao
研究了在k维格网{1，...，n}k上寻找Tarski不动点的查询复杂性，改进了已有的O(LOG⌈2k/3⌉n)[7]的最佳上界，给出了一个查询复杂度为O(LOG⌈(k+1)/2⌉n)的新算法.这是基于关于Tarski不动点问题的一个较弱变量的一个新的分解定理，其中输入由一个单调函数f：[n]k→[n]k和一个单调符号函数b：[n]k→{-1，0，1}组成，目标是找到满足f(X)∈x和b(X)≼0或f(X)≤x和b(X)≽0的点x≥[n]k。
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 O(log⌈2k/3⌉n)[7], we give a new algorithm with query complexity O(log⌈(k+1)/2⌉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 a point x ∈ [n]k that satisfies either f(x) ≼ x and b(x) ≤ 0 or f(x) ≽ x and b(x) ≥ 0.
登录
查看更多内容
塔斯基定理、超模博弈和均衡的复杂性
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
梯度下降的复杂度：CLS = PPAD ∩ PLS
DOI：
10.1145/3406325.3451052
发表时间：
2020
期刊：
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
John Fearnley;P. Goldberg;Alexandros Hollender;Rahul Savani
通讯作者：
Rahul Savani
TFNP进一步崩溃
DOI：
--
发表时间：
2022
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Mika Goos;Alexandros Hollender;Siddhartha Jain;Gilbert Maystre;William Pires;Robert Robere;Ran Tao
通讯作者：
Ran Tao
一种更快的找到 Tarski 不动点的算法
DOI：
10.1145/3524044
发表时间：
2020
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
John Fearnley;Rahul Savani
通讯作者：
Rahul Savani