CS Paper Radar

A Decomposition Theorem and a Simple Algorithm for Contraction Fixed Points

Xi Chen, Yuhao Li, Mihalis Yannakakis

cs.CC cs.DS ·submitted 2026-10-31 22:01 UTC · v1
publishedtheory

Abstract

We prove a decomposition theorem for the problem of computing an approximate fixed point of a contraction map $f\colon [0,1]^k \to [0,1]^k$ under the $\ell_{\infty}$-norm. After a preliminary version of the decomposition theorem appeared on arXiv [CLY26], Feodorov and Haslebacher [FH26] gave a striking application of the theorem, showing that it can be used to convert any $\operatorname{poly}(k,\log(1/\varepsilon))$-query algorithm with running time $(k\log(1/\varepsilon))^{O(k)}$ into an algorithm with running time $(k\log(1/\varepsilon))^{O(\sqrt{k})}$. They instantiated this framework with an $O(k^2\log(1/\varepsilon))$-query algorithm with the desired running time, thereby obtaining the first subexponential-time algorithm for contraction fixed points under the $\ell_{\infty}$-norm and, via well-known reductions, the first deterministic subexponential-time algorithm for simple stochastic games and mean-payoff games. In addition to the decomposition theorem, as our second main result in this paper, we show that the $O(k\log(1/\varepsilon))$-query algorithm of [CLY25] can be implemented in time $(k\log(1/\varepsilon))^{O(k)}$; our algorithm may be viewed as conceptually simpler compared to the algorithm of [FH26]. A key observation here is that the function constructed in [CLY25], whose fixed points are used as the next query points, turns out to be nonexpansive under the $\ell_{\infty}$-norm, so the brute-force procedure can be replaced by known algorithms for contraction fixed points.

Comment
To appear in SOSA 2027. This paper subsumes some of the results in our earlier preprint arXiv:2602.10296. This manuscript is an August 2026 snapshot, predating OpenAI's list of papers and the subsequent developments. The discussion and references have been retained as of that date

Closest papers

Nearest neighbours by meaning across the whole index.

A Quasipolynomial Algorithm for $\ell_\infty$ Contractions

cs.GT cs.CCcs.LGmath.OC ·2026-10-21 ·Ashkan Soleymani, Gabriele Farina
similarity 0.65
Abstract

We give an algorithm for computing an $\eps$-approximate fixed point of any $d$-dimensional nonexpansion with respect to the $\ell_\infty$ norm in time $\log(1/\eps)^{O(\log^2 d)}$. At its core, our method uses a boosting argument to geometrically shrink a search region. Among other consequences, our algorithm implies that simple stochastic games can be solved in quasipolynomial time.

0.31

Improved Algorithms for Beck--Fiala with Bounded Sets

cs.DS cs.DMmath.COmath.PR ·2026-09-17 ·Dylan J. Altschuler
similarity 0.62
Abstract · 11 pages, comments welcome

We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size. Let $A$ be an arbitrary matrix $A\in\{0,1\}^{m\times n}$ with at most $d$ ones per column and at most $s$ ones per row. Let $\log^*$ denote the iterated logarithm and $\ell_j$ denote the $j$-fold composition of log. Assume $s\le\exp(O(\sqrt d))$. We provide an efficient algorithm that, for arbitrary sparsity $d$, gives $O(\sqrt d(1+\log^*n))$ discrepancy. Moreover, if $d\ge\ell_j(n)$ for a fixed integer $j\ge1$, the algorithm gives $O_j(\sqrt d)$ discrepancy. The proof is a bootstrapping scheme using the Bansal-Jiang algorithm.

0.46

Almost Optimal FPT Inapproximability for k-SetCover

cs.CC cs.DS ·2026-09-17 ·Venkatesan Guruswami, Xuandi Ren
published similarity 0.62
Abstract

We show that $\bigl(\frac{\log n}{\log\log n}\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\log k)}$-time algorithms under ETH. This improves upon the previous best factors $\bigl(\frac{\log n}{\log\log n}\bigr)^{1/k}$ in (Lin, 2019) and $(\log n)^{1/\operatorname{poly}(k)}$ in (Karthik, Laekhanukit, and Manurangsi, 2019). Here $k$ is the yes-case guarantee and $n$ is the number of candidate sets. While the best approximation ratio is still $O(\log n)$ via the greedy algorithm, closing this $1/k$ gap in the exponent has been a longstanding open problem; we remove this loss via a simple direct reduction. The construction is self-contained and does not rely on the parameterized inapproximability hypothesis (PIH). Starting with sparse parameterized 2-CSP instances (Karthik, Marx, Pilipczuk, and Souza, 2024), we build a monotone CNF formula, which is equivalent to a SetCover instance. To obtain a $k$-versus-$h$ gap, the reduction enumerates all hash functions from $Σ$ to $[2h]$ and all unsatisfiable 2-CSP instances on the same constraint graph with alphabet $[2h]$. For each such instance, it asks for a certificate that the hashed label pairs are not all contained in that instance. Perfect hashing makes this enumeration efficient for $h=\log n/\log\log n$.

