Papers

In this paper we study the genome rearrangements done by translocation events. Genome rearrangements were used to measure evolutionary distance between organisms since 1936 (Dobzhansky and Sturtevant). The chromosomes are represented as strings of DNA and the translocation operation is defined as the exchange of prefixes between two strings. This operation results in the creation of two new strings (chromosomes) that can then be utilized in subsequent translocations. A translocation is referred to as contiguous if the new strings are produced in a single copy, so each of them can be used in only one subsequent operation. When the words produced by a translocation operation are considered to have an infinite number of copies, the translocation is referred to as non-contiguous. If the exchanged prefixes are of equal length, the translocation is called uniform. Otherwise, the translocation is termed non-uniform. The translocation distance between two sets of strings, termed the input set and the target set, represents the minimum number of translocations necessary to obtain all the strings in the target set via translocation operations. We prove that both the non-uniform contiguous and the non-uniform non-contiguous translocation distance problems are NP-hard over arbitrary finite alphabets, where the alphabet is part of the input. For the case in which the target set consists of a single string, we give a fixed-parameter tractable algorithm parameterized by the length of the target string.

Partizan Edge Geography is a two-player game on a graph where each player has their own token on a vertex and moves their token to a neighbor in a turn removing the edge. Two player alternately move their tokens and the first player who cannot move loses the game. Fraenkel and Simonson (TCS, 1993) showed that the winner determination of this game is PSPACE-complete on directed graphs, given a graph and token positions. This paper resolves its complexity on undirected graphs by showing the PSPACE-completeness on bipartite undirected graphs of maximum degree 3. The same reduction also works for a variant where two tokens cannot be placed on the same vertex.

The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns. Motivated by draft mechanisms in sports leagues, we investigate strategic behaviour in online round-robin for subadditive agents. This gives rise to an extensive-form game, and we study the computational problem of computing a subgame perfect Nash equilibrium (SPNE). We show that for just two submodular agents, computing an SPNE is $\mathsf{PSPACE}$-hard. Even for the class of $\mathit{OXS}$ utilities, which are a special case of submodular utilities, computing an SPNE remains $\mathsf{NP}$-hard for a small number of agents. We complement our computational results with normative results. We show that for just three additive agents, there exist instances where every equilibrium violates EF1. This separates the online and the direct revelation games. On the positive side, we show that for additive agents every equilibrium allocation is proportional up to one good (PROP1) and for two additive agents it is also EF1. Finally, by showing that round-robin is bossy at equilibrium, we prove that the number of equilibrium allocations can be exponential even if agents have lexicographic preferences.

Let $\mathcal{M}_1,\mathcal{M}_2$ be two matroids on a common ground set $V$, given by independence oracles, and let $S$ be a maximum-cardinality common independent set. We study the problem of deciding whether there exists another maximum common independent set $T\ne S$, and of outputting one when it exists. Writing $n=|V|$ and $r=|S|$, we give a Las Vegas algorithm using $\tilde O(n\sqrt r)$ expected independence queries and a deterministic algorithm using $\tilde O(nr^{2/3})$ queries. As an application, all maximum common independent sets can be enumerated with at most two another-solution calls between consecutive outputs and after the last output; if there are $L$ solutions, exactly $2L-1$ such calls are made. Neither algorithm constructs the exchange graph. Instead, they perform Kahn-style source peeling through two deletion-only data structures. One side uses the heavy/light categorization of Blikstad, van den Brand, Mukhopadhyay, and Nanongkai. For the opposite side, where no transposed oracle is available, we give a collective randomized classifier and a deterministic capacity-saturation certificate.

