Computing a Fixed Point of Contraction Maps in Polynomial Queries

We give an algorithm for finding an ε-fixed point of a contraction map f : [0, 1] k → [0, 1] k under the ℓ ∞ -norm with query complexity O(k log(1/ε)).