Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR23-073 | 15th May 2023 21:15

Reducing Tarski to Unique Tarski (in the Black-box Model)

RSS-Feed




TR23-073
Authors: Xi Chen, Yuhao Li, Mihalis Yannakakis
Publication: 21st May 2023 05:59
Downloads: 482
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint