← 研踪 PaperTrailarXiv:2607.23863 · v2
Polynomial-time computation of $\ell_p$-contraction fixed points for even $p$
首次提交 2026-07-27 06:12
版本更新 2026-11-13 23:34
雷达观测 2026-11-16 11:41
摘要
We give a -time algorithm that computes an -approximate fixed point of any -nonexpansive map , where is a convex compact set and is an even integer. This is the first algorithm with runtime for any fixed . Our techniques are based on a computationally efficient version of Sion's theorem for non-compact minmax problems, and extend to more general total search problems that admit low-degree polynomial potentials.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-13 23:34 · 最新观测版本
Polynomial-time computation of $\ell_p$-contraction fixed points for even $p$
We give a -time algorithm that computes an -approximate fixed point of any -nonexpansive map , where is a convex compact set and is an even integer. This is the first algorithm with runtime for any fixed . Our techniques are based on a computationally efficient version of Sion's theorem for non-compact minmax problems, and extend to more general total search problems that admit low-degree polynomial potentials.
查看此版本解读 →查看此版本原文 ↗