ALT In this paper, we show that there is no time-space tradeoff in incremental open addressing: there is an incremental open-addressed hash table that supports O(1) worst-case expected time insertions, positive queries, and negative queries, at any load factor (even load factor 1). As an intermediate result, we also revisit the problem of constructing an incremental open-addressed hash table that does not perform reordering (does not move elements around over time). In this setting, we show that it is possible to get O(1) amortized expected positive query time together with O(1) worst-case expected insertion time, a combination that was not previously known to be possible.

ALT We give a deterministic polynomial-time (60/11+\eps)-approximation for metric capacitated facility location with outliers, with arbitrary opening costs and nonuniform hard capacities. The algorithm respects both capacities and the outlier budget. Its guarantee, approximately 5.455, is close to the best known factor 5+\eps for capacitated facility location without outliers. The main ingredient is a local-search comparison for a common rejection penalty that retains the signed difference between the algorithm's and the comparator's rejection counts. Ordinary approximation guarantees for the penalty objective do not provide this comparison. We extend the exchange-forest accounting of Bansal, Garg, and Gupta so that a nonnegative assignment remainder pays for rejection and cancels in the final bound. We then merge two penalty assignments whose served counts bracket the outlier quota. Grouping alternating paths by their terminal facility preserves capacities and shares opening costs. These

ALT We study statistical inference and function evaluation problems in which the input binary vector is available only through a binary linear sketch, i.e., a fixed number of parity measurements. We show that under a certain monotonicity condition, simply truncating the input by retaining a subset of its coordinates is optimal among all linear sketches of the same size. In particular, this applies to distributed testing of correlations of binary vectors when they are of opposite signs and evaluating unate Boolean functions on uniformly random inputs. Additionally, given that truncation is optimal, we immediately have lower bounds for arbitrary binary linear sketches. To illustrate this application, we consider the one-way communication complexity of a distributional graph connectivity problem on n vertices and show that truncation, and hence all binary linear sketches, requires Θ(n log n) bits to achieve constant error, while a nonlinear protocol only requires O(log n) bits.

ALT The Hyperclique Hypothesis postulates that, for all constants k > h ≥ 3, detecting a k-clique in an h-uniform hypergraph with n vertices requires time nᵏ⁻ᵒ⁽¹⁾. This hypothesis is false: there is an algebraic algorithm that detects (and even counts) k-cliques in h-uniform hypergraphs in time O(n⁽¹⁻∊ₕk)). Via known reductions, this also refutes the recently proposed k-AP Hypothesis. As a consequence, many problems with conditional lower bounds based on these two hypotheses may admit faster algorithms after all. This result is almost entirely due to AI.

ALT We introduce a family of cut-sufficient instances for undirected multiflow that generalizes single-source planar and fully-planar instances. We also show the family has an additive 6 dₘₐₓ error for converting a fractional flow into an unsplittable one.

ALT A tournament is an orientation of a complete graph. A vertex v controls a vertex u≠ v if there is a directed path of length at most two from v to u, and a δ-king is one that controls at least δ(n-1) vertices. In the query complexity model, each query reveals the orientation of an edge. Shen, Sheng and Wu [SICOMP'03] established an Ω(n⁴/³) lower bound on the deterministic query complexity of finding a 1-king, and a non-matching upper bound of O(n³/²). Neither bound has been improved in over two decades, despite substantial progress on variants of the problem. For δ-kings with δ < 1, Biswas, Jayapaul, Raman and Satti [Discrete Applied Mathematics'22] showed that O(n⁴/³) queries suffice to find a ¹⁄₂-king. Lachish, Reidl and Trehan [FSTTCS'22] improved this guarantee to ¹⁄₂+²⁄₁₇ using Õ(n⁴/³) queries, and asked whether a larger fraction could be achieved within the same query bound. We answer this question affirmatively for every fixed fraction below one: for every fixed ε∈(0,1), we give

ALT We show that n × n permanents can be computed with O⁽²⁻εⁿ) arithmetic operations over every commutative ring, for ε = 10⁻⁴⁰. This solves a problem stated in Knuth's The Art of Computer Programming. Our algorithm implements the classical Binet–Minc identity with dynamic programming and careful bookkeeping. It also gives algebraic branching programs of size O⁽²⁻εⁿ).

