Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Yuhao Li:

TR23-073 | 15th May 2023
Xi Chen, Yuhao Li, Mihalis Yannakakis

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

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 ... more >>>

ISSN 1433-8092 | Imprint