0.59

Description Complexity Bounds for Analytic Approximations of Lipschitz Functions

cs.CL math.CA ·2026-10-10 ·Artem Vozmishchev
theory similarity 0.57
Abstract · 19 pages, 6 pages, 2 tables

We study how many bits are needed to write down an elementary analytic expression that uniformly approximates a Lipschitz function. Expressions are finite trees over the basis $\{+,-,\times,÷,\exp\}$ with the variables and rational constants, and their size is $\dc(f)$, the length of the shortest description of $f$ in a fixed binary description language. For functions of one variable we prove that every $L$-Lipschitz $F:[0,1]\to[0,1]$ has an everywhere-defined approximant of accuracy $Δ$ with $\dc(f)\le C\,(L/Δ+\lg(1/Δ+2))$ for all $L,Δ>0$, by a linear spline smoothed with logistic ramps in a description language with one repetition construct. We prove a matching lower bound valid for \emph{every} description language: for $Δ\le 1/36$ and every $L>0$ some $L$-Lipschitz function needs at least $\tfrac1{16}(L/Δ+\lg(1/Δ+2))$ bits. Hence the worst-case description complexity is $Θ(L/Δ+\lg(1/Δ+2))$. For functions on $[0,1]^d$ the same method gives $Θ_d\bigl((L/Δ)^d+\lg(1/Δ+2)\bigr)$, using a tensor-product spline whose coefficients are mixed second differences and cost $O(d)$ bits each. Without the repetition construct the upper bounds carry an additional logarithmic factor, whose necessity for plain expression trees is left open. A reference encoder, decoder and evaluator confirm the constructions numerically, and figures and tables report the checks.

0.27

Improved Approximation and Hardness Results for the Monitoring Edge-Geodetic Set Problem

cs.DS ·2026-10-20 ·Davide Bilò, Giordano Colli, Stefano Leucci
theory similarity 0.57
Abstract · 18 pages, 4 figures

We study the \emph{Monitoring Edge-Geodetic Set} problem (MEG-Set), which asks for a minimum-cardinality set $M$ of vertices of an undirected graph $G$ of $n$ vertices such that every edge of $G$ belongs to all shortest paths between some pair of vertices in $M$. We present new approximation and hardness results for MEG-Set. On the positive side, we design a deterministic polynomial-time $O(n^{1/3}\log^{2/3}n)$-approximation algorithm, improving upon the previously best-known $O(\sqrt{n\log n})$ approximation ratio. On the negative side, for every constant $\varepsilon \in (0,1)$, we prove that the problem admits no polynomial-time $\big(2^{\log^{1-\varepsilon} n}\big)$-approximation algorithm, unless $\mathsf{NP}\subseteq \mathsf{DTIME}(n^{\operatorname{polylog} n})$. This substantially improves upon the previously known logarithmic inapproximability bound. We also prove that \megset is $\mathsf{NP}$-hard on planar $2$-degenerate graphs, whereas $\mathsf{NP}$-hardness was previously known for $1$-apex $2$-degenerate graphs. We conclude by observing a connection between monitoring edge-geodetic sets and subsetwise distance preservers, i.e., subgraphs that preserve distances between all pairs of vertices in $S\subseteq V(G)$. Specifically, we show that any upper bound on the size of the latter yields a lower bound on the size of the former.

0.23

How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics

cs.DS ·2026-10-06 ·Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Chinmay Sonar +2 more
hot direction similarity 0.57
Abstract

