CS Paper Radar

Daily listing

2026-11-18 · cs.DS

2 papers first submitted this day (UTC) in cs.DS — Data Structures and Algorithms. arXiv announces a day's submissions the next evening, so the newest day fills up over ~24 h.

Score = weighted mean ofCitations 20%Upvotes 10%Code stars 10%Venue 15%Code/data 10%Novelty 15%Momentum 15%Substance 5%how it works

Theory & Algorithms 2

Faster polynomial-space algorithms for poset problems

cs.DS math.CO ·2026-11-18 ·László Kozma, Junqi Tan
Abstract

We give a polynomial-space, deterministic, exact algorithm for counting linear extensions of partial orders over $n$ elements, with running time $O^*((2\sqrt{2})^{n}) \subseteq O(2.829^n)$. This improves upon the long-standing bound of $O^*(4^{n})$ attainable by standard divide and conquer (Savitch 1970, Gurevich and Shelah 1987). Our algorithm uses a similar balanced splitting approach as the classical algorithm, but applies it only to the elements outside a largest antichain. For the elements of the antichain itself we develop a formula based on inclusion-exclusion that accounts for the ways in which they can appear in a linear extension. The technique is also applicable to other problems on posets, which we illustrate by solving the well-studied jump number problem in a similar running time of $O^*((2\sqrt{2})^{n})$ and polynomial space. To our knowledge, these are the first polynomial-space algorithms with a running time below $4^n$ for both problems.

0.34

Optimal universal sets for submodular functions

cs.DS ·2026-11-18 ·Marek Adamczyk, Richard Ueltzen, Jan Vondrak
theory
Abstract · Results obtained with the assistance of GPT-6 Astra

We resolve the question of deterministic non-adaptive algorithms for nonnegative submodular maximization: We prove that for every $n \geq 2$ and $ε\in (0,\frac{1}{4})$, there is a polynomial-size family ${F}_{n,ε}$, $|{F}_{n,ε}| = n^{O(1/ε^2 \log (1/ε))}$, such that for every nonnegative submodular function $f:2^{[n]} \to {\bf R}$, $\max_{S \in {F}_{n,ε}} f(S) \geq (1/4 - ε) \max_{S \subseteq [n]} f(S)$. It is also easy to show that a factor better than $1/4$ cannot be achieved by any fixed polynomial-size family. A related result that we prove is that there is a distribution ${D}_{n,ε}$ supported on polynomially many subsets of $[n]$ such that $(1 - ε) {\bf E}_{R \sim {U}_n}[f(R)] \leq {\bf E}_{R \sim {D}_{n,ε}}[f(R)] \leq {\bf E}_{R \sim {U}_n}[f(R)]$, where ${U}_n$ is the uniform distribution on $2^{[n]}$, and $f$ is any nonnegative submodular function. This is interesting in light of the fact that uniform convergence does not hold for submodular functions: Sampling polynomially many sets from ${U}_n$ and taking the empirical mean does not converge to the true expectation uniformly for all submodular functions. The construction of ${F}_{n,ε}$ and ${D}_{n,ε}$ is based on a new semidefinite extension of submodular functions: We show that the Goemans-Williamson rounding technique for a near-orthogonal arrangement of vectors gives a value close to the uniform expectation, and this rounding can be derandomized, since near-orthogonal vectors can be constructed in logarithmic dimension.

0.08