ALT We study the order-selection prophet inequality. A gambler knows the distributions of independent nonnegative random values, chooses the order in which to inspect them, and may irrevocably accept at most one value, at the time it is revealed. Since the order is irrelevant when the values are i.i.d., no algorithm can guarantee more than the optimal i.i.d. ratio Γ⋆≈0.74544 of the expected maximum. We give an algorithm with competitive ratio 0.74500001, less than 4.5×10⁻⁴ below this bound. The algorithm samples independent arrival times and uses item-dependent thresholds. It is designed so that, conditional on its value, every item is selected with probability equal to a fixed fraction of its probability of being the maximum. We show that the constructions of this form that apply one local rule to every item are exactly those given by an allocation kernel, that is, by a coupling of two uniform random variables. Requiring every rarely winning item to follow the optimal i.i.d. threshold pat

ALT The greedy algorithm for minimum 3-cut splits a global minimum-weight cut and then the cheaper of its two sides; it is a tight 4/3-approximation. We show that it is exact, from every global minimum-weight cut, whenever some optimal 3-partition has two parts joined by total weight at least the weighted edge connectivity λ. This extends both theorems of Hochbaum and Shmoys from unweighted planar graphs to all weighted graphs, recovers the 4/3 bound, and generalizes to minimum k-cut with a one-paragraph proof. The remaining hard instances have all pair weights below λ; for them we prove a merge lemma for Gomory-Hu sides. Finally, we give a 7-vertex graph with a unique Gomory-Hu tree whose unique optimal 3-partition contains no side of that tree, so the first stage of Kapoor's algorithm does not suffice on its own. The main theorem, the 4/3 bound, the merge lemmas and the counterexample are verified in the Lean 4 proof assistant.

ALT The Poisson approximation theorem states that when m balls are tossed uniformly and randomly into n bins, the distribution of the bin loads can sometimes be approximated by n independent Poisson random variables of mean m/n. We show that when the balls are tossed via a random F₂-linear map, the load distribution is still governed by this Poisson distribution, albeit in a (necessarily) weaker manner. This allows us to show that a random linear map behaves like a fully random map in the following ways: 1. Expected loads. We show that the expected value of the rth largest bin is governed by the rth largest value among n independent Poisson random variables of mean m/n. Specializing to the canonical setting of m=n and r=1, our bounds show that the expected maximum load when n balls are hashed into n bins by a random F₂-linear map is no more than the corresponding expectation for a fully random map plus (3/2) + o(1). Specializing to m≫ nlog n, we show that the expected max load is (1+o(1))m

ALT We study unweighted nonpreemptive throughput maximization: given jobs with processing times, release times, and deadlines, schedule a maximum-cardinality subset on identical machines. For every fixed ε>0, we give randomized algorithms with expected approximation ratios 17/13+ε in polynomial time and 21/17+ε in pseudopolynomial time. These improve the respective 4/3+ε and 5/4+ε guarantees of Armbruster, Grandoni, Tinguely, and Wiese [STOC'26]. Both results hold for an arbitrary number of identical machines. Our algorithms build on their configuration-LP and matching framework, which partitions time into blocks. For a job whose window meets multiple blocks, its boundary blocks are the first and last such blocks. Crossing boundary pairs, whose endpoints strictly interleave, permit additional assignments to sampled execution slots, while a noncrossing family can be coordinated using consistent joint distributions on at most three blocks. The exchange analysis accounts for fractional job as

ALT We study online vector balancing for independent sparse random vectors: each arrival is supported on a uniformly random set of s of the n coordinates, with nonzero entries equal to one (binary model) or independent random signs (signed model), and an online algorithm must sign each vector upon arrival. The prefix discrepancy is the largest \ell_∞-norm of the signed sums up to the horizon T, the terminal discrepancy that of the sum at time T. For binary inputs with 2≤ s≤ n/2 and T=Θ(n), Altschuler and Tikhomirov showed that both are of order √s+loglog n; they asked how the prefix discrepancy depends on the horizon and whether a matching terminal bound holds at every prescribed time. Over long horizons, the two differ. For every fixed s≥2 and c>0, every online algorithm, even a randomized one that knows the horizon, incurs with high probability prefix discrepancy Ω(loglog n+(log T/log n)α_s) for n≤ T≤ e^cn, where α_s=(2^s-1-1)/(2^s-1). For s=2, quadratic Greedy matches this bound; for fi

ALT We study the optimal coreset size for Euclidean (k,z)-clustering, where z≥1 is fixed. Huang, Li, and Wu (STOC 2024) proved a lower bound of Ωz(kε⁻ᶻ⁻²) for ε≳z k⁻¹/⁽ᶻ⁺²), matching the known upper bound up to polylogarithmic factors. For 0<ε<k⁻¹/⁽ᶻ⁺²), the upper bound Õz(k⁽²ᶻ⁺²/(z+2))ε⁻²) remained unmatched. The previous lower bounds gave only Ωz(max{kε⁻²,k⁽²ᶻ⁺³/(z+2))ε⁻¹}). We close this gap by proving a matching lower bound throughout 0<ε<k⁻¹/⁽ᶻ⁺²), including arbitrarily small ε. Together with known bounds, this determines the optimal worst-case coreset size as Θ̃z{({min{k⁽²ᶻ⁺²/(z+2))}ε}⁻², kε⁻ᶻ⁻²}) for every integer k≥1 and 0<ε<1. In particular, the bounds are Θ̃(k⁴/³ε⁻²) for k-median when ε<k⁻¹/³, and Θ̃(k³/²ε⁻²) for k-means when ε<k⁻¹/⁴. Our construction uses projection levels to encode four-wise independent signs, allowing k centers to detect omissions regardless of how the retained points are reweighted.