We study the challenging problem of learning depth-three circuits in the mistake-bound model of (realizable) online learning, which is a more difficult model than distribution-free PAC learning. Prior algorithms for this problem, due to Servedio and Tan [ST17], could only learn polynomial-size depth-three circuits of poly$(n)$ size over $\{0,1\}^n$ with a running time of $2^{n - \Omega(n/\log n)}$, and hence they ran in time $N^{1-o(1)}$ where $N=2^n$ is the running time of a naive memorization-based approach. In this work we substantially improve on the [ST17] result: for any constant $\gamma\geq1$, we give an algorithm that learns depth-three circuits of size $n^\gamma$ with running time \[ 2^{n-c_\gamma n}, \] where $c_\gamma>0$ depends only on $\gamma$ and not on $n$. Hence we achieve a polynomial savings over the naive approach for learning any polynomial-size depth-three circuit. The main driving force behind our improvement is an improved bound on the approximate degree of width-$k$ CNFs. Inspired by Szegedy [Sze04] and Magniez et al. [MNRS11], the rough idea of our construction is to use a Chebyshev polynomial to efficiently amplify the spectral gap of a carefully designed random walk. This is combined with a random-restriction-like approach to separately learn different subfunctions corresponding to different assignments to a randomly chosen set of variables, using the Perceptron algorithm over a specially designed feature space. A simplified warmup instantiation of our approach achieves $c_\gamma = \exp(-O(\gamma))$; by augmenting this warmup with further ingredients we obtain the sharp form of our result, which achieves $c_\gamma=\Omega(1)/\gamma$.

We prove that counting perfect matchings is $\#P$-complete under polynomial-time Turing reductions on each of three classes of simple, unweighted graphs: monotone graphs, unit interval graphs, and chordal permutation graphs. The monotone result settles the exact-counting complexity left open by Dyer, Jerrum, and Müller (JACM 2017), complementing their rapid-mixing theorem. Inspired by quantum circuits, our reductions implement a circuit simulation using globally coupled matching-transfer operators. The key construction is an exact projection, implemented by a polynomial-length sequence of normalized transfers, that restores tensor-product locality and makes encoded gates composable. Interpolation-based cancellation then reduces circuit evaluation to unweighted perfect-matching counts in all three classes. We also place Dyer and Müller's class QChains within the distance-hereditary graphs and give an $O(n^2)$-arithmetic-operation counting algorithm for the latter, improving the $O(n^4)$ bound obtainable from Curticapean and Marx (SODA 2016). Together with prior results, these advances complete the exact-counting classification of the graph classes in Dyer and Müller's diagram (SIDMA 2019).

We consider the determinant maximization problem under partition constraints: Given an $n\times n$ PSD matrix A and a partition matroid $M$ on $[n]$, find a base $S$ of $M$ that maximizes $\det(A_{S,S})$. We give an $e^{O(k)}$-approximation algorithm to find such a set $S$, where $k$ is the rank of $M$. This improves upon the current $k^{O(k)}$-approximation, and matches the current $e^k$-estimation guarantee, up to $O(1)$ factors in the exponent. Our algorithm is based on rounding the geometric max-min relaxation due to Nikolov-Singh'2016, using a continuous potential-driven process, and several new structural and analytic properties of this relaxation.

We study the problem of scheduling jobs on a serial-batch machine with the aim of minimising the total weighted late work. In a serial-batch setting, jobs within a batch are processed sequentially, and none are removed from the machine until the last job in the batch completes its processing. The processing time of a batch is the sum of the processing times of the jobs within it, and the completion time for each job in the batch is equal to the makespan of the jobs in the batch. When a new batch begins, a constant setup time is required for the machine. We show that minimising the total weighted late work in this environment is $NP$-hard even if all jobs have a common due date and unit weight. For the general problem, we present a pseudo-polynomial time dynamic programming algorithm. Additionally, we explore two special cases, i.e., one with a common due date and another with an agreeable condition among due dates, processing times and weights. For both special cases, we develop specialised pseudo-polynomial time dynamic programming algorithms. The proposed approaches are equipped with specialised acceleration techniques to enhance their computational performance. The extended experiments demonstrate that the dynamic programming algorithms outperform Gurobi in time efficiency.