ALT Gavoille and Labourel (ESA 2007) gave an adjacency labeling scheme of size log n+O(kloglog n) for graphs of treewidth at most k, and asked whether log n+O(k) bits suffice. We give a labeling scheme of size log n+O(loglog* n) for every fixed k, the first improvement of the second-order term for any k≥ 2. Equivalently, there is an induced-universal graph with n(log* n)^O_k(1) vertices for this family. We work with laminar families of intervals, in which a vertex finds each earlier neighbor as the owner of an interval of a given nesting depth around it. As long as every subtree occupies consecutive positions, the nesting depth must be logarithmic, and loglog n bits per neighbor follow. We give up contiguity. Heavy subtrees are moved out, which brings the depth down to O(log* n); the intervals broken by the moves are repaired with 2^O(k³) additional intervals per vertex; and the bits needed to find these intervals are paid for by the moved subtrees.

ALT The k²-tree is a compact representation of Boolean matrices: it stores the recursive hierarchy of their non-empty submatrices, with neither values nor coordinates, and serves rows and columns alike. Its traversal, however, locates the children of each node by rank queries, a chain of dependent irregular loads that leaves a GPU waiting on memory. We implement sparse matrix-vector multiplication (SpMV) on k²-trees for the GPU. Since the traversal does not depend on the vector, the positions of the children are static: we descend the tree one level at a time and obtain them from a parallel prefix sum or from a sampled directory of about 0.1 bits per node. Descending in tiles bounds the temporary memory by the depth of the tree, so the device memory of a product is known before it runs. The same traversal computes right and left products, for one vector or a batch, over the plus-times, Boolean and tropical semirings. We evaluate the engine on an NVIDIA GB10 and an H100 with fourteen Wikida

ALT A seminal result of Ahn, Guha, and McGregor (PODS'12) showed that a cut sparsifier of an unweighted graph can be computed from a near-linear number of linear measurements. Later work extended this to spectral sparsifiers (Kapralov et al., FOCS'14) and to near-linear recovery time (Kapralov et al., SODA'20). For weighted graphs, these sketches rely on grouping edges by weight, which general turnstile streams do not allow. Chen, Khanna, and Li (FOCS'22) removed this limitation, using tildeO(n/ε³) bits of space. We improve the space to tildeO(n/ε²) bits. Our algorithm makes one pass over a general turnstile stream of a weighted graph, processes each update in tildeO(1) time, and recovers, in tildeO(n/ε²) time, a reweighted subgraph with O(nε^-2log² n) edges that preserves every cut within a factor of 1±ε. Its space, update time, and recovery time are all optimal up to polylogarithmic factors.

ALT Online matching with stochastic rewards is a generalization of online bipartite matching in which an attempt to match an online arrival to an offline resource may fail with some probability. Each arrival allows at most one attempt and the success probabilities of its edges are revealed when it arrives. Greedy is 0.5-competitive, which is the best possible for deterministic algorithms. While better competitive ratios are known in several special cases, beating 0.5 for arbitrary probabilities has remained open. We show that, against the adaptive offline benchmark and for arbitrary probabilities, a randomized Perturbed Greedy algorithm is at least 0.591-competitive in the unweighted setting and at least 0.531-competitive with vertex weights. The perturbation functions combine Greedy with scaled versions of the classic exponential function.

