ALT We study mean-based algorithms for single-choice prophet inequalities: the algorithm knows the number of variables and the mean of their maximum, but not their distributions. For arbitrary independent variables in a fixed order, we can already achieve the optimal 1/2 competitive ratio using only this mean. For i.i.d. variables and prophet secretary, however, we previously knew only a 1-1/e guarantee, which is far away from the ratios with full distribution information. We improve the guarantees in both settings using a simple and natural algorithm: we fix a continuous decreasing threshold function that depends only on the mean and accept the first variable exceeding its threshold. For i.i.d. variables, we prove a 0.7419 competitive ratio. For the prophet secretary, we prove a 0.6902 competitive ratio.

ALT We give an O(log k)-competitive randomized algorithm for weighted paging with delay. This improves upon the O(log k log n)-competitive algorithm of Gupta, Kumar, and Panigrahi (STOC 2020, SICOMP 2022) by removing the dependence on the number n of pages. Without delay, the optimal competitive ratio of randomized algorithms is Theta(log k), and since the lower bound carries over, our bound is tight. Our algorithm is fractional and combines mirror descent, used by Bubeck et al. (STOC 2018) for weighted paging without delay, with preemptive service, introduced by Azar et al. (STOC 2017) for online service with delay: when a request is served, an increase in the mirror descent potential is offset by preemptive service to other pending requests, with a budget derived from the mirror descent path. To obtain a randomized algorithm, we use the online rounding of Bansal, Buchbinder, and Naor (FOCS 2007) from classical paging.

ALT We study promise graph coloring in one pass insertion-only adversarial streams. We give a randomized algorithm that distinguishes 3-colorable graphs from graphs that are not 6-colorable using O(n³/2log(n/ε)log n) bits of space. This provides a truly subquadratic space algorithm for a constant coloring gap, answering an open problem posed by Assadi, Sundaresan, and Yazdanyar [SODA 2026] for q=3. Combining this algorithm with the vertex-sampling lemma of Assadi et al. yields, for any 144⌈log₂ n⌉≤ Q≤ n, a one-pass decision algorithm distinguishing 3-colorable graphs from graphs that are not Q-colorable using O((n/Q)³/2log⁵ n) bits of space. This improves upon the Õ((n/Q)²) bound achievable via dynamic streaming techniques. Setting Q=⌈n¹/3⌉ yields a semi-streaming decision algorithm, answering the decision version of another open problem posed by Assadi et al. On the negative side, we prove that distinguishing χ(G)≤ q from χ(G)≥(q-1)² requires Ω(n²/q⁵) bits of space, improving upon the pr

ALT We give a randomized combinatorial (1/2 - ε)-approximation for nonnegative non-monotone k-submodular maximization under a fixed number d of knapsack constraints, for k ≥ 2. The algorithm selects whole elements and follows the proportional top-2 rule of Chen et al.: it samples from the two labels with the largest marginal gains, with probabilities proportional to the positive parts of these gains. Extending their single-knapsack Bellman analysis, we construct a common resource potential and associated resource weights, with potential losses charged to greedy gains. Since these weights depend on the unknown optimum, we discretize their defining coefficients and enumerate monotone guesses over phases determined by resource consumption. This yields an algorithm using at most A(d,ε)(nk+1)ᴴ⁺² value queries, where n is the number of elements, A(d,ε) depends only on d and ε, and H=O(d log(2d) / ε²). The approximation ratio can be made arbitrarily close to the optimal oracle threshold for k=2 a

ALT We show that adding "catalytic space" (which starts full and must have its original contents restored at the end of computation) provably speeds up time-and-space-bounded computation. In a natural output model, with O(log(n)) free space and poly(n) catalytic space, we give algorithms for sorting and the discrete Fourier transform running in time n¹⁺ᵒ⁽¹⁾, and an algorithm for matrix multiplication running in time nω⁺ᵒ⁽¹). In the same output model, without additional catalytic space, sorting and DFT are known to require time-space product Ω(n²), and matrix multiplication is known to require time-space product Ω(n³) [Borodin and Cook, 1982] [Beame, 1991] [Yesha, 1984] [Abrahamson, 1991]. This is the first unconditional demonstration that (uniform, non-relativized) catalytic logspace algorithms can outperform their (non-catalytic) logspace counterparts. We give several further results relevant to fast catalytic algorithm design. We observe that many applications of sorting, FFT, and fast m