We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix $\mathbf{M}\in\mathbb{R}^{n\times n}$ and parameters $k$ and $\alpha$, the goal is to preprocess $\mathbf{M}$ so as to answer entry queries $(u,v)\mapsto \mathbf{M}^{k}[u,v]$ up to additive error $1/n^{\alpha}$. We focus on AMP in the succinct and systematic regime, in which the data structure stores $\mathbf{M}$ verbatim, uses an additional $r$ bits of redundancy, and must answer queries by probing only a small number of entries of $\mathbf{M}$. Our main conceptual contribution is a general framework for proving probe–redundancy trade-offs for systematic data structures. We introduce the query-with-sketch model and develop a min-entropy-based approach that lifts conditional min-entropy bounds in the absence of redundancy to probe lower bounds in the presence of redundancy. We then establish these min-entropy bounds using problem-specific analytic and algebraic tools, for the downstream applications to AMP and its variants. As a consequence, our results provide new unconditional evidence toward a conjecture of Patrascu and Roditty (2010) on the space required for constant-time set-disjointness queries.

Chatterjee and Sloman proved that a bounded measurable similarity function with sufficiently small average Gromov hyperbolicity admits a tree representation with small mean approximation error. Their argument uses a weighted version of Szemerédi's regularity lemma and does not yield explicit quantitative bounds. Here, we establish a tighter relation between average hyperbolicity and mean tree approximation error. For a similarity function $s:S\times S\to[0,b]$, we prove that $$\operatorname{Tree}(s) \leq (63/e)^{1/3} \sqrt[3]{b^2 \operatorname{Hyp}(s)} \leq 2.8512 \sqrt[3]{b^2 \operatorname{Hyp}(s)}.$$ The proof uses a simple pivoting construction inspired by \KwikCluster. We also discuss the optimal dependence on average hyperbolicity, including a square-root lower bound, and connections with ultrametric fitting.

For a ferromagnetic Ising model on a graph of maximum degree $\Delta\ge3$, we prove a bound of order $\sqrt n$ on every row of the influence matrix at the tree uniqueness threshold. The estimate is uniform in the degree, the external fields, and all pinnings. More generally, if the couplings are bounded by $\beta$ and $\varepsilon=((\Delta-1)\tanh\beta-1)_+$, the bound is $C(\sqrt n+n\varepsilon)$. The proof combines a pointwise cavity bound with a positive-series magnetization tilt and the field comparison theorem of Ding, Song and Sun. The critical estimate removes the logarithm in recent general graphical bounds for the ferromagnetic case. As a consequence, zero-field single-site Glauber dynamics mixes in polynomial time throughout the supercritical window $\varepsilon=O(\sqrt{\log n/n})$, with the polynomial degree depending on the window size.

The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, and each vertex has a capacity. The goal is to find a maximum weight subset of edges such that, at each vertex, the total demand of the incident selected edges does not exceed the vertex capacity. Parekh [IPCO 2011] proved that, if each edge is individually feasible, the natural LP relaxation for demand matching has integrality gap at most $3$, yielding a $3$-approximation algorithm. This bound is tight for the natural LP relaxation, matching the lower bound of Shepherd and Vetta [Math. Oper. Res. 2007]. We present a randomized $(3/2 + \sqrt{2} + \varepsilon) \approx (2.914 + \varepsilon)$-approximation algorithm for the demand matching problem for every $\varepsilon > 0$, giving the first approximation ratio strictly better than $3$. For bipartite graphs, we obtain a randomized $(2 + \varepsilon)$-approximation algorithm for every $\varepsilon > 0$. Both algorithms run in time polynomial in $1/\varepsilon$ and the input length. Our algorithms use a strengthened LP relaxation based on intersecting the integral knapsack polytopes associated with the vertices, together with a multiple-choice generalization. As a key ingredient, we prove the existence of a $(q, 1/(1+q))$-balanced contention resolution scheme for the integral knapsack polytope for every $q \in [0, 1]$, which may be of independent interest. The balance guarantee $1/(1+q)$ is tight in the worst case over all knapsack instances.

Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph $G$. To begin with, the defender places $k$ guards on vertices of $G$. The attacker, on their turn, can choose an edge $e$ not already occupied at both endpoints to "attack". The edge $e$ is defended if a guard moves along the edge $e$. The defender, on their turn, can move any subset of guards. A guard can only move to a neighboring vertex. The minimum number of guards needed to indefinitely defend against any sequence of attacks is called the eternal vertex cover number, generalizing the classic vertex cover number. Determining this number is NP-hard in general, motivating the study of parameterized and approximation algorithms. The problem is known to be FPT when parameterized by the cover number, but structural parameters remain relatively unexplored in the literature. In this work, we explore structural parameterizations for EVC. We show that EVC is FPT parameterized by the cluster vertex deletion number, which generalizes the previously studied parameterization by vertex cover number. We next study the problem parameterized by vertex integrity, which is the smallest number of vertices we need to delete from $G$ so that the resulting graph is a disjoint union of constant-sized components. We first show that Eternal Vertex Cover is XP parameterized by vertex integrity. Then, we develop a polynomial-time approximation algorithm, which computes an additive $6k+1$ ($g(k)$) approximation, where $k$ is equal to the cluster vertex deletion number (vertex integrity). Finally, we show a FPT algorithm for when the deletion set produces "nice" connected components, which are components that are bounded in size and satisfy a technical condition.

