← 研踪 PaperTrailarXiv:2503.16089 · v3
Query-Efficient Fixpoints of $\ell_p$-Contractions
首次提交 2025-03-20 20:30
版本更新 2026-10-27 00:17
雷达观测 2026-10-29 00:35
摘要
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).
作者备注：36 pages. This is the TheoretiCS journal version
期刊信息：TheoretiCS, Volume 5 (2026), Article 17, 1-36
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-10-27 00:17 · 最新观测版本
Query-Efficient Fixpoints of $\ell_p$-Contractions
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).
查看此版本解读 →查看此版本原文 ↗