ALT We present a near-linear time algorithm to find a maximum clique in circular arc graphs, the intersection graphs of arcs on the circumference of a circle, answering a 30-year-old open question posed by Bhattacharya and Kaller [J. Algorithms 1997] and Tiskin [CPM 2006]. Our algorithm runs in time O(nlog² n), given n circular arcs, where the graph is implicit. Previous approaches take at least quadratic time (unless the implicitly given graph is sparse). To overcome the quadratic barrier, we solve (structured and related) instances of bipartite matching by interpreting them as a single, offline 2D dominance problem, which in turn we model as a shortest paths problem in a planar grid graph. This allows for the final step, which builds on the theory of Monge matrices to obtain sparse representation and efficient distance computations in the grid graph. Additionally, we provide an observation about the structure of circular arc cliques that leads to an algorithm for the weighted version of

ALT Exact forward triangle listers orient each edge of a graph by a vertex order. The order does not change the output, but it changes the work. For the adaptive lister, which scans the smaller of the two forward neighborhoods, the number of candidate tests is a known sum of minima of forward degrees, but how to optimize it had not been characterized. We show that this work is a concave function of the forward degrees, so choosing an order is concave minimization over the orientation polytope, whose vertices are the forward-degree vectors of orders. A single sort therefore rounds any point of the polytope, including the out-degree vector of any orientation, to an order with no more work, with a computable lower bound on the improvement. Minimizing the work is nevertheless NP-hard and APX-hard on triangle-free graphs of maximum degree three, and under the Unique Games Conjecture it has no polynomial-time constant-factor approximation. We also analyze logistic score relaxations and the large

ALT We give a deterministic worst-case algorithm for exact Batched Range Mode on an arbitrary array of length n and a batch of Q intervals. The algorithm returns the mode frequency and the smallest mode identifier for each query in time (n+Q)⁽tau+o(1)), where tau = 5 - sqrt(13) = 1.394448724536.... The algorithm combines virtual occurrence windows and block-boundary snapping with a query-restricted min-plus product whose first operand is column-monotone and whose second operand is row-monotone. A deterministic modular verifier uses geometric and query potentials to bound the same active regions; false modular matches are corrected by offline orthogonal range updates. The final analysis uses the sharper rectangular exponent curve of Uznanski (2026), together with exact rational parameter balancing and a transfer to prime fields. The analysis covers every frequency scale and arbitrary batch sizes. Exact frequencies and the smallest mode identifiers are recovered without increasing the expone

ALT The Transversal Hypergraph problem asks to enumerate (list) all inclusion-minimal hitting sets of a hypergraph. It usually assumes that the input is completely known and does not change over the course of the enumeration. In many applications, the underlying hypergraph is too large or expensive to compute. This motivated the implicit hitting set framework [Chandrasekaran, Karp, Moreno-Centeno, and Vempala, SODA 2011] for the corresponding optimization problem of finding a smallest hitting set. Access to the input is given by an oracle that either confirms that a query set S is a hitting set, or reveals a new hyperedge disjoint from S. We adapt this framework to enumeration. We show for a general class of algorithms that they are able to find all hitting sets when given access to such an oracle, even if the hypergraph is a priori unknown. We also prove that the current fastest Transversal Hypergraph algorithm, Minimal-to-Maximal Conversion Search by Murakami and Uno [DAM 2014], belongs

ALT Given a vertex v in a large bipartite graph G, can one quickly find a small densely connected region near v? This is the algorithmic core of many fraud detection, community detection, and recommender systems. One would like a local algorithm, i.e., an algorithm that probes G in only a small number of locations to find such a region. Our main contribution is the first constant-factor local approximation, independent of the maximum degree of the graph, for the classical notion of bipartite density: if the sides of a bipartite subgraph are S and T, its density is d(S,T):=e(S,T)/√|S||T|, where e(S,T) is the number of edges between S and T. We consider cohesive dense subgraphs, since every dense subgraph contains a cohesive core of at least the same density. For such a cohesive dense subgraph Smathbin∪̇T with at most k vertices per side, our algorithm, starting from any vertex in Smathbin∪̇T, uses O∊(k⁴⁺ᵋ) neighbor queries to find a subgraph Xmathbin∪̇Y of density Ω∊(d(S,T)) on O∊(k²⁺ᵋ) ver