The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable decisions. Singla (2026) recently gave a $4$-competitive algorithm for arbitrary matroids using only the number of elements and independence queries on already-arrived elements. Following his approach of maintaining a dynamically updated reference set, we introduce random deletions and a time-dependent acceptance rule, improving the competitive ratio to $C_*\approx3.1462$ in the same information model, where $C_*-\log C_*=2$. Our ordinal algorithm accepts every element of a fixed canonical optimum with probability exactly $1/C_*$ and uses $O(n^2)$ independence queries. The algorithm maintains a greedy reference solution, protects only accepted elements, and randomly deletes unaccepted reference-basis elements. A time-dependent acceptance rule makes the accepted set, conditional on the reference set, an independent thinning of its greedy basis. The resulting guarantee has a direct analytic proof.

The $\textit{Colored Knapsack Problem}$ (ColKP) generalizes the classical Knapsack Problem by partitioning the items into color classes and requiring the selected items to admit an ordering in which consecutive items have different colors. The problem is weakly $\mathcal{NP}$-hard and admits two pseudo-polynomial dynamic programming (DP) algorithms proposed in the literature. These two DP algorithms have worst-case running times $O(b \, n^4)$ and $O(b^2 \, n^3)$, respectively, where $b$ is the knapsack capacity and $n$ is the number of items. We develop the first approximation algorithm for the ColKP. By rounding an optimal basic solution of the linear programming relaxation of its natural integer programming formulation and repairing color feasibility, we obtain a linear-time approximation-algorithm whose worst-case performance ratio is $1/3$. We then reformulate both DP algorithms so that profit, rather than knapsack capacity, indexes their pseudo-polynomial dimension, and combine them with profit scaling to obtain two fully polynomial-time approximation schemes (FPTASs). The first FPTAS runs in $O(n^5/\varepsilon)$ time for nonnegative profits and in $O(n^6/\varepsilon)$ time for arbitrary integer profits. The second FPTAS runs instead in $O(n^5/\varepsilon^2)$ and $O(n^7/\varepsilon^2)$ time, respectively. The approximation guarantee, along with new structural insights, provides the bounds needed to control the scaled profit range and establish these running times.

In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of $\eta + \varepsilon$ where $\eta$ is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than $2\eta + \varepsilon.$ Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). In this paper, we resolve this problem and give such an algorithm. Perhaps surprisingly, our techniques make crucial use of various types of no-regret learners. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits sandwiching polynomials with respect to hypercontractive distributions. As one consequence, we give the first polynomial-time algorithm for robustly learning a halfspace with respect to Gaussian marginals that achieves error $\eta + \varepsilon$ for any constant $\varepsilon$.

