EUVIMEDEUVIMED entdecken
Crossref

Query-Efficient Fixpoints of $\ell_p$-Contractions

Sebastian Haslebacher, Jonas Lill, Patrick Schnider, Simon Weber

TheoretiCS · 27.10.2026 · Volume 5

DOI: 10.46298/theoretics.26.17 ↗

Kurz gefasst

Fachartikel in der Zeitschrift TheoretiCS, online erschienen am 27.10.2026. Verfasst von Sebastian Haslebacher und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We prove that an $ε$-approximate fixpoint of a map $f:[0,1]^d\rightarrow [0,1]^d$ can be found with $\mathcal{O}(d^2(\log\frac{1}ε + \log\frac{1}{1-λ}))$ queries to $f$ if $f$ is $λ$-contracting with respect to an $\ell_p$-metric for some $p\in [1,\infty)\cup\{\infty\}$. This generalizes a recent result of Chen, Li, and Yannakakis [STOC'24] from the $\ell_\infty$-case to all $\ell_p$-metrics. Previously, all query upper bounds for $p\in [1,\infty) \setminus \{2\}$ were either exponential in $d$, $\log\frac{1}ε$, or $\log\frac{1}{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 $\ell_\infty$-case. We provide such a rounding for the $\ell_1$-case, placing an appropriately defined version of the $\ell_1$-case in $\textsf{FP}^{dt}$. To prove our results, we introduce the notion of $\ell_p$-halfspaces and generalize the classical centerpoint theorem from discrete geometry: for any $p \in [1, \infty) \cup \{\infty\}$ and any mass distribution (or point set), we prove that there exists a centerpoint $c$ such that every $\ell_p$-halfspace defined by $c$ and a normal vector contains at least a $\frac{1}{d+1}$-fraction of the mass (or points).

Zitieren

APA

Haslebacher, S., Lill, J., Schnider, P., & Weber, S. (2026). Query-Efficient Fixpoints of $\ell_p$-Contractions. TheoretiCS, Volume 5. https://doi.org/10.46298/theoretics.26.17

Vancouver

Haslebacher S, Lill J, Schnider P, Weber S. Query-Efficient Fixpoints of $\ell_p$-Contractions. TheoretiCS. 2026;Volume 5. doi:10.46298/theoretics.26.17

BibTeX
@article{Haslebacher2026,
  author = {Haslebacher, Sebastian and Lill, Jonas and Schnider, Patrick and Weber, Simon},
  title = {Query-Efficient Fixpoints of $\ell_p$-Contractions},
  journal = {TheoretiCS},
  year = {2026},
  volume = {Volume 5},
  doi = {10.46298/theoretics.26.17}
}
Kostenlos starten →