ALT We study online interval selection with binary predictions of membership in a final optimal solution. Requests arrive in arbitrary order; accepted requests may be revoked, but rejected or revoked requests cannot be recovered. With rewards proportional to interval length, the best consistency under finite strict robustness is d=(3+√5)/2 when both guarantees hold almost surely on each fixed input, including for randomized algorithms. A continuous lower bound forces consistency strictly above d at every robustness budget below 4ϕ+3≈9.472, whereas our deterministic algorithm attains d with exact robustness ϕ⁵≈11.090, where ϕ=(1+√5)/2. Each held interval inherits a ledger recording positive prediction mass lost through irrevocable decisions. A tunable replacement cost gives a continuous family with exact consistency throughout and exact robustness on two parameter intervals, including (C,R)=(25/9,10) and (4,7). Randomization permits expected consistency approaching one with finite expected

ALT A set of vertices S in a graph G is a semitotal dominating set if S is a dominating set and every vertex in S has a witness, that is, another vertex in S within distance at most two. The Semitotal Domination problem asks whether G admits such a set of size at most k. We study this problem parameterized by the solution size. We provide a linear kernel of size 358k on planar graphs, a result that adds to several existing linear kernels for other domination variants on planar graphs. Additionally, we show Semitotal Domination is W[2]-hard on split graphs, on bipartite graphs and on t-claw-free graphs, it is W[1]-hard on circle graphs.

ALT In the generalized k-server problem, each of k servers moves in its own metric space, and a request (r₁,…,rₖ) is served once some server i stands at the point rᵢ of its space. We determine the randomized competitive ratio against an oblivious adversary when every space is a uniform metric. With unit distances the ratio is Θ(klog k): we give a (k+1)ln(2k)-competitive algorithm and show that for large k every algorithm has ratio at least ¹⁄₂₀kln k, improving the bounds O(k²log k) and Ω(k) of Bienkowski, Jeż, and Schmidt. When server i pays wᵢ per move, the ratio is exp(Θ(k)): we give a 20ᵏ-competitive algorithm, which also applies to weighted k-server on uniform metrics. This improves the exp(O(k²)) bound of Bijoy, Mondal, and Chiplunkar and matches the Ω(2ᵏ) lower bound of Ayyadevara and Chiplunkar up to the base of the exponent. Both algorithms follow normalized weights exactly, through couplings whose expected movement is controlled by the decrease of the logarithm of the total weight

ALT The mixed evacuation problem is a variant of the dynamic transshipment problem where there exist two modes of transportation and we allocate supplies to each mode of transportation in such a way that we can send all the supplies from sources to sinks within a given time limit. It is known that this problem can be solved in polynomial time when the number of sources and sinks is small. In this paper, we prove that the mixed evacuation problem can be solved in polynomial time with the ellipsoid method.

ALT A planar graph is rectilinear planar if it admits a planar orthogonal drawing without bends. For series-parallel graphs in the variable embedding setting the best known testing algorithm takes O(n²) time. We show that rectilinear planarity of a series-parallel graph with maximum degree four can be tested in 2ᴼ⁽ᵏ⁾⋅ n time, where k is the number of degree-4 vertices; the planar embedding is not fixed. In particular, the running time is subquadratic when k=o(log n). Each node of the SPQ*-tree stores the set of its admissible spiralities; we show that this set is a union of 2ᴼ⁽ᵏ⁾ arithmetic progressions of step two. All proofs are in the paper and are additionally verified in Lean 4 with Mathlib.

ALT In Principal Component Analysis (PCA), we are given as input a matrix A∈ℝⁿˣᵈ and an integer k≤ d, and the goal is to find the top k right-singular vectors of A. We consider the setting where each row of A is the private data of an individual, and we design an (∊,δ)-differentially private algorithm whose utility guarantee improves with the coherence of the input matrix. Prior works were either restricted to the case k=1 or ensured significantly weaker privacy protections. Our algorithm is based on a preconditioned variant of the power iteration method that is designed to significantly reduce the noise needed to ensure privacy.

ALT We study uniformity testing for the monomer-dimer model on a known graph G=(V,E). Given samples from an unknown distribution Dw(M)∝ ∏ₑ∈M wₑ over matchings M of G, we ask whether Dw is the uniform distribution over all matchings of G or is ε-far from it in total variation distance. Our main result is that, for every maximum-degree bound Δ, uniformity can be tested with ÕΔ(√ m/ε²) samples, where m=|E|. We complement this with an information-theoretic lower bound for general graphs: for every pair of parameters n≤ m≤ n², there are graphs with Θ(n) vertices and Θ(m) edges on which every tester requires Ω(√ m/ε²) samples. Thus, for bounded-degree graph families with m=Θ(n), testing uniformity over the space of matchings has widetilde Θ(√ n/ε²) sample complexity, in contrast with the Θ(n/ε²) samples needed to estimate Dw in total variation distance.

ALT We prove the first unconditional lower bound tradeoff between the number of passes and the approximation factor of maximum matchings in the semi-streaming model. Specifically, we show that any algorithm that outputs an (1-ε)-approximation to maximum matching requires Ω(log(1/ε)) passes for constant ε ∈ (0,1). Prior to our result, such tradeoffs were proven only conditioned on a certain combinatorial assumption about the density of Ruzsa-Szemerédi graphs. The state-of-the-art unconditional lower bound rules out any approximation factor better than (8/9) in two passes but leaves open the possibility of a (1-ε)-approximation for any ε > 0 even in three passes. We provide two different proofs of our result: the first proof uses the recent hierarchical-embedding framework of Assadi, Konrad, Naidu, and Sundaresan (STOC 2024) along with combinatorial constructions using Ruzsa-Szemerédi graphs. The second extends the two-level Ruzsa-Szemerédi hierarchy of Konrad and Naidu (SODA 2024) beyond tw

ALT We present a polynomial-time randomized algorithm that colors every n-vertex 3-colorable graph with O(n⁰.¹⁵³⁷) colors. This improves upon the previous bound of O(n⁰.¹⁹⁵⁴) colors by Bansal, Huang, and Lee (SODA '27). To achieve this result, we introduce a new algorithmic framework for finding a large independent set from a solution to the vector coloring SDP. Combined with the (combinatorial) dense-progress algorithm of Kawarabayashi, Thorup, and Yoneda (STOC '24), this framework yields an n¹/⁶⁺ᵒ⁽¹)-coloring algorithm. Furthermore, we strengthen the SDP-based algorithm specifically for 3-colorable graphs to achieve O(n⁰.¹⁵³⁷) colors.

ALT Suffix array and inverse suffix array queries on a text of length n can be answered in Õ(τ³) time using an auxiliary data structure occupying O(n/τ) words, for any τ ∈ [1,n].