Yuhao Li

collaborators

Showing cs.CCShow all

4 papers · 1 filter

cs.CC2026

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points

Xi Chen, Yuhao Li, Mihalis Yannakakis

We give an $O (lo g^{2} n)$ -query algorithm for finding a Tarski fixed point over the $4$ -dimensional lattice $[n]^{4}$ , matching the $I^c ◯ (lo g^{2} n)$ lower bound of [EPRY20]. Additionall…

cs.CC2026

Quadratic Speedup for Computing Contraction Fixed Points

Xi Chen, Yuhao Li, Mihalis Yannakakis

We study the problem of finding an $I^µ$ -fixed point of a contraction map $f : [0, 1]^{k} \mapsto [0, 1]^{k}$ under both the $ℓ_{\infty}$ -norm and the $ℓ_{1}$ -norm. For both norms, we give…

cs.CC2025

Relative-error monotonicity testing

Xi Chen, Anindya De, Yizhi Huang +4

The standard model of Boolean function property testing is not well suited for testing $sparse$ functions which have few satisfying assignments, since every such function…

cs.CC2025

Computing a Fixed Point of Contraction Maps in Polynomial Queries

Xi Chen, Yuhao Li, Mihalis Yannakakis

We give an algorithm for finding an $I^µ$ -fixed point of a contraction map $f : [0, 1]^{k} \mapsto [0, 1]^{k}$ under the $ℓ_{\infty}$ -norm with query complexity $O (k lo g (1/ I^µ))$ .