ALT We give a simplified, self-contained proof of OpenAI's FPRAS for counting perfect matchings in general graphs. As in the original proof, we use a restricted Poincaré inequality for two matchings to sample weighted perfect matchings and estimate their total weight. We simplify the proof of this inequality by isolating parts of alternating cycles directly on the original vertex set and controlling the resulting error terms. This avoids the auxiliary vertices and tree constructions used in the original proof. The argument preserves the required parameter bounds and yields the same FPRAS guarantee.

ALT We prove that, for every ε>0, a (ᵏ⁄₂ₖ₋₁+ε)-approximation algorithm for maximizing monotone k-submodular functions requires exponentially many value-oracle queries. This improves the ᵏ⁺¹⁄₂ₖ oracle bound of Iwata, Tanigawa, and Yoshida. Their ᵏ⁄₂ₖ₋₁-approximation algorithm therefore gives the exact threshold in the monotone setting. For k≥5, our bound also matches, up to an arbitrarily small loss, Aggarwal's recent approximation guarantee for non-monotone k-submodular maximization.

ALT We study capacitated line aggregation with per-batch maximum delay. Requests arrive over time at locations on a rooted half-line and are served in instantaneous batches of at most k requests. Each batch pays the distance to its farthest request plus the waiting time of its oldest request. The objective is to minimize the total cost. We give a deterministic online algorithm with competitive ratio 36+12√3. The algorithm uses a Next Fit idea along paths of nested time intervals: it assigns a new group to an existing batch when a path-load test permits, and opens a new batch otherwise. The path load controls both capacity and the cost of opening new batches. Randomizing the common scale improves the expected competitive ratio to (18+6√3)/ln2 against an oblivious adversary. Both guarantees extend to arbitrary indivisible request sizes. We also study capacitated LAD in the learning-augmented model. Advice revealed at its service times allows (1+ε)-consistency against every complete feasible

ALT Given a mixed graph G and an ordered pair (u,v) of vertices in V(G), we say that an orientation G⃗ of G satisfies (u,v) if v is reachable from u in G⃗. We consider problems in which we seek orientations that satisfy a maximum number of pairs. We distinguish between two different problems. In the most general problem called Fixed Pairs Maximum Mixed Reachability Orientation (FPRO), a multiset P of ordered pairs of vertices in V(G) comes with the input. In the more restricted problem All Pairs Maximum Mixed Reachability Orientation (APRO), P contains exactly one copy of every ordered pair of distinct vertices in V(G). We compare the computational complexity of FPRO and APRO in two ways: First, we show that both FPRO and APRO behave similarly when it comes to approximation. Namely, they both admit an asymptotic approximation, but are unlikely to admit a constant factor approximation. Then, we consider the parameterization with respect to the treewidth of the underlying graph of the input

ALT The arithmetic regularity lemma of Green is a fundamental tool in additive combinatorics, providing a decomposition of arbitrary subsets of finite Abelian groups into pseudorandom pieces with respect to Fourier analysis. Over the years, it has found numerous applications in combinatorics, property testing, and theoretical computer science. However, Green's proof is existential, and many algorithmic applications require an efficient procedure for constructing the underlying regular decomposition. De, Nadimpalli, and Servedio (SODA 2022) developed a query-efficient constructive regularity framework over F₂ⁿ and explicitly raised the problem of extending their dimension-independent sumset-estimation algorithm to other finite Abelian groups. In this work, we resolve this question for finite Abelian groups of constant torsion. We develop the first constructive version of Green's Arithmetic Regularity Lemma in this general setting. Given oracle access to a subset of the group, our algorithm

ALT Ski rental is one of the most fundamental online problems, where an agent repeatedly decides whether it should continue renting for a service, or buy it at a one-time fixed cost. In classic online analysis, an adversary may freely select any arbitrary time horizon t after which the instance terminates, hence leading to strong competitive ratio lower bounds of 2 (deterministic) and e/(e-1) (randomized). We consider a novel but natural model aiming at limiting the adversary's power without degrading its flexibility. A stochastic signal, containing no information apart from its arrival time, is transmitted to the algorithm at a time drawn from a known distribution scaled to [0,t]. This framework allows us to account for visible effects of the adversary's choice to the algorithm. Focusing as a first step on uniform distributions, we show that the best possible competitive ratios are approximately 1.478 (deterministic) and 1.438 (randomized). Surprisingly, simplistic deterministic strategie

ALT We study fully dynamic (Δ+1)-coloring against an adaptive adversary. Behnezhad, Rajaraman, and Wasim (SODA 2025) gave the first algorithm with Õ(n⁸/⁹) amortized update time, later improved to Õ(n²/³) by Flin and Halldórsson (ICALP 2025). We give a fully dynamic (Δ+1)-coloring algorithm with Õ(√ n) worst-case update time. Unlike previous algorithms, it avoids sparse-dense decompositions and relies only on elementary data structures, resulting in a short self-contained algorithm and analysis. Moreover, it avoids global recoloring, resulting in a worst-case recourse of 3.

ALT We study integer programs in standard form min{cᵀx:Ax=b, l{≤x{≤u,{ x∈ℤ}ⁿ}}}, where A∈ℤᵈˣⁿ and all entries of b,c,l,u are integers. Let N be an upper bound on the absolute values of the entries of A. We give a deterministic algorithm running in time poly(Lᵢₙ)+ f(d) Nᴼ⁽ᵈ⁾(1+log(cₘₐₓ+1))ᴼ⁽¹⁾, where cₘₐₓ bounds the absolute values of the costs and Lᵢₙ is the input length. Prior to our work, the best known running time was Nᴼ⁽ᵈ²) [Eisenbrand & Weismantel'20], and it has been a fundamental open problem whether the exponent O(d²) can be improved to one linear in d. We answer this question affirmatively.

ALT The minimum Birkhoff decomposition problem asks for a representation of a doubly stochastic matrix as a convex combination of as few permutation matrices as possible. This NP-hard problem arises in the scheduling of switches in data centers and satellite systems, in random assignments in economics and in the statistics of rankings. We consider doubly stochastic matrices whose entries are given with a fixed number of decimal digits and look for exact decompositions whose weights have the same precision. We propose a parallel method with three parts. For matrices built from few permutation matrices, the first part reads the weights from the frequencies of the entries and places them on the matrix positions by a rule that, given the correct weights, never fixes a position wrongly. The second part computes lower bounds from pairs of rows or columns, which remain valid for real weights, and from certificates of a satisfiability solver. For matrices built from many permutation matrices, the

ALT Using the Hadamard matrix for dimension reduction can accelerate the computation due to the fast Hadamard transform. However, the previous target dimension bounds in terms of the Gaussian width depend on the ambient dimension. In this paper, we obtain the following ambient dimension free bound using three Hadamard-diagonal blocks. Let H∈mathbbR^d×d be the normalized Walsh-Hadamard matrix, and let D₁,D₂,D₃∈mathbbR^d×d be independent Rademacher diagonal matrices. We prove that for any symmetric set T⊂ S^d-1, mathbbP{sup_boldsymbolt∈T|frac dm‖PΩ HD₃HD₂HD₁boldsymbol t‖₂²-1|≤ε} ≥1-δ whenever mgtrsimε^-2w(T)²log²frac eδ log⁴(e+fracw(T)εlogfrac eδ). Here w(T) is the Gaussian width of T, and Ω is a set of m distinct coordinates chosen uniformly. This is the first ambient dimension free bound on the target dimension using Hadamard transforms, for an arbitrary symmetric set in terms of its Gaussian width. We also prove that it is impossible to obtain an ambient dimension free bound for an arbitr