All reports by Author Yuhao Li:

__
TR24-057
| 28th March 2024
__

Xi Chen, Yuhao Li, Mihalis Yannakakis#### Computing a Fixed Point of Contraction Maps in Polynomial Queries

__
TR23-073
| 15th May 2023
__

Xi Chen, Yuhao Li, Mihalis Yannakakis#### Reducing Tarski to Unique Tarski (in the Black-box Model)

Xi Chen, Yuhao Li, Mihalis Yannakakis

We give an algorithm for finding an $\epsilon$-fixed point of a contraction map $f:[0,1]^k\rightarrow [0,1]^k$ under the $\ell_\infty$-norm with query complexity $O (k^2\log (1/\epsilon ) )$.

more >>>Xi Chen, Yuhao Li, Mihalis Yannakakis

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