The Binary Tree Mechanism is a standard algorithm for differentially private continual counting, but its asymptotic optimality under pure differential privacy has remained unresolved since its introduction. We resolve this question. For fixed $0 < \varepsilon \le 1$, we prove asymptotically tight lower bounds of $\Omega(\log^2 n)$ for worst-case expected $\ell_\infty$ error and $\Omega(\log^3 n)$ for mean and maximum per-coordinate expected squared error. These bounds hold for arbitrary mechanisms, even when the entire stream is available in advance. The same lower bounds hold under approximate differential privacy whenever $\delta\le n^{-c}$, for any fixed $c>0$. Our lower bounds match the Binary Tree Mechanism instantiated with Laplace noise, establishing its asymptotic optimality under both pure differential privacy and approximate differential privacy in the standard regime of $\delta \ll1/n$. Our proof uses a single hard distribution with a bounded exponential score on a tree. A simple modification of the score allows the same framework to establish tight lower bounds for all three error measures.

We study an $\varepsilon$-differentially private synthetic measure for $n$ points in $[0,1]^d$ by applying the existing PrivTree algorithm to construct an adaptive binary partition and then privately releasing its leaf masses. We consider the worst-case data model without any sampling or population-distribution assumption. The 1-Wasserstein error of the synthetic measure is $\widetilde O_d((\varepsilon n)^{-1/d})$ for $d\ge2$, which is optimal compared to the minimax lower bound up to a logarithmic factor. Moreover, for $d\ge3$ and $2<s\le d$, if the data set has covering number at most $Ar^{-s}$ over the relevant finite range of scales $r$, the expected error improves to $\widetilde O_{d,s}((\varepsilon n)^{-1/s})$. Thus the rate depends on a finite-scale intrinsic dimension rather than the ambient dimension, without requiring the recovery of a low-dimensional manifold. We also introduce a shifting technique to further avoid the exponential dependence of the constant on the ambient dimension $d$.