ALT We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an n-point metric (P,d) and a parameter α≥ 1, an α-navigable graph is a directed graph G=(P,E) such that for every ordered pair of distinct points s,t∈ P, the vertex s has an outgoing edge (s,p) with d(p,t)<d(s,t)/α. The objective is to minimize the number of edges. Approximation algorithms for this problem were recently studied by Khanna, Padaki, and Waingarten (SODA 2026), and independently by Conway et al. (SODA 2026). These works show that the single-criterion problem faces a Set Cover barrier: an O(log n)-approximation is achievable, whereas obtaining an o(log n)-approximation is NP-hard. To obtain faster algorithms, Khanna, Padaki, and Waingarten introduced bicriteria approximation, in which the output graph is required to be α-navigable, while its size is compared against that of an optimal β-navigable graph for some relaxed parameter β ≥ α. They gave a fast matrix-multiplication

ALT We give an Õ(n/ε)-space algorithm for the minimum cut problem in dynamic streams, resolving the space complexity of streaming min-cut up to polylogarithmic factors. Ding, Garces, Li, Lin, Nelson, Shah, and Woodruff (ITCS 2025) obtained the same Õ(n/ε) space bound for insertion-only streams, while prior to our work the best known bound even for unweighted dynamic streams was Õ(n/ε²), due to Ahn, Guha, and McGregor (PODS 2012). Our main technical contribution is an Õ(n/ε)-space for-each cut sketch in dynamic streams, which may be of independent interest. The construction applies to weighted graphs under general ±Δ updates, a stronger model than the standard dynamic-stream setting in which weighted edges are inserted and deleted in their entirety. Despite this stronger guarantee, our algorithm is surprisingly simple and relies on very little machinery. We also obtain applications to minimum ℓₚ-norm k-partitioning for every fixed k, weighted correlation-clustering evaluation for two cluste

ALT We present new constructions of vertex fault-tolerant (VFT) (α,β)-spanners with substantially improved size bounds. Given a bound f on the number of vertex faults, an f-VFT (α,β)-spanner is a subgraph of G that preserves an (α,β)-spanner of G- F for every fault set F ⊆ V with |F| ≤ f. Most existing constructions of VFT (α,β)-spanners rely on a black-box sampling technique that incurs an exponential blow-up compared to their non-fault-tolerant counterparts. We develop two independent techniques for constructing f-VFT (α,β)-spanners that improve the dependence on f, reducing it to polynomial overhead. For every unweighted graph G=(V,E) on n vertices, stretch parameter k, and fault parameter f, we show: (i) f-VFT (O∊(kᵋ), O∊(k))-spanners with Õ(fᵉˣᵖ⁽¹/∊)⋅ n¹⁺¹/ᵏ) edges for any ∊ ∈ (0,1). For any fixed constant ∊, this introduces a poly(f) overhead compared to the non-faulty constructions of [Ben-Levy and Parter, SODA 2020] and [Chechik and Lifshitz, SODA 2026]. (ii) For any δ ∈ (0,1), an