ALT We study directed graph problems in the semi-streaming model where we are restricted to Õ(n):=O(n⋅ polylog(n)) space for processing the edge stream of an n-node graph and can make one or a few passes to solve the given problem. A longstanding open problem in multipass streaming is determining the number of semi-streaming passes needed to solve directed s,t-reachability: there is an exponential gap—Ω(log n/log log n) vs n¹/²⁺ᵒ⁽¹)—between the best-known lower and upper bounds. Several related fundamental digraph problems, e.g., topological sorting, acyclicity testing, and decomposition into strongly connected components (SCCs), are known to have the same semi-streaming pass lower bound. However, no o(n/polylog(n))-pass upper bound was known for any of them. Our main result achieves an n¹/²⁺ᵒ⁽¹)-pass semi-streaming algorithm for each of these problems. As a corollary, we get algorithms with the same pass and space usage for a broad class of DAG problems that admit a certain form of dynam

ALT We establish a separation between the stability thresholds of Minimum Sum-of-Radii (MSR) clustering and two closely related objectives. Known hardness results show that, on general metrics, exact recovery for Minimum Sum-of-Diameters and symmetric k-center is hard for every fixed 1<γ<2, unless NP=RP. We show that MSR admits deterministic polynomial-time exact recovery for every fixed γ>1, extending Gao and Reyzin's result for γ≥2. All three results use the same Bilu–Linial stability model: the optimal partition remains uniquely optimal when each pairwise distance is multiplied by any factor in [1,γ], without requiring the perturbed distances to satisfy the triangle inequality. The number of clusters is part of the input. For 1<γ<2, our algorithm runs in nᴼ⁽⁽ᵞ⁻¹⁻⁵)) time. The main structural insight is that a cheap merge in one part of the instance would allow a profitable split elsewhere under a suitable perturbation, contradicting stability. The resulting exchange inequality controls

ALT Suppose an optimization problem is randomly restricted, independently on each variable, and re-optimized after the restriction is revealed. For multilinear objectives, every fixed solution is unbiased after rescaling, but re-optimizing introduces an upward bias. We bound this excess, the hindsight gain, over products of arbitrary compact local domains in Euclidean unit balls. For interactions A=(Aₑ)ₑ among r distinct variables and independent random weights ζᵢ, the gain is at most Oᵣ(‖A‖_F M⁽ʳ⁻¹/2)σₘₐₓ), where ‖A‖_F² is the sum of squared coefficients, M=∑ᵢEζᵢ², and σₘₐₓ²=maxᵢVar(ζᵢ); only second moments are needed. Under uniform retention with probability p, we sharpen this to Oᵣ(pʳ⁻¹/²√(1-p) n⁽ʳ⁻¹/2)‖A‖_F), which is tight for every fixed r and p∈(0,1). Our proof combines a comparison principle along a single support direction with tensor projection, vector contraction, and repeated thinning. Applications: (i) For fixed arity and alphabet size, solving the subproblem induced by O(ε⁻²)

ALT In expander routing, we seek to establish paths in the expander graph between given source-target pairs while minimizing both dilation (maximum path length) and congestion (maximum edge load). We study this problem in a decremental dynamic setting where the underlying graph remains an expander despite ongoing edge deletions, and source-target pairs can be added or removed. Our goal is to maintain paths under these updates while keeping dilation and congestion low and performing low computation per update. We present a randomized algorithm that maintains paths with polylogarithmic dilation and congestion against an adaptive adversary, while incurring only polylogarithmic amortized computation per update, all with high probability. Our approach leverages a recent technique called Temporal Aggregation to maintain a collection of low-congestion, low-dilation random walks resilient to adaptive adversaries.