ALT We study online graph coloring in the random-arrival model, where the vertices are presented in a uniformly random order. Assuming n and k are known in advance, we present a randomized exponential-time algorithm that colors any k-colorable graph on n vertices with O(k³ log² k log⁴ n) colors in expectation. This is the first online coloring algorithm that uses a polylogarithmic number of colors for all fixed k ≥ 3, and is better than a known lower bound of Ω(log^k-1 n) colors under adversarial arrivals for all fixed k ≥ 6. In addition, assuming n is known in advance, we obtain a competitive ratio of Õ(n²/3). For comparison, it is known to be NP-hard to approximate (offline) graph coloring within a factor of n¹-ε for all fixed ε > 0. Therefore, our exponential-time online algorithm achieves a performance guarantee beyond the NP-hardness threshold for polynomial-time approximation algorithms.

ALT We give faster algorithms for sampling from the uniform distribution over a polytope. Our main result is an algorithm that, when applied to a polytope with m constraints in n dimensions, uses m ⋅ polylog((m/δ)) iterations, each running in time O(mnω⁻¹), to return a sample within total variation distance δ to the uniform distribution. When m=O(n) and δ = poly((1/n)), our runtime improves upon all prior works by an Ω(n²/³) factor. Our sampler is based on the recent functional stochastic localization framework of [GST26], and achieves an iteration count nearly matching the Poincaré constant of the uniform distribution with respect to the logarithmic barrier.

ALT We study the problem of load balancing in the dynamic setting. The input is a bipartite graph G = (J ∪ M, E) of jobs J and machines M. Every job has a positive weight w(j). The goal is to assign every job in J to an adjacent machine in M so as to minimize the maximum machine load, where the load of a machine is the sum of the weights of the jobs assigned to it. Although load balancing has been studied extensively in many models of computation, the only previous result in the dynamic model addresses the incremental setting, where updates take the form of edge insertions and job deletions [BKS23b]. The authors show a (1+∊)-approximation for incremental fractional load balancing with poly({log(n)},1/∊) update time; they point out that their techniques do not extend to the decremental setting. Main Result: We obtain an algorithm which maintains a (1+∊)-approximate solution to the fractional load balancing problem under edge deletions and job insertions in Õ(log (n), 1/∊) update time. Our t

ALT The girth of a weighted undirected graph is defined as the length of a shortest cycle in the graph. In this paper, we give a randomized O(m¹⁺²/⁽ᵏ⁻¹) n¹/⁽ᵏ⁻¹)) algorithm to approximate the girth of a graph with n vertices and m edges to within a factor of k for any real k. We assume that all edge weights are non-negative. For sufficiently high approximation factors, our algorithm outperforms the state of the art by polylogarithmic factors. Specifically, for approximation factors k = clog n/log log n where c>5, our algorithm gives a runtime of O(m (log n)⁵/ᶜ), while instantiating the previous best k-approximation algorithms with k = clog n/log log n yields a running time of O( cn (log n)²⁺⁴/⁽³ᶜ) /log log n + mlog n) (Kadria, Roditty, and Vassilevska Williams, arXiv:2607.00938). Furthermore, the algorithm presented here is conceptually simple, has relatively small constants, eschews single-source shortest path and sparse spanner algorithms, and employs a new technique, which we call “rand

ALT Finding a global minimum cut in an unweighted graph is a fundamental task in the cut-query model. While there exists a randomized algorithm for this task using Õ(n) queries, known deterministic algorithms use Õ(n⁵/³) queries. We improve upon this result and give a simple deterministic algorithm that finds a global minimum cut using Õ(min{ nδ,n²/δ }) cut queries, which equals Õ(n³/²) in the worst case, where δ is the minimum degree of the graph. The key ingredient in our approach is an efficient maximum s,t-flow algorithm, for the case when the minimum s,t-cut has value at most δ.