ALT We study a simple random deletion algorithm to find short circuits in regular matroids. Given a regular matroid M with m elements, the algorithm randomly deletes each element independently with probability 1-1/mΘ⁽¹/ᵍ) where g is the size of a minimum circuit, and returns the remaining set R of elements. We establish the following results: 1. With high probability, R contains no circuit and is therefore independent. 2. For every α-approximate minimum circuit C where α≥ 1, with probability at least m⁻ᴼ⁽ᵅ⁾, the entire circuit C survives in R and moreover, the minimum number of elements that need to be removed to make R independent is O(αlog(α+2)). This yields an algorithmic proof that the number of α-approximate minimum circuits is mᴼ⁽ᵅ⁾, improving the previous known bound of mᴼ⁽ᵅ²) by Gurjar and Vishnoi, and resolving a recent conjecture of Khanna, Putterman, and Song. Our results yield two immediate applications. First, we obtain very simple RNC algorithms for computing the shortest cir

ALT The Burrows-Wheeler transform (BWT) is the core of many compressed full-text indexes and most read aligners. The fastest BWT constructions on GPUs need about 20 bytes of device memory per character, which severely limits the texts that can be processed there. For example, on our GPU with 24 GB device memory, this is only about 1200 MiB. Prefix-free parsing (PFP) can be used to reduce the memory requirements of BWT construction algorithms in main memory. But, it uses hash tables and inverted lists which are not suited for GPUs. We show that PFP-based BWT construction can work with only sorting, scanning, and simple data-parallel procedures. This results in our GPU construction gpupfpbwt that on an NVIDIA RTX 3090, reduces the peak memory on an English text 11.9 bytes per character. There, it can processes 2108 MiB input files, which is 1.8 times larger than what the current state of the art libcubwt can handle. It is faster than or on par with libcubwt on eight of nine repetitive texts

ALT We study non-preemptive scheduling on identical parallel machines in which assigning job j to machine Mᵢ incurs the cost cᵢⱼ=aᵢwⱼ+bⱼ. The processing times pⱼ and the cost weights wⱼ are independent, and the number of machines is part of the input. For every fixed ε∈(0,1] and every deadline T for which a schedule with makespan at most T exists, we give a polynomial-time algorithm that computes a schedule with makespan at most (1+ε)T whose total assignment cost does not exceed the minimum under the deadline T. Using this algorithm as a subroutine, we obtain a polynomial-time approximation scheme for minimizing the makespan under a total cost budget whose schedules always satisfy the budget; this answers an open question for costs cᵢⱼ=lᵢcⱼ with cⱼ independent of pⱼ. For the lexicographic problem, in which the total assignment cost is minimized among all schedules of minimum makespan, we obtain in polynomial time a schedule with makespan at most 1+ε times the minimum and total assignment c

ALT In this paper, we introduce braided cuckoo hashing, an open-addressed hash table that supports load factor up to 1 - ε (for some parameter ε ∈ (0, 1)), while supporting queries, insertions, and deletions in worst-case time O(log ε⁻¹), with high probability. This result represents an exponential improvement on insertion/deletion time over previous constructions, and disproves a conjecture of Bender, Kuszmaul, and Zhou that the product of worst-case query time and expected insertion/deletion time must be Ω(ε⁻¹).

ALT A path or cycle in a 2-edge-coloured graph is alternating if consecutive edges have different colours. These objects are natural analogues of paths and cycles in graphs, and even more so in digraphs. A well-studied class is that of acyclic 2-edge-coloured graphs, that is, those forbidding alternating cycles. In particular, (acyclic) 2-edge-coloured graphs generalize directed (acyclic) graphs (DAGs), but the complexity of problems on DAGs is much better understood than that of the corresponding problems on acyclic 2-edge-coloured graphs. We investigate the complexity of two such problems, whose directed counterparts are well-known. Our first result is an nᴼ⁽ᵏ⁾-time algorithm for the alternating k-linkage problem on acyclic 2-edge-coloured graphs. This problem asks for k vertex-disjoint alternating paths joining k prescribed pairs of vertices. This generalizes the directed k-linkage algorithm for DAGs. For every fixed k, this also yields a polynomial-time algorithm for finding k internal

