Query-Efficient Fixpoints of ₚ-Contractions

We prove that an $ε$-approximate fixpoint of a map f:[0,1]ᵈ→ [0,1]ᵈ can be found with O(d²(log1ε + log1/1-λ)) queries to f if f is $λ$-contracting with respect to an ₚ-metric for some p∈ [1,∞)∪\∞\. This generalizes a recent result of Chen, Li, and Yannakakis [STOC'24] from the _∞-case to all ₚ-metrics. Previously, all query upper bounds for p∈ [1,∞) \2\ were either exponential in d, log1ε, or log1/1-λ. Chen, Li, and Yannakakis also show how to ensure that all queries to f lie on a discrete grid of limited granularity in the _∞-case. We provide such a rounding for the ₁-case, placing an appropriately defined version of the ₁-case in FPᵈᵗ. To prove our results, we introduce the notion of ₚ-halfspaces and generalize the classical centerpoint theorem from discrete geometry: for any p ∈ [1, ∞) ∪ \∞\ and any mass distribution (or point set), we prove that there exists a centerpoint c such that every ₚ-halfspace defined by c and a normal vector contains at least a 1/d+1-fraction of the mass (or points).