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

ALT We study the problem of online clustering with movement cost, which generalizes the fundamental k-server problem. At each time step, the algorithm is given a set of points in a metric space and must choose k cluster centers. The cost incurred is the sum of the clustering cost at each time step and the total distance that the centers move over time. Prior work established competitive algorithms for the case k∈{1,2} on the line metric with the k-median clustering objective; under the k-median objective, this problem is also known as facility reallocation. We substantially generalize these results to arbitrary k, general metric spaces, and a broad class of clustering objectives. Specifically, we consider clustering costs defined as a norm of the distance vector from points to their nearest center, which subsumes the k-median, k-center, and (square root of) k-means objectives, and provide an asymptotically optimal O(k)-competitive randomized algorithm against adaptive online adversaries. T

ALT We present a simple deterministic semi-streaming algorithm that computes a (1-ε)-approximate maximum matching in general graphs in O(1/ε²) passes. This matches the pass complexity of the auction algorithm of Assadi, Liu, and Tarjan [SOSA'21] for bipartite graphs, and answers Open Question 2 of Assadi [SOSA'24 & TheoretiCS'25]. Our approach, which we call the budgeted price approach, is very different from the previous poly(1/ε)-pass semi-streaming algorithms for (1-ε)-approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use O(1/ε¹⁹) passes by Fischer, Mitrović, and Uitto [STOC'22], O(1/ε⁶) passes by Mitrović, Mukherjee, Sankowski, and Sheu [ICALP'25], and O(1/ε⁴) passes by Izumi, Kitamura, and Yamaguchi ['25].

ALT The conclusions of an experimental study of algorithms are only as good as the instances they are run on. Benchmark libraries for well-studied problems took decades to curate, while evaluations of new problems often fall back on random instances, which are known to be misleading: they may say more about the random generator than about the algorithmic question at hand. We treat instance generation as an optimization problem: parameterize the instance space, take the solver's running time as the objective, and let a black-box optimizer search for hard instances. We develop a widely applicable workflow built on the Nevergrad optimization platform and demonstrate it on four NP-hard problems: satisfiability, traveling salesperson, Hamiltonian cycle, and non-permutation flow-shop scheduling. The search needs only the solver, an instance encoder, and a compute budget. Our evolved instances beat the hardest instance of a budget-matched random draw in all four case studies, by an order of magni