ALT We study the fundamental problem of PAC learning positive linear combinations of k arbitrary ReLU activations on ℝᵈ with respect to the Gaussian distribution, in L₂ loss. We give the first fully-polynomial time algorithm for this learning task. Specifically, our algorithm draws poly(d, k, 1/∊) samples, runs in poly(d, k, 1/∊) time, and outputs a hypothesis that is ∊-close to the target concept with high probability. All prior algorithms for this problem require super-polynomial time in k or 1/∊, or leverage strong well-conditioned assumptions on the weight matrix. On a technical level, our approach develops a novel boosting procedure of a “weak” learner that recovers the hidden weight vectors to constant error, in a list-decodable manner. To develop this “weak” learning procedure, we leverage implicit tensor computation techniques to construct a low-degree filtering procedure based on Hermite tensors of the target function. This procedure amplifies separation among (clusters of) weight

ALT Boolean matrix multiplication is a fundamental operation in many graph-based applications, including web and social network analysis, information retrieval, and graph query evaluation. However, conventional sparse representations such as CSR}/CSC still incur significant space and time costs on large graphs. In this work, we introduce a method for multiplying Boolean matrices based on a biclique-based compressed representation that decomposes them into dense bipartite subgraphs, thereby capturing large sets of implicit edges. We first improve the iterative biclique extraction algorithm of Hern\'andez and Navarro by introducing percentile-based parameter adaptation that dynamically adjusts its parameters according to the degree distribution, enhancing both extraction efficiency and compression ratio. We then extend the Schoor multiplication algorithm to operate directly on biclique-encoded matrices, thereby enabling a compositional form of multiplication where the output can also be repr

ALT We study the structure and exact certification of nonnegative tensor decompositions supplied through rational factor matrices. Every failure of minimality or essential uniqueness contains an irreducible positive exchange between p supplied terms and q competing terms. A dimension count based on the Lovitz–Petrov splitting theorem bounds the effective order of such an exchange, the sum over the modes of the joint factor-span dimension minus one, by p+q-2, and this bound is attained at every supplied length R≥2. After eliminating ambient-row variables by the Farkas lemma, the resulting semialgebraic systems have fewer than 2R² real variables. For input bit length L, this gives a deterministic G(R)Lᴼ⁽ᴿ²)-time algorithm that computes the nonnegative rank and an exact minimum-length decomposition, decides minimality and essential uniqueness, and returns exact witnesses when either property fails. The exponent is independent of the tensor order and the mode dimensions. For Lebesgue moment te

ALT The selection problem asks to find the k-th smallest element in a given set X. Its complexity is well-known to be Θ(|X|) for every fixed k. We consider the poset selection problem where a partial order P on X is given, and the underlying order of X is guaranteed to be a linear extension of P. This generalizes several variants of the selection problem studied before. Our main result is an algorithm that performs O( k + OPT(P,k) ) comparisons, where OPT(P,k) is the minimum number of comparisons required for the input (P,k). If P is a rooted tree, we obtain an O( OPT log (k / OPT) ) algorithm, which can be further improved to O( OPT log log (k/OPT) ) or O( OPT log OPT) under mild assumptions about P. Our algorithms are based on the work of Kaplan, Kozma, Zamir, and Zwick [SOSA 2019], who used Chazelle's soft heaps [J. ACM 2000] to simplify several older results. We introduce a new soft heap variant, the weighted soft heap, which allows greater control over which elements get corrupted.

ALT We consider the problem of maintaining the triconnectivity in some biconnected graph G in the incremental dynamic setting. We consider updates in the form of edge insertions and edge subdivisions, and triconnectivity queries, i.e. queries of the form "are there at least three vertex disjoint paths between a and b?". All algorithms presented in this paper are deterministic. All queries and updates are answered in worst-case O(log n) time. By combining this result for biconnected graphs with a result of Holm and Rotenberg [SODA'20] we get an algorithm for general graphs with a worst-case running time of O(log² n) per operation. These algorithms represent an improvement of the state-of-the-art by a factor of O(log n).

ALT We establish an Ω(d) lower bound on the competitive ratio of convex body chasing in ℝᵈ with ℓₚ movement costs for any p ∈ [1, ∞). Previously, the best known lower bound for general p was Ω(max{√d, d¹⁻¹/ᵖ}), established by Bubeck et al. (2019); a linear lower bound was known only for p = ∞, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior bound for every fixed p ∈ [1, ∞) and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio O(d) - is asymptotically optimal for every ℓₚ norm. Our lower bound is based on the recursive construction of Bubeck, Coester, and Rabani (2023) for metrical service systems, which gives a lower bound of Ω(r²) for requests of size O(r) in that setting. We show that requests in their construction, each comprising a set of discrete points in a graph metric, can be mapped to the vertices of convex requests in a (2r+1)-dimensional vector space while approxi