ALT Let G=(V,E) be a d-uniform hypergraph with |V|=n and |E|=m. Estimating m from uniformly random hyperedge samples requires Θ(√m) samples by a birthday-paradox argument. We investigate the power of conditional sampling through a hierarchy of oracles: for an integer 1≤ s≤ d, given pairwise disjoint subsets X₁,…,Xₛ⊆ V, the s-colorful oracle returns a hyperedge chosen uniformly at random from all hyperedges contained in X₁∪⋯∪ Xₛ that intersect every Xᵢ, provided one exists. For s=1, this samples a uniformly random hyperedge induced by X₁. For every 1≤ s≤ d, we give a randomized algorithm that outputs m̂∈[(1-ε)m,(1+ε)m] with probability at least 2/3 using Os,d(poly(1/ε,log n)) conditional samples, where the exponent of log n is an absolute constant independent of both s and d. Conditional sampling thus yields an exponential separation over uniform hyperedge sampling. We also study the decision version, in which the oracle only reports whether a qualifying hyperedge exists. For every 1≤ s<d,

ALT We revisit the capacitated k-median problem, focusing on constant-factor approximation algorithms with either (1+ε)-cardinality or capacity violations. Previous results [DemirciL16, Li16} achieve an Oε(1)-approximation with (1+ε)-violations via complex extended configuration linear programming formulations with the round-or-cut framework. We propose a simpler, unified round-or-cut framework that handles both cardinality and capacity violation settings. Our main technical contribution is a mechanism that directly utilizes the costs of local instances to generate valid inequalities. Specifically, we partition the metric space into local pieces of size O(1/ε) as in previous work, and construct instances of capacitated clustering with penalties, which allow client demands to be unserved at a penalty cost. Solving these local instances yields lower bounds on the original LP cost, yielding valid LP constraints. In contrast, previous approaches rely on complex extended configuration LPs over

ALT We study deterministic single-item lot sizing with all-units quantity discounts, linear holding costs, and time-varying end-of-period inventory bounds. Unit prices may vary arbitrarily over time. For one common positive discount threshold, we give an exact algorithm requiring O(n³) arithmetic operations and O(n²) working space, including recovery of an optimal purchase plan. The method combines a critical-state theorem in cumulative-purchase coordinates with two prefix-minimum scans per dynamic-programming layer. The structural argument accommodates downward price discontinuities and distinguishes prescribed from free terminal inventory. With a fixed global set of m positive threshold values, the bounds become Oₘ(nᵐ⁺²) time and Oₘ(nᵐ⁺¹) space. Period-specific thresholds admit the same exact construction, but its state set can be exponential. For commensurate flow data, an inventory-lattice implementation takes O(PW) time, where P is the total number of price tiers and W is the largest

ALT Given a sequence of online points in general position in the plane, the geometric matching problem asks to match as many points as possible, subject to segment crossing constraints. We initiate the study of online geometric matching with limited crosses. In the k-crossing model each matched segment is allowed to have at most k crosses, where k=0 corresponds to the online noncrossing matching model for which Bose et al. proved that Greedy is an optimal deterministic algorithm achieving a competitive ratio of 2/3. In the triangle-free-crossing model no three matched segments are allowed to pairwise cross each other. Interestingly, we show in both cases the performance of Greedy does not improve by allowing crosses, and in fact, becomes worse in the k-crossing setting for k≥ 1. In the triangle-free-crossing model, we propose a simple two-layer-Greedy deterministic algorithm achieving a competitive ratio 4/5. More interestingly, we propose and study the underlying segments blocking points

ALT We study the metric distortion of the minimum spanning tree (MST) problem when numerical edge weights are unavailable and each vertex reports only a ranking of the other vertices induced by these weights. We first show, through a simple example, that without assumptions on the weights, no ordinal algorithm guarantees a finite approximation ratio. We therefore focus on general metrics and present a Borruvka-inspired algorithm using only ordinal comparisons that achieves distortion O(log n). We complement this result by showing that, for every ε>0, no deterministic ordinal algorithm guarantees distortion at most 3/2-ε on all finite metric instances. We then investigate more informative settings in pursuit of constant distortion, first considering two well-studied metric classes. For tree metrics realized on the given vertex set, a more careful variant of our initial algorithm achieves distortion 1, recovering an optimal MST from ordinal information alone. For the broad class of doubling