Xi Chen

collaborators

Showing cs.CCShow all

2 papers · 1 filter

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

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^µ))$ .