ALT We prove the all-exp property for the Traveling Salesman Problem with the 2-opt neighborhood, and for (3,2,2)- and (2,3,2)-Maximum Constraint Assignment with the flip neighborhood. The all-exp property states that infinitely many instances have an initial solution from which every sequence of improving moves to a local optimum, and hence every run of local search, has exponential length. For the Traveling Salesman Problem, the all-exp property was previously known for every k-opt neighborhood with k ≥ 3, so our result for 2-opt completes the picture for all k-kopt neighborhoods. In (p,q,r)-Maximum Constraint Assignment, each constraint involves at most p variables, each variable occurs in at most q constraints, and each domain has size r. Decreasing any of the parameters of (3,2,2) or (2,3,2) yields a problem in which every sequence of improving flips has polynomial length, so both Maximum Constraint Assignment results are tight. All three results settle long-standing open problems. Ou

ALT Data summarization techniques, such as coresets, are essential for scaling clustering algorithms to massive datasets. We study uniform sampling, which is an extremely simple and ultra-efficient method to construct coresets, in the context of weak, stable, and strong coresets for the k-means problem in Hilbert space. We begin with the fundamental case k=1, and establish matching upper and lower bounds on the sample complexity of stable and weak coresets, finding that the two notions require different sample complexities. As a consequence, we obtain tight bounds for stable 1-median coresets in ℓ₁ and ℓ₂ (and thus also Kendall–tau and Jaccard metrics), removing the dimension dependence of Carmel and Krauthgamer (ICLR 2026). Our analysis is substantially simpler than prior work and reduces to bounding the deviation of the sample mean. For the general k-means problem on ρ-separated instances, a well-studied structural assumption on the input, we show that uniform sampling yields a stable co

ALT We introduce peak-aware one-way trading (PA-OWT), an online problem in which a player must purchase a fixed quantity of an asset by a deadline, minimizing its total cost plus a charge proportional to the largest single purchase at any time. The model is motivated by electricity procurement, where the cost of energy rewards buying at low prices, but peak demand charges discourage concentrating purchases in short periods. Balancing these incentives is challenging when future prices are unknown: a large purchase can establish a peak that later decisions cannot undo. We develop a peak-aware online algorithm that balances price and peak control with deadline feasibility and achieves the order-optimal competitive ratio. We further extend our results to a learning-augmented algorithm that uses predictions of optimal purchasing decisions to achieve an order-optimal consistency-robustness tradeoff, exploiting accurate advice while retaining worst-case guarantees in the face of arbitrary predict

ALT We consider the class of open addressing hash tables that uses a fixed offset sequence r₀,r₁,…,rₙ₋₁ to find an open slot in the table. As special cases this subsumes linear probing (rᵢ=i) and quadratic probing (rᵢ=i²). We give a simple analysis that the expected insertion time when the load factor is 1-∊ is O(∊⁻²). This bound is tight for linear probing (but not for quadratic probing), so the analysis cannot be improved at this level of generality.