ALT We study the stochastic matching problem, where a graph G is known in advance, but each edge survives independently with probability p. The goal is to select a subgraph H of small maximum degree before seeing the surviving edges, while preserving a (1-∊) fraction of the expected maximum matching size. This problem has received significant attention due to its numerous applications in kidney exchange, labor markets, and online dating. In this paper, we show there is always a subgraph H ⊆ G achieving a (1-∊)-approximation while having a maximum degree of at most O(log(1/∊)/∊⁴ ⋅ ¹⁄ₚ). This resolves a major conjecture of the literature, first stated by [BDH, STOC'20], that poly(1/∊ p) degrees suffice. The best previous bound was (1/p)ᵉˣᵖ⁽⁽¹/∊log(1/∊))) by [ABGR, STOC'25]. The key to this result is a lemma of independent interest that any distribution over the matchings of a stochastic graph can be transformed to another distribution which matches each vertex with exactly the same probabili

ALT The Submodular Orienteering problem asks for an s-t walk in a directed graph that maximizes a monotone submodular function over the visited vertices subject to a bound on its length. We give a deterministic polynomial-time approximation algorithm with subpolynomial approximation rate 2^O(√(logn loglogn)). This improves over the O(nε) approximation rate that was previously known for every fixed ε>0. We prove a decomposition lemma that partitions a directed graph into rooted subgraphs such that every path intersects only polylogarithmically many such subgraphs. Our algorithm uses this decomposition to construct its recursive subproblems.

ALT We determine the optimal sample size for constructing value coresets for Max-Cut via uniform vertex sampling. That is, sampling O(ε⁻²) vertices uniformly at random in n-vertex graphs with edge weights in [0,1] yields a reweighted subgraph whose Max-Cut value is an additive ε n²-approximation to that of the original graph, with constant success probability. This improves the previously known O(ε⁻⁴) upper bound and matches the known lower bound. The same guarantee holds also for importance sampling, where vertices are sampled proportionally to their weighted degrees, and we further prove a matching lower bound for this sampling method. Our analysis extends directly to metric Max-Cut, showing that importance sampling of O(ε⁻²) vertices yields (1±ε)-approximation to the Max-Cut value, and to Max-Cut in graphs with edge weights in [0,1] and average weighted degree d̄, achieving the same (1±ε)-approximation by either uniform or importance sampling of O(ε⁻²n/d̄) vertices. We additionally show

ALT We study exact exponential-time algorithms for 3- and 4-coloring. For 3-coloring, the best previously published running-time bound is O⁽1.3289ⁿ), due to Eppstein (SODA 2001). We improve this bound to O⁽1.3204ⁿ) deterministically and O⁽1.3159ⁿ) using randomization. For 4-coloring, the best previously known running-time bound is O⁽1.7159ⁿ), due to Wu, Gu, Jiang, Shao, and Xu (ESA 2024). We improve this bound to O⁽1.6975ⁿ) deterministically and O⁽1.6933ⁿ) using randomization. Our algorithms for both problems combine constraint satisfaction algorithms with dynamic programming over tree and path decompositions, exploiting their complementary strengths on different graph structures. For 6-coloring, the best published randomized running-time bound is exponentially smaller than the best published deterministic bound. For 3- and 4-coloring, however, no such improvement through randomization was previously known. To the best of our knowledge, our results provide the first randomized running-time

ALT We study the deterministic and nondeterministic cut query complexity of minimum cut in undirected graphs with arbitrary nonnegative edge weights. For the nondeterministic case, we show that every n-vertex graph has an O(nlog²(2n))-query certificate of its exact global minimum-cut value, such that any other nonnegatively weighted graph on the same vertex set that agrees on these queries has the same minimum cut value. A key ingredient is a way to certify a maximum s–t flow value with only O(n) cut queries. For the deterministic case we give an algorithm that finds an exact global minimum cut using O(n³/²log³(2n)(log{log(2n}))²) cut queries. Previously no O(n²⁻ε) deterministic bound was known for arbitrary nonnegatively weighted graphs. The algorithm follows Karger's two-respecting tree approach. The key new ingredient is a deterministic construction of a weak skeleton of the input graph G: an explicit weighted graph H in which every minimum cut of G is a 5/4-approximate minimum cut.