A linear sketch is a randomized linear mapping of a vector $v$ to a lower dimensional sketch vector, designed to preserve relevant information about $v$. We consider sketches of vectors $v \in Z^u$ (for $u \in N$), designed for exact recovery of $v$ from its sketch. Concretely, our Stuffed IBLT is a linear sketch configured with a capacity $n \in N$ and a multiplicity limit $L \in N$ and will recover $v$ with high probability whenever $||v||_0 \leq n$ and $||v||_\infty \leq L$. The sketch can be maintained efficiently under unrestricted updates to $v$, i.e., $v$ is not subject to any constraints in between decoding requests. This makes the sketch useful for streaming algorithms and for solving the (multi)set reconciliation problem. For any positive constants $c$, $\epsilon$, and for large enough $n$ and $u \geq n^{1+\Omega(1)}$, the space usage of a Stuffed IBLT is within a factor $1+\epsilon$ from the information-theoretic optimum while allowing updates in constant time, and decoding in time $O(n)$ with failure probability $n^{-c}$. This improves the space/time/error probability trade-off over all prior constructions with similar functionality, including the Invertible Bloom Lookup Table (IBLT). The performance of the Stuffed IBLT is essentially the best we could hope for, up to the dependence on $c$ and $\epsilon$. We make the dependence on these parameters explicit, and further show a lower bound demonstrating that the dependence on $c$ is optimal within the class of peeling-based approaches. Our improvement comes from a careful combination of Walzer's spatial coupling technique (SODA '21), the purity heuristic of Houen, Pagh, and Walzer (SOSA '23), and backyarding (Belazzougui, Kucherov, and Walzer, ESA '24; Fleischhacker, Green Larsen, Obremski, and Simkin, ICALP '24), allowing us to eliminate bottlenecks of past approaches.

Given vectors $v_i \in {\mathbb R}^d$, we consider the problem of choosing a set $I$ independent in a partition matroid in order to maximize the determinant $\det (\sum_{i \in I} v_i v_i^T)$. Our main result is a polynomial-time approximation algorithm that finds a solution of value $det ( \sum_{i \in I} v_{i} v_{i}^T) \geq e^{-O(d)} OPT$, where $OPT = \max_{I^*} det ( \sum_{i \in I^*} v_{i} v_{i}^T)$. For partition matroids of rank $m \leq d$, we give a similar result for approximating the $m$-dimensional volume spanned by the chosen vectors, within a factor of $e^{O(m)}$. This matches earlier known algorithms that estimate the optimal value but do not find the corresponding solution, up to a constant in the exponent. Similar to these estimation algorithms, our algorithm is based on the saddle-point relaxation proposed by Nikolov and Singh. A new ingredient is a randomized transformation based on $1/2$-stable distributions, which converts the saddle-point relaxation into a more convenient multilinear relaxation.

This paper is the first work at the intersection of game theory and property testing, giving algorithms and lower bounds for efficiently testing whether an allocation mechanism is incentive compatible (IC). We propose distinguishing whether a mechanism is $\epsilon$-far from being IC, i.e., when it observes many monotonicity "violations." Conceptually, inspired by the literature on Boolean function monotonicity testing, we construct a tester for discrete single-parameter allocation rules. Technically, our work is the first to consider monotonicity testing of vector-valued functions on the hypergrid. We give a $\tilde{O}(n/\epsilon)$-query algorithm to test whether a function (representing n-player allocation mechanisms) is coordinate-wise monotone versus $\epsilon$-far from it. We also show a matching lower bound: the class of coordinate-wise monotone vector-valued functions on a Boolean hypercube or hypergrid requires $\tilde{\Omega}(n/\epsilon)$ queries to test whether it is $\epsilon$-far from monotonicity, and this holds even if the tester is two-sided and allowed to make adaptive queries. Finally, we extend our upper bound to and give a tester of the same query complexity for pricing functions of allocation mechanisms. This requires overcoming the technical challenge that the path in function space to the closest IC mechanism may involve interdependent changes to both the price and the allocation rule.

We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed $\varepsilon>0$, we give a randomized polynomial-time $(2+\varepsilon)$-approximation, improving the previously best known factor of $10/3$. Our algorithm extends the cluster-LP framework for unweighted correlation clustering to pseudometric weights. The weighted setting requires controlling both the total weight of admissible pairs and the weighted error in pairwise marginals. Our spectral preclustering preserves a near-optimal solution while bounding the total admissible weight by $\operatorname{poly}(1/\varepsilon)\mathrm{OPT}$, where $\mathrm{OPT}$ is the optimal clustering cost. An aggregated Ptolemy-type inequality yields a degree-product bound and a warm start for random walks within witness clusters, allowing the construction to use walks of constant length. We sample clusters from a bounded sub-cluster relaxation using correlated rounding with a randomized stopping time. An entropy bound and the triangle inequality charge the weighted marginal error to the admissible pairs rather than to the total input weight. Repeated sampling and atom-wise coverage corrections produce an explicit feasible cluster-LP solution supported on polynomially many clusters, with value at most $(1+\varepsilon)\mathrm{OPT}$. After rescaling $\varepsilon$, factor-$2$ rounding gives the stated approximation guarantee.

Efficient resource use in packing and assembly-line applications requires decisions that jointly account for capacity and precedence constraints. The strongly NP-hard bin packing problem with generalized precedence constraints (BPP-GP) models such decisions by minimizing the number of ordered, capacitated bins required to pack weighted items, even when precedence requirements span multiple bins. Existing exact algorithms primarily focus on classical special cases, whereas general BPP-GP has been addressed only via compact integer models and heuristics, with no efficient open-source exact solver. We present PrecPack, a unified exact solver that extends branch-bound-and-remember (BBR) to arbitrary nonnegative precedence weights and naturally specializes to the classical cases. Generalized states capture restrictions that remain active across future bins, which are addressed through branching, dominance, and conflict-aware lower bounds. Root column generation uses fixed-point arithmetic to compute numerically valid dual bounds for pruning or to prove optimality. To support reuse and verification, we provide common programming and command-line interfaces, independent assignment checking, explicit termination statuses, and reproducible batch execution; the core procedures require no commercial software. In same-machine, single-threaded comparisons on classic assembly-line benchmarks, more instances are proven optimal, and average computing times are substantially reduced relative to leading source-available BBR implementations. Further comparisons with published benchmark results for bin packing with precedence constraints and BPP-GP also show that more instances were proved optimal and that reported average gaps were smaller on most benchmark sets. PrecPack is released under the MIT License at https://github.com/Sunkanghong-Wang/PrecPack.

The classical Weisfeiler-Leman algorithm (also known as the $2$-dimensional Weisfeiler-Leman algorithm) is a simple combinatorial algorithm that was originally designed as a heuristic for the graph isomorphism problem. However, it has also numerous connections to other areas such as algebraic graph theory, logics, proof complexity, combinatorial optimization and machine learning. We prove that the classical Weisfeiler-Leman algorithm terminates after $5(n-1)$ iterations. This improves over the previous best upper bound of $O(n \log n)$ by Lichter, Ponomarenko and Schweitzer [LICS 2019], and asymptotically matches the known lower bound of $\Omega(n)$ by Fürer [ICALP 2001]. Additionally, building on our results for the $2$-dimensional case, we obtain an improved upper bound of $O(n^{k-1}/(k-2)! + n^{k-2})$ on the number of iterations performed by the $k$-dimensional Weisfeiler-Leman algorithm, for every $k \geq 3$. Our arguments actually hold for a larger class of sequences of colorings of $k$-tuples; in this larger class our upper bounds are essentially tight for all $k \geq 3$.

We study online allocation problems where $n$ requests over $m$ resources arrive in an adversarial order and must be served immediately and irrevocably. This framework captures both Online Resource Allocation, where the goal is to maximize value subject to resource budgets, and Online Load Balancing, where the goal is to minimize the makespan. We seek $(1\pm\epsilon)$-competitive algorithms in the large-budget or large-makespan regime. We consider a sampling model that generalizes the following two well-studied sampling models. In the Single-Sample Prophet Inequality ($\mathsf{SSPI}$) model, request $t$ is drawn from an unknown distribution $\mathcal{D}_t$, and the algorithm is given one independent sample from each $\mathcal{D}_t$ before the online phase. In the $p$-$\mathsf{Sample}$ model, the requests are adversarial, but a uniformly random $p$-fraction is revealed upfront as training data. Although near-optimal algorithms are known in the easier random-order model ($\mathsf{RO}$), where the requests arrive in a uniformly random order, prior algorithms for $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$ were problem-specific and incurred substantially worse dependencies on $\epsilon$, $m$, and $n$. Our main contribution is a general framework that converts $\mathsf{RO}$ algorithms into algorithms for the $p$-$\mathsf{Preview}$ model, a model that generalizes both $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$. As consequences, we obtain near-optimal bounds for Online Resource Allocation, generalized Online Load Balancing, and online mixed packing-covering problems in these adversarial-order sampling models, significantly improving the bounds of [Ghuge, Singla, Wang (STOC'25)] and [Gupta and Molinaro (SODA'26)].

Estimating the second frequency moment ($F_2$) of an underlying frequency vector is a fundamental problem in the streaming model. While recent work by Braverman and Zamir [STOC 2025] resolved the space complexity for constant failure probability in the insertion-only model, the optimal dependence on the failure parameter $\delta$ remained open. We close this gap by proving a tight high-probability lower bound of $\Omega\left(\frac{1}{\varepsilon^2}\log\frac{1}{\delta}\,\log\frac{\varepsilon\sqrt{n}}{\log(1/\delta)}\right)$ for $(1\pm\varepsilon)$-approximate $F_2$ estimation. The key challenge is the failure of prior multi-scale direct sum arguments under noise sensitivity. We introduce a noise-robust communication primitive, Exam Mostly Set Disjointness, and prove an $\Omega\left(\frac{m}{t}\log\frac{1}{\delta}\right)$ one-way lower bound. Embedding this into a multi-scale reduction yields the correct $\log(1/\delta)$ dependence. We also give two complementary algorithms under natural structure assumptions. For streams with frequency bound $B$, we design a subsampling method using continuous $F_0$ tracking that replaces a $\log(n)$ factor with $\text{polylog}(B)$. For $k$-sparse streams, we develop a two-stage sketch using approximate Morris counters, replacing $\log n$ with $\log k$ and achieving a further $\log\log m$ dependence on stream length.

We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with $\|\sum_i s_i H_i\|\le 13\|\sum_i H_i^2\|^{1/2}$. As a corollary, for vectors $v_i$ with $\sum_i v_iv_i^*=I$ and $\|v_i\|^2\le\delta$, the signs yield a partition $[N] = S_1 \cup S_2$ such that each part satisfies $\|\sum_{i \in S_j} v_i v_i^* - \frac{I}{2}\| \leq \frac{13}{2}\sqrt\delta$ for $j = 1,2$. This gives a deterministic polynomial-time algorithm for the Kadison–Singer problem, in Weaver's equivalent discrepancy-theoretic $\mathsf{KS}_2$ formulation, with a universal constant.

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - \epsilon$ are $(p, O(q H_q(p)/\epsilon))$-list decodable with high probability for all values of $p, q, \epsilon$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/\epsilon$ due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for $q > 2$ since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \ln n / {\ln \ln n}$, both in expectation and with probability $1-o(1)$. This nearly matches the lower bound of $\ln n / {\ln \ln n}$. Previously, only a polylogarithmic upper bound was known for $q > 2$, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set $S$ by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside $S$ than outside.

Bin packing asks whether a collection of items can be packed into at most a given number of bins of a given capacity. We consider the high-multiplicity setting with $d$ distinct item sizes, in which both the item sizes and the number of items of each size are encoded in binary. Goemans and Rothvos (JACM 2020) gave an XP algorithm parameterized by $d$. Whether this problem is fixed-parameter tractable (FPT) in $d$ has remained a central open problem. We resolve this question by giving a deterministic $O^*(2^{d^{O(d)}})$-time algorithm. We formulate bin packing as an integer linear program (ILP) with at most $(d+1)d^d$ variables. A bin configuration records the number of items of each type in one bin. We partition these configurations by their coordinate remainders modulo $d$. For each class, we use one variable for the bin count and $d$ variables for the total item counts. The convex hull of each class has the integer decomposition property, which guarantees that every feasible ILP solution corresponds to a packing.

A regular expression with backreferences (rewb) specifies a set of strings formed by characters combined with concatenation, union, star operators, and backreferences. A backreference consists of a capturing group $(\cdot)_i$ and a reference $\backslash i$. The substring matched by the reference must match the substring matched by the corresponding capturing group. Given a rewb $R$ and a string $Q$, the rewb matching problem is to decide whether $Q$ is one of the strings specified by $R$. In full generality, rewb matching is NP-complete, but efficient solutions exist for various subclasses. In the paper, we focus on rewb containing a single capturing group and $k$ references. For this class, Uezato~[CPM 2026] gave an $O((k n^2 m^2)$ time and $O(n^2m^2)$ space algorithm, where $m$ is the length of the regular expression $R$ and $n$ is the length of the string $Q$. For the special case of $k=1$, Nogami and Terauchi~[MFCS 2025] gave an $O(n^2m^2)$ time and $O(n+ m^2)$ space algorithm. On the other hand, Nogami, Nakamura, and Terauchi~[arXiv 2026] gave a conditional lower bound, showing that we cannot solve the problem in $O(n^{2-\epsilon} \mathrm{poly}(m))$ for any $\epsilon > 0$ assuming the orthogonal vector hypothesis. Our main result is a new algorithm that runs in $O(n^2m)$ time and uses $O(nm)$ space. This improves the above results (by a factor of $km$ and $m$, respectively) and the former's space bound (by a factor of $nm$). We also show how to extend our algorithm to handle a slightly more general class of ordered and single-nested rewbs.