Computing a Fixed Point of Contraction Maps in Polynomial Queries

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