Given a complete graph whose edge weights represent dissimilarities, Metric Violation Distance asks whether at most $k$ weights can be changed to form a metric. Motivated by metric repair for noisy data, the problem admits a polynomial-time $O(\log n)$-approximation due to Cohen-Addad, Fan, Lee and de Mesmay [SIAM J. Comput., 2025]. In the context of parameterized complexity, Fan, Gilbert, Raichel, Sonthalia and Van Buskirk [SWAT 2020] gave a $k^{O(k)}n^{O(1)}$-time algorithm. Fomin, Golovach and More [IPEC 2026] obtained an $O(k^2)$ kernel and a single-exponential algorithm for the ultrametric case. They asked whether general metrics admit a single-exponential algorithm and a polynomial kernel, and whether the tree-metric analogue is fixed-parameter tractable. We answer all three questions. We give a $2^{O(k)}n^{O(1)}$-time algorithm and prove that, unless ETH fails, no $2^{o(k)}n^{O(1)}$-time algorithm exists, even when all input distances lie in $\{1,2,3\}$. We also give a kernel with at most $6k$ vertices. The kernel supports solution lifting and can precede any approximation algorithm. Combined with the $O(\log n)$-approximation of Cohen-Addad, Fan, Lee and de Mesmay, it yields an $O(\log \mathrm{OPT})$-approximation at no asymptotic cost in running time. Both results extend to an interval generalization in which each edge $e$ has an observed value $M_e$ and an admissible range $[A_e,B_e]$ within which it may be reassigned; the kernel then has $7k$ vertices. Finally, Tree Metric Violation Distance is fixed-parameter tractable and solvable in $k^{O(k)}n^{O(1)}$ time.

0.48

Shaving Two Logs for Discrete and Continuous Fréchet Distance

cs.CG ·2026-10-12 ·Timothy M Chan, Isaac M Hair
similarity 0.57
Abstract

We revisit the classical computational geometry problem of computing the exact (discrete or continuous) Fréchet distance between two given polygonal curves with $n$ vertices in a constant dimension $d$. 1. We present an $O((n^2/\log^2n)\log^2\log n)$-time deterministic algorithm for the discrete Fréchet distance problem, improving the previous $O((n^2/\log n)\log\log n)$ result by Agarwal, Ben Avraham, Kaplan, and Sharir [SODA'13]. 2. We present an $O((n^2/\log^2n)\log^2\log n)$-time deterministic algorithm for the decision version of the continuous Fréchet distance problem, improving the previous $O((n^2/\log n)\log^2\log n)$ result by Buchin, Buchin, Meulemans, and Mulzer [SODA'14] and the recent $O(n^2/\log^{1+μ}n)$ randomized result by Cheng and Huang [SODA'25] for a small unspecified constant $μ>0$ (which converges to 0 as $d$ increases). 3. Finally, we present an $O((n^2/\log^2 n)\log^{O(1)}\log n)$-time Las Vegas randomized algorithm for the continuous Fréchet distance problem, improving the previous $O(n^2\log^2\log n)$ randomized result by Buchin, Buchin, Meulemans, and Mulzer [SODA'14] and the recent $O(n^2/\log^μn)$-time randomized result claimed by Cheng and Huang [SODA'25]. Since these problems have near-quadratic OV-based conditional lower bounds and shaving of two log factors is the best that is known for similar, simpler problems such as longest common subsequence and edit distance, our results reach the natural limit of the current state of the art (up to $\log\log$ factors).

0.27

Optimal Rényi and Logarithmic Additive Functional Entropy Estimation

cs.IT cs.CCeess.SPmath.ST ·2026-10-20 ·Arman Adibi, Piotr Krysta
theory similarity 0.57
Abstract

We characterize the minimax sample complexity of estimating Rényi entropy from independent samples on an alphabet of size at most $k$, when the known order $α>1$ may vary with $k$. For every fixed additive accuracy $\varepsilon\in(0,1/2)$ and success probability $2/3$, we prove matching bounds with constants independent of $k$ and $α$. For $1<α<\log k$, the rate is $Θ_\varepsilon(αk^{1-1/α}X_α(k,\varepsilon))$, where a monotone scalar inequality defines $X_α$ at noninteger orders. The bounds remain uniform as the order approaches one or an integer, or grows with the alphabet. Integer orders below $\log k$ have rate $Θ_\varepsilon(αk^{1-1/α})$; orders at least $\log k$ and min-entropy have rate $Θ_\varepsilon(k\log k)$. We extend the analysis to logarithms of positive additive functionals. For every fixed continuous $f$ satisfying $f(0)=0$, $f(x)>0$ for $x>0$, and $f(x)\sim ax^r$ at zero, with $a>0$ and $r>1$, estimating $-β^{-1}\log\sum_i f(p_i)$ at fixed accuracy, for fixed $β>0$, has sample complexity $Θ(k^{1-1/r})$ for integer $r$ and $Θ(k/\log k)$ otherwise. A replication reduction preserves the sampling experiment and transfers the rates for powers. Smooth flat functions show that regularity alone does not determine the complexity. The upper bound combines polynomial approximation, Gamma count statistics, and an independent pilot, with a global affine correction near order one. The lower bound uses interpolation to construct positive mean-one priors and controls their distinguishability and entropy separation after normalization. Exact count-variance identities and weighted approximation duality connect the two arguments.

0.17