ALT The delayed deterministic finite automaton (D²FA) is a powerful tool for compressing the prohibitively large deterministic finite automata (DFAs) used in modern signature-based deep packet inspection systems. A D²FA augments a DFA with unlabeled default transitions to remove transitions that are similar. This technique works well in practice and has inspired numerous subsequent studies. However, existing approaches do not guarantee a D²FA of optimal size as they restrict the default transitions to form a forest. In this paper, we consider the problem of finding an optimal D²FA. We make the key observation that cycles of default transitions can be valid and produce a smaller D²FA, provided that for every character in the alphabet, at least one state in the cycle has an outgoing transition labeled by that character. This observation raises fundamental questions concerning the computational complexity of finding an optimal D²FA and the approximation guarantee of the standard (forest-restr

ALT A proper vertex coloring assigns colors to vertices so that adjacent vertices have distinct colors. A Kempe change in a proper vertex coloring exchanges two colors on one component of the subgraph induced by the vertices of those colors. For a fixed palette of k colors, textscKempe Reachability asks whether two given proper vertex colorings of the same graph are connected by a sequence of Kempe changes. This problem is known to be PSPACE-complete for every fixed k≥ 3. A graph is claw-free if no vertex has three pairwise nonadjacent neighbors. The line graph of a graph has one vertex for each edge, with two vertices adjacent exactly when the corresponding edges share an end. Line graphs are claw-free, and their Kempe changes correspond to edge-Kempe changes in the original graph, which exchange two colors on one component of the subgraph formed by the edges of those colors. A claw-free graph with a proper k-coloring has maximum degree at most 2k-2, whereas for k≥ 4 all proper k-coloring

ALT A k-path vertex cover (k-PVC) of a graph is a set of vertices meeting every path on k vertices. In Token Sliding, one token occupies each vertex of a cover; a move slides one token along an edge to an unoccupied vertex, preserving the cover property. We study whether two covers of a tree are joined by such moves. The case k=2 admits a linear-time decision algorithm. For every integer k≥2, we give an O(kn²)-time decision algorithm on trees of order n, with k part of the input. Two covers are reachable precisely when their rigid tokens, which never move, occupy the same set and every component remaining after their deletion has the same token count. The proof transforms configurations of equal size without rigid tokens into a canonical configuration built on properly rooted subtrees, whose paths on k vertices pass through their roots. A rooted-subtree recurrence identifies movable candidate tokens. We also give a direct recursive construction between the supplied endpoints, returning at

ALT We study the classic k-median problem and refine the iterative rounding framework recently introduced by Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which yields a (2+ε)-approximation. Our algorithm opens k+O(1) facilities and achieves an expected connection cost of at most 1.9999 times the value of the standard LP relaxation. Although the numerical improvement over 2 is small, it establishes a conceptual result: the integrality gap of the standard relaxation is strictly below 2 when a constant number of extra facilities is allowed. This partially answers an open question of Li and Svensson [STOC'13]. Combined with their reduction, our result yields a 1.9999-approximation algorithm for k-median. Our approach builds on several technical ingredients. First, we develop a preprocessing routine that makes the LP solution poly(ε)-integral, at the cost of a (1+ε) factor in the connection cost and O(1) extra facilities. Unlike the preprocessing of Byrka et al. [FOCS'26], our conversion is unc

ALT The Equal Subset Sum problem asks, given n positive integers bounded by M, to find two distinct non-empty subsets with the same sum. We study this problem in the regime M = 2ᵒ⁽ⁿ⁾, where the pigeonhole principle guarantees that a solution exists, and the main challenge is to find one efficiently. A straightforward dynamic-programming algorithm runs in time poly(n).M. After a sequence of improvements, the current best algorithm, due to Jin, Williams, and Zhang (ESA 2025), achieves running time poly(n).M¹/³. In this work, we give the first poly(n).Mᵒ⁽¹⁾-time algorithm for Equal Subset Sum in the regime M = 2ᵒ⁽ⁿ⁾. We complement this algorithmic result with a tight conditional lower bound showing that any substantial improvement would require a major breakthrough in approximation algorithms for lattice problems, building on recent techniques of Vafa and Vaikuntanathan (STOC 2025). Finally, we show that our techniques yield an asymptotically faster algorithm for the regime when M = Θ(2ⁿ): a

ALT Let \F be a finite field. Given N distinct points α₁,…,α_N ∈ \F^m and associated values β₁,…,β_N ∈ \F, we study the problem of computing an m-variate polynomial f(\vy) ∈ \F[\vy] of individual degree less than d, with d^m ≥ N, that satisfies f(α_i)=β_i for all i∈[N], whenever such an f exists. This is known as the multivariate polynomial interpolation problem. In this work, given N=d^m, we present a deterministic algorithm for multivariate polynomial interpolation over an arbitrary finite field \F that runs in near-quadratic time N²+o(1)poly(m,d,log|\F|), assuming d is ω(1). This bound holds whenever the associated multivariate Vandermonde matrix is nonsingular, has constant co-rank, or admits some special structure. In the general case, we give a randomized Las Vegas algorithm attaining the same near-quadratic running time, provided the finite field is sufficiently large and d grows similar to the previous case. Unlike other multivariate interpolation strategies, we do not assume black

ALT We study the mixing time of two local Markov chains for uniformly sampling proper edge colorings of trees. For a tree with n vertices and maximum degree Δ, we establish optimal mixing-time bounds for the single-edge Glauber dynamics when q≥Δ+2 and for the neighboring-edge heat-bath dynamics when q≥Δ+1. Both chains mix in OΔ(n(log n+log(1/ε))) steps, uniformly over the number of colors q. These bounds are tight in their dependence on n for fixed Δ. Our proof establishes log-Sobolev inequalities through local color release, reusable recoloring buffers, and component entropy mixing. The two dynamics require different local constructions: a two-spare-color buffer for single-edge updates and a second-layer controller for neighboring-edge updates. The resulting entropy analysis applies to general bounded-degree trees, including regimes where worst-case spatial mixing fails.

ALT An online tracker retains one state and may reset only to the current observation, although its complete observed history is available. Offline knows the future and obeys the same reset rule. Under a hard discrepancy radius, for every horizon T≥5 and every feasible randomized causal policy, a fixed path on a known five-point metric requires at least (T+1)/2 expected refreshes, against exactly two offline refreshes with a strict radius margin. Missing the useful prefix center forces a refresh at every suffix observation. The path visits four values, with resolution fixed as T grows. Write Jλ for cumulative discrepancy plus a charge λ>0 per refresh, and V_T for the sum of successive observation distances. A candidate prefix adapts Bienkowski and Schmid's randomized lower bound to this objective under current resets, even with a known horizon and V_T<3λ. This construction needs finer grids; a fixed finite metric with positive minimum separation instead admits a competitive policy for pena

ALT We study the paging with time windows problem, a natural generalization of classical paging, in which each request must be served within a specified time interval. This model allows the algorithm to delay service and batch service requests over time, but also introduces significant challenges due to overlapping requests. While the problem is well understood in the unweighted setting, where optimal O(log k)-competitive algorithms are known, the weighted case remains more elusive. The best previously known algorithm, due to Gupta, Kumar, and Panigrahi, achieves an O(log k log n)-competitive ratio, leaving a gap between weighted and unweighted settings. We obtain an O(log k)-competitive algorithm for weighted paging with time windows, matching the optimal competitive ratio. The core of our approach is a structural decomposition that separates the evolution of the cache from the scheduling of page loads. We show that, given a sequence of cache configurations, computing a near-optimal seque

ALT Temporal graphs are graphs whose edge relation changes in discrete time steps. The Temporal Exploration Problem (TEXP) asks for a temporal walk that visits all vertices. We show that every connected temporal graph with n vertices can be explored in O(qnlog³(n)) time steps, where q is the number of vertex color classes induced by the 2-dimensional Weisfeiler-Leman (2-WL) coloring. For small q, our bound substantially improves on the known worst-case bound of Θ(n²) in general connected temporal graphs. A corresponding walk can be constructed in deterministic polynomial time. The upper bound is complemented by lower bounds of Ω(nlog(n)) when q is constant and Ω(qn) when 1 ≤ q ≤ n. We also apply our techniques to the Temporal Rendezvous Problem (TRP), in which two agents that do not communicate have to meet on a vertex of the temporal graph. Our exploration algorithm yields that, with only polynomial-time computational power, the agents can meet in O(nlog³(n)) time steps, leaving a gap of

ALT The non-preemptive dial-a-ride problem (DaRP) asks for a minimum-cost route of a capacitated vehicle that serves a collection of pickup-and-delivery requests, without allowing objects to be transferred or temporarily unloaded. We study this problem and the closely related minimum-ratio Steiner k-Forest (SkF) in general symmetric metrics on n locations. We develop a randomized polynomial-time algorithm with expected approximation ratio O(n¹/4log¹1n) for the minimum-ratio SkF. Our algorithm combines a deterministic approximation on hierarchically well-separated trees with randomized metric embeddings. Using this algorithm, we obtain expected O(n¹/4log¹2n)-approximations for both the non-preemptive DaRP and the SkF. These guarantees improve on the previous n⁰.3+ε-approximation ratios for the SkF and the non-preemptive DaRP, where ε>0 is any fixed constant. Complementing these algorithmic results, we establish the first superconstant inapproximability bounds for the non-preemptive DaRP. Un

ALT Power grids use a constantly changing mix of fossil fuels and clean renewables like solar and wind. Because of this, the carbon footprint fluctuates drastically based on time and geographic location. Time-varying carbon intensity creates opportunities to reduce carbon emissions by shifting workloads to cleaner periods, but deadlines, task dependencies, and limited edge capacity constrain this flexibility. We study carbon-aware scheduling of jobs with release times, deadlines, and arbitrary precedence constraints under piecewise-constant carbon costs. Jobs execute preemptively on a single edge server or are outsourced at job-dependent costs to an unlimited-capacity cloud, modeled as providing instantaneous execution. The objective is to minimize the sum of edge carbon costs and cloud outsourcing costs while satisfying all timing and precedence constraints. For edge-only execution, we give an exact polynomial-time algorithm. Allowing cloud outsourcing makes the problem NP-hard, but we ob

ALT The k-center problem is one of the most fundamental clustering problems and has applications in a wide range of areas, including facility location, network design, data mining, and machine learning. Given a set of objects together with a distance measure, the goal is to select k centers such that the maximum distance from any object to its closest center is minimized. The k-center problem has been studied extensively from a theoretical perspective, both in metric spaces and on graphs. While there have been experimental studies for k-center clustering in metric spaces, a comprehensive experimental comparison of graph-based k-center algorithms on large-scale graphs is still lacking. In this paper, we bridge this gap by evaluating a set of algorithms ranging from classical approaches such as Gonzalez's greedy algorithm [TCS 1985], an algorithm based on the framework established by Hochbaum and Shmoys [Math. Oper. Res. 1985], to more recent methods, including algorithms by Thorup [SICOMP 2

ALT Counting small patterns is a core primitive in large-scale graph analytics, with numerous applications in data management and network analysis. As modern graphs are massive and continuously evolving, maintaining such counts efficiently under updates is essential. Although specialized dynamic algorithms for patterns with up to four vertices exist, they remain largely theoretical; practitioners instead rely on general-purpose or approximate methods. We present an in-depth study of two dynamic approaches by Eppstein et al. and Hanauer et al. for maintaining counts of triangles and all connected four-vertex subgraph patterns, both based on variants of heavy-light vertex partitioning. We introduce theoretical and practical optimizations and develop hybrid variants that combine complementary strengths of both approaches. Experiments on 56 large real-world and synthetic dynamic graphs show that our optimized algorithms outperform the original methods and strong static and dynamic baselines on

ALT An approximate distance oracle (ADO) is a compact data structure that answers distance queries within a multiplicative stretch k. The classical oracle of Thorup and Zwick [STOC'01, JACM'05] has stretch k=2ℓ-1 and uses O(ℓ n¹⁺¹/ℓ) space, for every integer ℓ≥1, and this trade-off is optimal for dense graphs under the Erdős girth conjecture. However, for sparse graphs (m=O(n)), their lower bound yields nothing beyond Ω(m) space. A pivot-based 1-hop ADO gives every vertex Õ(1) pivots and returns as an estimate the length of a walk of the form u→ pᵤ → pᵥ → v, where pᵤ is a pivot of u, pᵥ is a pivot of v, and pᵤ→ pᵥ is a stored distance. We observe that all the state-of-the-art ADOs with Õ(1) query time are in fact pivot-based 1-hop ADOs. Our main result is that, under the Erdős girth conjecture for graphs with constant degree, there are sparse graphs on which every pivot-based 1-hop ADO with stretch k requires Ω̃(m¹⁺²/⁽ᵏ⁺¹)) space, for every real k≥1. This matches the best known upper bound

ALT In STOC 1972, Jürg Nievergelt and Edward M. Reingold introduced the BB[α]-tree, also known as a weight-balanced tree, which for any α ∈ (0,¹⁄₂] is a binary search tree where every node with induced subtree size s has children with induced subtree sizes at least α(s+1)-1. A new rotation-based binary search tree, the PopTree, is introduced. The PopTree stores n elements and is a BB[tfrac120]-tree after the execution of each search and a BB[tfrac1729]-tree at all times, notably while rebalancing. For any constant α, its performance on search sequences of length Ω(n log n) is proved to be within a constant factor (which can depend on α) of the optimal offline rotation-based binary search tree that maintains the BB[α] balance invariant.