Reducing Tarski to Unique Tarski (in the Black-box Model)
Reducing Tarski to Unique Tarski (in the Black-box Model)
复制标题
将 Tarski 简化为独特的 Tarski（在黑盒模型中）
DOI：
10.4230/lipics.ccc.2023.21
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
M. Yannakakis
中科院分区：
文献类型：
--
作者：
Xi Chen;Yuhao Li;M. Yannakakis
研究了k维网格[ n ] k上的Tarski不动点问题.我们给出了一个黑盒减少从塔斯基问题到相同的问题与一个额外的承诺，输入函数有一个唯一的不动点。这意味着塔斯基问题和唯一塔斯基问题具有完全相同的查询复杂度。我们的减少是基于一个新的概念的部分信息功能，我们用它来愚弄算法的唯一塔斯基问题，如果他们是工作在一个单调的函数与一个唯一的不动点
We study the problem of finding a Tarski fixed point over the k -dimensional grid [ n ] k . We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique Tarski problem have exactly the same query complexity. Our reduction is based on a novel notion of partial-information functions which we use to fool algorithms for the unique Tarski problem as if they were working on a monotone function with a unique fixed point
塔斯基定理、超模博弈和均衡的复杂性
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
改进了查找 Tarski 不动点的上限
DOI：
10.1145/3490486.3538297
发表时间：
2022
期刊：
Proceedings of the 23rd ACM Conference on Economics and Computation (EC ’22
影响因子：
--
作者：
Chen, Xi;Li, Yuhao
通讯作者：
Li, Yuhao