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].

ALT This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting. Let X ⊂ ℝᵈ be a set of n points, labeled by a collection of k boxes: the label of each point in X is determined by the unique box containing it. A learner aims to exactly recover the labels for every point in X given access to a label oracle. We consider three increasingly-structured settings. In the most general setting, there are no conditions on the boxes, and they may overlap. We show that CAL (Cohn-Atlas-Ladner 1994), a classical active learning algorithm, is minimax-optimal with query complexity Θ(kd log (n/kd)). When the boxes are disjoint, we examine two regimes. In the large-k regime, CAL remains minimax-optimal. For the constant-k regime, an optimized variant of the Halving algorithm (Hegedüs 1995) can beat CAL by a log(d) factor. Finally, in the most-structured settings, the boxes correspond to the leaves of a constant-sized decision tree. We prove a tight query

ALT Large sparse matrices—adjacency matrices of web and social graphs, feature matrices of machine-learning pipelines, the relations of graph databases—are routinely compressed to save space. Classical compressors, however, force the matrix to be decompressed before it can be used, so the space savings often yield a computational overhead. A recent line of work studies computation-friendly compression: formats that are not only small, but let us carry out matrix–vector products, and in some cases matrix–matrix products, sums and closures, directly on the compressed representation in time proportional to that compressed size. This survey organizes that literature around the kind of redundancy each format exploits: spatial clustering of the nonzeros (k²-trees and their variants), similarity between rows (Boldi–Vigna-style referencing and set-difference compression), repeated substrings (grammar compression), and dense bipartite substructures (bicliques). For each family we describe the repre

ALT We give a deterministic quasi-polynomial-time algorithm for the maximum independent set problem. If an N-vertex graph contains an independent set of size 2^-tN, where t is an integer with 1≤ t≤√(log N)/12, then our algorithm finds an independent set of size 2^t in time N^O(t). This gives an approximation ratio of N/2Ω(√(logN)) in time N^O(√(logN)), improving on the approximation ratio N/2^{Ω((logN)¹/3)} obtained by Lovett [Lov26]. A limitation of this form of analysis follows from the integrality gaps of Tulsiani [Tul09]. These gaps imply that a universal guarantee of the form Las_R(t)(G)≥2^-tNLongrightarrowα(G)≥2^t, at 2^o(√(logNloglogN)) levels, cannot hold over a range extending beyond t=O(√(log Nloglog N)). Thus, the exponent 1/2 is the limit of this form of analysis, up to a factor of √(loglog N).

ALT We study the problem of submodular maximization under a matroid constraint. In this problem, there is a monotone submodular function f: 2^N → mathbbR^+ and a matroid M(N, I), accessible via value and independence oracles and the goal is to find the independent set S ∈ I maximizing the objective function, i.e., f(S) = max_I∈I f(I). In the fully dynamic setting, the active ground set N ⊆ N evolves through element insertions and deletions. The goal is to maintain a solution S ⊆ N with S ∈ I and f(S) = max_I⊆N,,I∈I f(I) after each update. Two approximation algorithms have been proposed to solve this problem: D\"utting et al. developed a (4+ε)-approximation algorithm with an expected amortized update time of O(k²/ε log k log n log³ k/ε), and Banihashem et al. achieved a similar approximation with a better update time O(k log k log³ k/ε). However, these methods both become inefficient when the rank k of the matroid is large (e.g., when k = n^o(1)). The central open question in this line of w

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