Papers

Eulerian digraphs retain the directional structure of general digraphs while exhibiting a symmetry of cuts reminiscent of undirected graphs. We show that this symmetry extends beyond individual cuts to two fundamental techniques in parameterized algorithms for undirected cut problems: treewidth reduction and recursive understanding and randomized contractions. Both of these techniques have proved useful for dealing with undirected graph cut problems as each of them reduces the problem at hand on general undirected instances to ones that have bounded treewidth or that are highly connected, respectively. In this work we prove an edge-cut analogue of the treewidth-reduction theorem of Marx, O'Sullivan, and Razgon [ACM TALG 2013], and an Eulerian analogue of the reduction of CMSO model checking to unbreakable instances due to Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP 2018]. Both these results allow us to reduce several problems on general Eulerian digraphs to Eulerian digraphs whose underlying undirected graph has bounded treewidth, or to Eulerian instances that are highly connected, thus bringing to Eulerian digraphs two fundamental tools from the undirected parameterized cut toolkit for which no counterparts are known on arbitrary digraphs. Beyond their structural significance, these results have substantial algorithmic consequences: they yield FPT algorithms for several directed cut problems that are W[1]-hard in general. We show that Directed Multicut and Directed Edge Odd Cycle Transversal are FPT on Eulerian digraphs when parameterized by the solution size and the number of terminal pairs, and just the solution size, respectively. This is in sharp contrast to general digraphs, where the first problem is W[1]-hard even for 4 terminal pairs, and the second is W[1]-hard in general. We also obtain FPT algorithms for Directed Edge Multiway Cut-Uncut and Directed Steiner Cut.

We study the two-player communication complexity of the Coin problem. Here, two players, denoted Alice and Bob, are given up to $n$ individual i.i.d. random coins, and asked to output whether there are more heads or tails. An immediate approach is for Alice to send Bob her exact numbers of heads and tails, yielding a deterministic protocol with one-way communication cost $O(\log n)$ bits. Indeed, this is provably optimal in the related multi-player and streaming settings [Braverman, Garg, Woodruff, FOCS'20]. Our contribution is to show that this is not the right answer in the one-way two-player setting. Instead, we prove a $\Omega(\log\log n)$ bit lower bound for the constant error-rate regime, and a $\Omega(\log(1/\delta))$ bit lower bound for arbitrarily small error rates, $\delta \geq n^{-0.1}$. We also complement these with a tight one-way protocol using $O(\log\log n + \log(1/\delta))$ bits of communication. Unlike the previous works, our lower bounds avoid intricate direct information-theoretic arguments. Instead, our $\Omega(\log(1/\delta))$ bound is via a standard fooling-set style argument, whilst our $\Omega(\log\log n)$ bound is via a novel yet simple reduction from the Gap-Greater-Than problem. This reduction is our main technical contribution, and can be seen as loosely inspired by the Robust Communication Complexity arguments of [Chakrabarti, Cormode, McGregor, STOC'08]. Finally, we also show that our constant-error lower bound and protocol can be adapted to the multi-round setting: up to polynomial factors in $r$, the $r$-round communication complexity of the coin problem is $\Theta\left((\log\log n)^{1/r}\right)$ bits.

We study the vehicle routing problem (VRP) with stochastic demands, where each client has an independent demand with a known distribution, and its realized demand is observed only on the first visit. We consider a priori and restocking policies that fix the client order before observing demands and serve each client's entire demand before first visiting the next. Gupta, Nagarajan, and Ravi (Oper. Res., 2012) developed randomized a priori $(\alpha+1)$-approximation and $(\alpha+2)$-approximation algorithms for splittable and unsplittable deliveries, respectively, where $\alpha$ is the approximation ratio of a metric traveling salesman problem (TSP) algorithm. We improve these approximation ratios to $2$ and $3$ by using their replenishment rules with a TSP tour constructed via matroid parity. We also obtain deterministic a priori $(2+\varepsilon)$-approximation and $(3+\varepsilon)$-approximation algorithms by compressing the distributions of cumulative demands to select an initial stock in polynomial time. All guarantees are relative to the general adaptive optimum. We then establish matching lower bounds of $2$ and $3$ that hold even for the more general class of randomized restocking policies. Finally, we apply our matroid-parity construction to improve approximation ratios for several VRP variants with deterministic demands.

We present new algorithms for approximate shortest path computation in weighted undirected graphs within the Massively Parallel Computation (MPC) model. Specifically, we construct an $a$-approximate Single-Source Shortest Path (SSSP) oracle: Given a query consisting of a source vertex $u \in V$, the oracle returns $a$-approximate distances $\delta(u,v)$ for all $v \in V$. Fix an $n$-vertex weighted undirected graph. We consider two regimes of the MPC model: the near-linear regime, where each machine has $\tilde{\Theta}(n)$ memory, and the heterogeneous regime, where all machines have $\Theta(n^\gamma)$ memory for some constant $\gamma\in (0,1]$, except for a single machine with $\tilde{\Theta}(n)$ memory. We develop randomised algorithms that construct $O(1)$-approximate SSSP oracles in $O(\log\log n)$ rounds in the near-linear regime and in $O(\log^2\log n)$ rounds in the heterogeneous regime. These oracles answer distance queries in $O(1)$ rounds. Our results improve upon the recent work of Dory and Matar (SPAA 2024) which, for the same total memory, requires $\left(\log\log n\right)^{2+O(1/\gamma)}$ rounds and applies only to unweighted graphs in the heterogeneous setting. We say that $\tilde N_k(u)$ is the approximate $k$-nearest neighbourhood of a vertex $u$ if there exists an approximate distance estimate $\delta$ such that $\tilde N_k(u)$ consists of the $k$ vertices closest to $u$ according to $\delta$, breaking ties by vertex ID. The main technical ingredient is a new method for efficiently computing approximate $n^{O(\gamma)}$-nearest neighbourhoods in the heterogeneous MPC model in $O(\log^2\log n)$ rounds.

Submodular maximization arises in a wide range of combinatorial optimization problems and has been extensively studied from the perspective of approximation algorithms. For maximizing nonnegative, non-monotone submodular functions subject to a matroid constraint, randomized algorithms achieve a $0.401$-approximation, whereas obtaining comparable deterministic guarantees remains challenging. In this paper, we present a deterministic $0.401$-approximation algorithm in the exact value and independence oracle model, improving upon the previous deterministic guarantee of $(0.385-\varepsilon)$ \cite{ChenGLSZ2026}. Our algorithm builds on the extended multilinear extension and provides a deterministic implementation of the recursive guided framework underlying the randomized $0.401$-approximation algorithm. The main technical ingredient is a direction oracle supported on at most two partitioned matroid bases. This oracle simultaneously satisfies the growth condition required by the extended-multilinear update and an approximate stationarity condition needed to construct the recursive guides. The resulting finite-support representation enables exact evaluation of the relevant expectations and marginal values without random sampling. The algorithm uses polynomially many value- and independence-oracle queries.

Inspired by Steinitz's celebrated result (1913) and recent online vector-balancing results of Kulkarni et al. (2024) and Aden-Ali (2026), we introduce the online Steinitz problem: $T$ vectors in $\mathbb R^d$, each of $\ell_2$-norm at most $1$ and with total sum zero, arrive one at a time and must be assigned immediately and irrevocably to unused positions of an array. The goal is to keep every prefix sum of the resulting order small. We first obtain deterministic prefix-discrepancy bounds of $O(\log T)$ for $d=1$ and $O(\sqrt T)$ for $d\ge2$. Our main contribution is a general reduction that converts deterministic and randomized online vector-balancing algorithms, which assign signs to arriving vectors, into online ordering algorithms. Combined with recent vector-balancing results, this yields a randomized algorithm with prefix discrepancy $O(\log T+\sqrt{d\log T})$ and running time $O(dT\log T)$. The guarantee holds with high probability against an oblivious adversary. The reduction also gives bounds for sparse vectors and extends to inputs in arbitrary compact convex bodies. Finally, we prove matching lower bounds in both the deterministic and randomized cases.

In the tensor principal components analysis (tensor PCA) problem, we are asked to recover an unknown vector in $\{\pm1\}^N$ from a noisy observation of its $k$-th tensor power, for a fixed $k\ge3$. Tensor PCA exhibits a well-studied information-computation gap: global algorithms such as spectral methods and sum-of-squares work above an algorithmic threshold, below which we know matching lower bounds (against these and some other restricted models of computation). In contrast, local algorithms such as Markov chains were only known to succeed from a random initialization at a polynomially larger signal-to-noise ratio, and were believed to be inferior to global algorithms for tensor PCA. We show that Glauber dynamics, when supplemented with annealing and ergodic averaging, achieves polynomial-time strong recovery above the algorithmic threshold from a uniformly random initialization, demonstrating that local Markov chains can succeed all the way down to the algorithmic threshold from an uninformative cold start.

We study the recovery of the hidden vertex correspondence between two correlated dense random geometric graphs. Each graph is generated from $n$ latent unit vectors in $\mathbb R^d$; the vectors $u_i^A$ and $u_i^B$ of corresponding vertices satisfy $\langle u_i^A,u_i^B\rangle=\rho$, and the vertex labels of the second graph are permuted by an unknown permutation $\pi$. For every fixed correlation $\rho\in(0,1]$ and every edge density bounded away from zero and one, we give a randomized polynomial time algorithm that recovers $\pi$ exactly with probability tending to one whenever $d\ge(\log n)^L$, where $L$ depends only on the correlation and the density bounds. The algorithm assigns to each vertex a signature formed by counting decorated paths with a constant number of seeds. The number of such seeded templates grows exponentially with the path length, with an arbitrarily large constant base, so the resulting statistics amplify an arbitrarily small constant correlation. We control the dependencies created by the latent geometry in two ways: when $d$ is larger than $n/(\log n)^{L_0}$ for a suitable constant $L_0$, by comparing local moments with those of correlated Erdős–Rényi graphs; for smaller $d$, by spectral estimation of the latent geometry combined with a harmonic correction. We also provide low-degree evidence for a tradeoff between the correlation and the computational cost.

We present the first dynamic maximal independent set (MIS) of a graph with $n$ vertices and up to $m$ edges under edge updates in the prediction model, where a predicted update sequence is available for offline preprocessing before the real updates arrive online. We consider the incremental (insertion-only), decremental (deletions-only), and fully dynamic (insertions and deletions) models. Without predictions, deterministic algorithms need worst-case update time of $O(n)$ for decremental and $O(m)$ for incremental and fully dynamic settings. Bernstein et al.~[SODA26] proved under the combinatorial BMM conjecture, combinatorial incremental algorithms against an adaptive adversary require $\Omega(n^{1-o(1)})$ amortized update time. We present deterministic incremental, decremental, and fully dynamic algorithms whose update times depend on the prediction error. This error is measured by the number $\eta_e$ of mispredicted updates, and by the number $\eta_v$ and total degree $\eta_v^*$ of vertices whose MIS membership was mispredicted. With $O(mn)$ preprocessing, our decremental and incremental algorithms achieve worst-case update times $O(\eta_v)$ and $O(\eta_e+\eta_v^*)$, respectively. Our fully dynamic algorithm achieves $O(\eta_e+\eta_v^*)$ worst-case update time with $O(un)$ preprocessing for $u$ updates. We also give space-efficient variants using $O(m)$ space for the decremental and $O(m\sqrt{m})$ for the incremental setting, at the cost of a logarithmic overhead in worst-case update time. Our algorithms satisfy consistency, robustness, and smooth degradation, the required properties of algorithms with predictions. They can also utilize the general error correction framework of Khan et al.~[Arxiv26], relaxing the error measures from first point of difference to prefix matching (for partially dynamic) and set edit distance (for fully dynamic), maintaining the same bounds.

We give a deterministic distributed algorithm for $(\Delta+1)$-coloring an $n$-node graph of maximum degree $\Delta$ in $O(\sqrt\Delta+\log^* n)$ rounds in both the LOCAL and CONGEST models. More generally, $(\deg+1)$-list coloring with lists from a color space of size $C\geq\Delta+1$ can be solved in $O(\sqrt\Delta\log(1+C/\Delta)+\log^* n)$ rounds; in CONGEST, we assume $C\leq n^{O(1)}$. The algorithm combines Barenboim's polynomial coloring procedure with arbdefective decompositions, degree reduction, and a short family of hash functions. Using the polynomial procedure in the degree-reduction framework already gives an $O(\sqrt\Delta\log\Delta+\log^* n)$-round algorithm when $C=O(\Delta)$. Hashing adapts the color space to the current degree and removes the logarithmic factor. We prove the existence of the hash family by the probabilistic method and compute it by deterministic exhaustive search, using unrestricted local computation. We also give an explicit variant based on lossless expanders that avoids this search and achieves $O(\sqrt\Delta+\log^* n)$ rounds for $C=O(\Delta)$.

In the context of graph reconstruction studies, this paper addresses the problem defined as follows: given a sample of vertex-coloured graphs, each associated with a number, does there exist a connected graph containing exactly the given number of induced subgraphs isomorphic to each graph in the sample, such that every edge of the solution graph is included in at least one of these subgraphs. This paper first shows that this problem is $\Sigma$______-complete. The associated optimisation problem is to determine the minimum number of vertices in a solution graph, if one exists. For instances consisting of two paths, we prove NP-completeness in general and give a polynomial-time dynamic programming algorithm when one path is monochromatic.

We study the following simultaneous embedding problem: Given k graphs on the same vertex set with the same pairwise intersection, do they admit planar drawings that coincide on their shared graph? We establish fixed-parameter tractability with respect to the vertex integrity of the union graph (that is, the union of the input graphs) plus k, resolving an open question and generalizing the known algorithm parameterized by vertex cover number plus k. Our main technical contribution on the way towards this result is the extension of the recently introduced Ramsey pruning technique beyond ordering problems. Finally, we complement our tractability result with a lower bound that establishes NP-hardness when both k and the pathwidth of the union graph are bounded by constants, ruling out a generalization of our main result to path- or treewidth.

Quantization has emerged as one of the primary techniques for reducing the memory footprint of large language models during inference. A prominent example is Quantized Johnson$-$Lindenstrauss (QJL), which compresses KV caches using 1-bit asymmetric quantization while approximately preserving the inner products required by the attention mechanism. Recent theoretical and practical work aims at replacing the dense Gaussian projections used by the aforementioned transforms with more structured embeddings $-$ such as compositions of randomized Hadamard transforms $-$ while retaining the same embedding dimension. In this paper, we introduce two constructions based on a composition of randomized Hadamard transforms, albeit with a Gaussian rather than Rademacher diagonal in the second stage. The first adds Gaussian dithering to smooth the quantizer, while the second inserts a random permutation to regularize the covariance structure of the resulting Gaussian measurements. We prove embedding-dimension and running-time guarantees analogous to those of Fast JL in the non-quantized setting. The first construction achieves $m=O(\varepsilon^{-2}\log^2(d/\delta))$, while the second achieves $m=O(\varepsilon^{-2}\log(d/\delta))$ under a restriction on $m$. Both constructions can be applied in $O(d\log d)$ time.

The Tarski fixed-point problem asks for a fixed point of a monotone map on a $k$-dimensional grid lattice of width $n$ and has applications in game theory, economics, and verification. Substantial gaps remain between the known upper and lower bounds on its quantum query complexity. We prove two hardness bootstrapping theorems for quantum query lower bounds. Starting from a hard instance family whose instances have pair-wise incomparable unique fixed points, and a lower bound established by the nonnegative adversary method, we bootstrap this lower bound by (i) a factor of $\Omega(t)$ when the dimension is multiplied by $t$ and the width remains unchanged, and (ii) a factor of $\Omega(\log m)$ when the width is multiplied by $m$ and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an $\Omega(k\log^2 n)$ lower bound for $k\geq 4$, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant $\alpha>0$, there exists a constant $\delta(\alpha)>0$ such that $Q_\epsilon(\text{Tarski}(n,k))=\Omega(kn^{\delta(\alpha)})$ whenever $k>n^\alpha$, and in particular, an $\Omega(kn^{0.0072})$ lower bound for $k>n^{2/203}$, the first lower bound with simultaneous linear dependence on the dimension and polynomial dependence on the width; and (iii) a superpolynomial lower bound of $(k/\log k)^{\Omega(\log k)}$ for exponentially wide grids, where $n=2^{\Theta(k)}$. The last result rules out a route to polynomial-time algorithms for simple stochastic games and ARRIVAL through generic polynomial-query black-box Tarski solvers.

Serving stacks for large language models manage context through four recurring mechanisms: incremental edits to a growing context, branching and snapshotting for tree search, identification of reusable prefixes for KV-cache reuse, and encoding of repeated segments. Each mechanism is served today by a different specialist structure. We show that all four reduce to a single persistent weight-balanced rope whose every node carries a polynomial hash of its subtree over a Mersenne prime, so that the structure supports logarithmic edits and logarithmic verified content-identity queries at the same time. We validate each mechanism with pre-registered, replicated experiments, then compare against a deployed specialist per mechanism: the Ropey editing library, a faithful PagedAttention copy-on-write block table, and the vendored SGLang radix matcher. On workloads that interleave edits with identity queries, Hashrope is net-superior to Ropey by a factor that grows without bound (369.7x at one million characters). Against the radix matcher on a live vLLM stack serving Qwen2.5-7B-Instruct-1M on four A100 GPUs, Hashrope identifies a one-million-token shared prefix exactly and 1.20x faster, at a context length the dense engine cannot even prefill.

In this paper, we present a discrepancy-based approach to cost-preserving rounding under hard constraints. Starting from a feasible fractional solution, our rounding procedure preserves the designated hard constraints, never increases the linear objective, and bounds the error in the remaining constraints by the discrepancy of a suitable column-difference matrix. Our second discrepancy-theoretic result bounds the discrepancy of a matrix in terms of a novel column parameter, called mountain distance. This notion captures ordered structural features of a matrix which are invisible to the classical Beck–Fiala and Komlós column-norm parameters. We show a variety of applications of these two results. In particular, we obtain new results for min-cost unsplittable flows, bounded-turn routing in grids and tori, rainbow prefix hypergraph decomposition, and $2$-multicast scheduling.

We study Coflow Scheduling, introduced by Chowdhury, Zhong, and Stoica (2014). We give deterministic polynomial-time algorithms achieving a $2.77$-approximation without release dates and a $3.17$-approximation with integer release dates. These improve the $3.42$ and $4.36$ guarantees of Rohwedder and Schnaars (2025). Our approach combines two ideas: (1) a novel iterated rounding scheme, and (2) Galvin's list edge coloring method, which is based on the Gale–Shapley stable matching algorithm.

We revisit the online submodular welfare maximization problem (OSW), a vast generalization of numerous well-studied online allocation problems, including online bipartite matching, display ads and AdWords. A natural greedy OSW algorithm achieves a competitive ratio of $1/2$ [LLN06], and $1-1/e$ under i.i.d. arrivals [KPV13]. Both bounds are tight for polynomial-time algorithms unless NP=RP [KPV13]. The information-theoretic limits for OSW, in contrast, remained open. This prompted researchers to ask for tighter upper bounds [Mehta13] or conjecture the existence of better-competitive (slow) algorithms [Huang23, LTX+23, CHS24, Huang2024, HTW24}. We resolve Mehta's question and refute the subsequent conjectures, proving that the greedy algorithm is in fact tight for both adversarial and i.i.d. arrivals, regardless of computation time. Seemingly contradicting recent $(1-1/e)$-competitive fractional algorithms for OSW [HJP+24,Patton26], we show that this impossibility even holds for fractional algorithms, provided their outputs correspond to marginals that are roundable in hindsight. Conceptually, our proofs can be seen as identifying that a bottleneck for OSW, even under (deterministic) adversarial arrivals, is the inherently random notion of correlation gap [ADSY12].

Both the unweighted and weighted variants of caching are cornerstone problems in competitive analysis, with tight randomized competitive ratios of $\Theta(\log k)$, where $k$ is the cache size. We study weighted caching with per-request predictions, where each page request is accompanied by a prediction of the next arrival time of the same page. For unweighted caching, such perfect predictions suffice to implement Belady's offline optimal rule. For weighted caching, however, previous work shows that a logarithmic lower bound persists even with perfect predictions on adversarial request sequences. Stochastic assumptions alone are also insufficient: the classical caching lower bounds already apply to uniform independent requests. In this work, we ask whether combining these two sources of additional information can overcome this barrier, and answer this question affirmatively. Specifically, we develop an efficient, deterministic cache eviction policy that achieves a competitive ratio of $15.75$ using perfect per-request predictions when page requests are drawn independently from an arbitrary, known static distribution in every step, and page costs are arbitrary. Our algorithm's performance degrades gracefully under erroneous predictions: we prove a bound of $O(\min\{1+E,\log k\})$ on the competitive ratio, where $E$ aggregates each page's average prediction error, and may be unknown to the algorithm.

A hereditary graph class has strongly edge-sublinear separators if, for some constant $0 \leqslant b < 1$, every graph in the class with $m$ edges admits a balanced separator of size $\mathcal O(m^b)$. We show that Max Weight Independent Set (MWIS) admits a deterministic quasipolynomial-time approximation scheme (QPTAS) on every such class. In particular, this applies to graphs excluding any fixed graph as an induced minor, by a separator theorem of Korhonen and Lokshtanov [SODA 2024]. Our theorem generalizes the QPTASes for axis-parallel rectangles [Adamaszek and Wiese, FOCS 2013] and polygons [Adamaszek, Har-Peled, and Wiese, JACM 2019], or equivalently for packing connected subgraphs of a planar graph [Pilipczuk, van Leeuwen, and Wiese, Algorithmica 2020]. It also generalizes the QPTAS for MWIS on hereditary classes with strongly sublinear separators measured in vertices [Dvořák, EJC 2018; Dvořák and Lahiri, ESA 2021], as well as the QPTASes for graphs excluding particular induced minors [Chudnovsky et al., arXiv 2025; Bonnet et al., SWAT 2026; Czyżewska et al., arXiv 2026].

Modern inference systems rely on batching to exploit parallel execution and amortize serial execution overheads, but batching creates a fundamental online scheduling tradeoff: serving requests immediately reduces request queuing delay, while waiting can form larger batches that better utilize parallel hardware and improve serving efficiency. We study this tradeoff in a single-server online batching model with bounded batch capacity, fixed batch processing time, and the objective of minimizing total flow time. Our focus is on the value of finite lookahead into future arrivals over a purely online setting for scheduling. We show that the benefits of lookahead depend on the arrival model. In the adversarial setting, finite perfect lookahead has inherent limitations: for any bounded lookahead window, every online algorithm remains separated from the offline optimum by a constant factor. Thus, worst-case arrival sequences can prevent perfect knowledge of future events from fully overcoming online uncertainty. In contrast, under Poisson arrivals in the stable regime, finite lookahead is much more powerful. Although the best distribution-aware online algorithm has a nonzero asymptotic gap from the offline optimum, lookahead closes this gap exponentially fast in the window length. We prove matching upper and lower bounds up to constants in the exponent. Together, these results give a tight characterization of when lookahead can close the online–offline gap, incorporating insights from the competitive analysis of online algorithms into queueing-theoretic steady-state bounds. We also study imperfect predictions, showing that the benefit of lookahead degrades gracefully with prediction error. Simulations on synthetic arrivals and experiments on real request traces support the theory: modest lookahead substantially reduces flow time and brings online batching close to the offline benchmark.

In multi-group learning, a single predictor must perform nearly as well as the best hypothesis in a class on every group in a rich, possibly infinite and overlapping, collection of subpopulations. The known algorithms with the optimal sample complexity keep track of every pair of a group and a hypothesis, which is impossible for the large classes of interest, and the known oracle-based algorithms have a worse rate. We ask whether the optimal rate can be attained by a learner that accesses the classes only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses $\tilde{O}((d_G+d_H)/\varepsilon^2)$ samples and polynomially many calls to a weighted ERM oracle over pairs of a group and a hypothesis, where $d_G$ and $d_H$ are the VC dimensions of the group and hypothesis classes and $\varepsilon$ bounds the excess risk on every group, weighted by its probability. We also show a matching lower bound of $\Omega((d_G+d_H)/\varepsilon^2)$ samples for every learner even with unlimited computation, so oracle efficiency costs no additional samples. We also consider a natural special case in which every input belongs to at most $k$ groups and these groups can be listed. In this case, an ERM oracle for the hypothesis class alone suffices, with $\tilde{O}((d_H+\log k)/\varepsilon^2)$ samples in the agnostic setting and $\tilde{O}((d_H+\log k)/\varepsilon)$ samples when every group has a hypothesis that is correct on it.

In sequential learning, a group of agents sequentially receives a noisy private signal and observes the predictions of prior agents to estimate a hidden ground truth. While extensively studied for binary signals, we formalize and analyze sequential learning when the hidden ground truth is an ordering of $n$ items, and both private signals and inferences involve pairwise comparisons. A key focus in sequential learning is herding, where agents disregard their private signals to follow the crowd. We show that, while local herding in our model may lead agents to make incorrect pairwise inferences, the global hidden order can still be approximated. Specifically, by aggregating all pairwise comparison outputs, the highest-ranked items can be retrieved. We investigate top-$k$ retrieval across three scenarios: (1) passive aggregation, where information is gathered from the social learning process without intervention; (2) strategic selection, where agents choose their pairwise comparisons dynamically; and (3) aggregation with stubborn nodes, where a very small set of stubborn agents, who base their inferences solely on their private signals, join the mechanism. With query complexity as the number of agents needed for a high-probability estimation, we propose top-$k$ retrieval algorithms with query complexities sublinear in $O(n^2)$, the total number of pairs.

Sorting is one of the most basic algorithmic problems. Adaptive sorting algorithms exploit features that make an input easier to sort, often captured by entropy measures. Many such measures have been studied, raising two natural questions: how do they relate to one another, and are there algorithms that are adaptive to them? We complete a hierarchy of relations between previously studied entropy measures and show that the classical measure Reg is a source of this hierarchy. We prove that an existing data structure yields a Reg-adaptive sorting algorithm, thereby achieving the adaptive bounds of every measure in the hierarchy. Following McIlroy's observation that Reg has a mathematically inconvenient definition, we study a slightly weaker but simpler measure, reg. For inputs without duplicates, we show that O(n + log reg) = O(n + log Reg), so this simplification preserves the adaptive bound. Finally, we do algorithms design and introduce SproutSort, a reg-adaptive algorithm in the offline binary search tree (BST) model. SproutSort achieves an access cost of O(n + log reg), making it the most adaptive algorithm in this model to date. We also introduce SkeletonSort, a simple randomised pointer-machine algorithm that sorts distinct keys in expected O(n + log reg) time, offering a considerably simpler implementation of a sorting algorithm this high in the adaptive hierarchy.

We study the problem of fair allocation when agents have dichotomous submodular preferences over groups of, rather than individual, items. These preferences naturally extend existing models, and have a natural interpretation in settings such as course allocation. We show that this seemingly minor extension results in computational intractability barriers: computing a utilitarian or Nash-optimal allocation with item complements is NP-hard. However, when agents' complementary bundles have size at most $k$, there exist poly-time algorithms that compute $\frac1k$-$\texttt{maxUSW}$ allocations and approximate Nash-welfare-maximizing allocations. While PO+EF-1 allocations may not exist in the complementary preference setting, it is possible to compute $\frac1{k+1}$-approximately $\texttt{maxUSW}$ EF-X allocations in polynomial time; furthermore, these allocations offer each agent $i$ a utility of at least $\frac{\texttt{MMS}_i - k}{k+1 + \frac1n}$, where $\texttt{MMS}_i$ is agent $i$'s maximin share guarantee. While the standard dichotomous binary submodular setting admits simple sequential techniques for computing fair and efficient allocations, our results for the complements setting require more complex tools from combinatorial optimization.

We identify the free-facility gaps of greedy online assignment on a cycle with the discrete additive coalescent and use this connection to determine the exact expected assignment cost. The cycle has circumference $n$, with one unit-capacity facility at each integer point and $n$ independent uniform arrivals. Each request is assigned immediately to a nearest free facility. The conditional one-step cost is the sum of squared gap lengths divided by $4n$. A uniform cyclic-order argument identifies the unordered gap process with additive coalescence. The classical Cayley-tree representation then reduces the accumulated cost to a two-vertex distance functional, yielding \[ G_n=\frac n4\sum_{d=0}^{n-1}\prod_{j=1}^{d}\left(1-\frac jn\right) \sim\frac14\sqrt{\frac\pi2}\,n^{3/2}. \] The formula requires a linear number of scalar recurrence steps to evaluate. We also obtain an asymptotic upper bound of $\pi\sqrt3/2$ on the ratio of expected greedy cost to expected offline optimum under this arrival model. An exact rational Bellman calculation shows that greedy is optimal for three facilities but exceeds the optimal online expected cost by $1/512$ for four facilities. Independent exact recurrences and finite tree enumeration provide reproducible checks of the analysis.

We study adaptive confidence sets for mean vectors of multivariate Gaussians with identity covariance under Huber contamination when the contamination proportion is unknown. We show that an information-theoretically optimal adaptive confidence set can be constructed by simultaneously quantifying uncertainty across all one-dimensional projections. The resulting confidence set achieves the optimal diameter and reveals a substantial adaptation cost compared with the minimax estimation error. Although statistically optimal, this construction is computationally infeasible. We establish a Statistical Query (SQ) lower bound showing that achieving diameter $O(m^{-1/2})$ requires either exponentially many queries or query tolerance $d^{-\Omega(m)}$. Thus, in contrast to robust mean estimation, adaptation to the unknown contamination proportion incurs both a statistical cost and a computational barrier within the SQ framework. Finally, we give a low-degree moment-matching algorithm that constructs an adaptive confidence set using $d^{O(m)}$ samples and time. Its diameter bound contains an additional $O(m^{-1/2})$ term beyond the information-theoretic rate, matching the dependence on $m$ in the SQ lower bound. Together, these results characterize the statistical limits of adaptive robust confidence sets under Huber contamination and quantify a computational barrier within the SQ framework.

Large-scale distributed training increasingly makes collective communication bandwidth-bound. In modern GPU clusters, communication libraries such as NCCL implement collectives including AllReduce over heterogeneous interconnects such as NVLink, InfiniBand, and Ethernet, making efficient use of available network bandwidth a central systems challenge. ForestColl showed that collective communication on such fabrics can be formulated using fractional tree packing; its scalable polynomial-time construction is developed for AllGather, with AllReduce obtained by composing AllGather and ReduceScatter. We present DualColl, which targets bandwidth-bound AllReduce directly. Under the tree-based AllReduce model, DualColl applies a Garg–Könemann-style multiplicative-weights algorithm and, for any $0<\epsilon<1$, computes a feasible schedule whose throughput is at least $(1-\epsilon)^2$ of the optimal AllReduce throughput. Its key component is an exact minimum-cost collective-tree oracle that projects physical-link dual prices onto a logical graph of participating ranks, reducing each iteration to shortest-path computations followed by a minimum spanning tree. We further extend the framework to local equal-next-hop packet-sprayed routing and to networks without explicit per-tree bandwidth control. For the latter, we introduce a tree-coupled max-min bandwidth-sharing model and show that tree duplication approximates an explicit fractional allocation with a provable accuracy-complexity tradeoff. Finally, we extend the fractional-packing framework to additional collective operations and multiple concurrent collective groups.

A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for either a polynomial-time algorithm or an NP-hardness proof for metric planarity testing: given a metric space $(X,d_X)$, determine whether there exists an edge-weighted planar graph $G=(V,E,w)$ with $X\subseteq V$ that realizes the distances in $X$, meaning that $d_G(x,y)=d_X(x,y)$ for every $x,y\in X$. This question arose in the context of research on metric embeddings and their applications in computer science since the mid-1990s. Over the past few decades, polynomial-time algorithms have been developed for several special cases. In this work, we show that metric planarity testing is NP-hard, in sharp contrast to graph planarity testing. Our reduction yields a stronger result: under the Exponential Time Hypothesis (ETH), no $2^{o(n)}$-time algorithm for metric planarity testing exists, where $n$ is the number of points in the metric. To complement our ETH lower bound, we give two algorithmic results: (i) an algorithm for computing a metric planar embedding in $2^{\tilde{O}(n^2)}$ time and (ii) a $(1+\epsilon)$-approximation algorithm in $2^{\tilde{O}(n)}$ time for any fixed $\epsilon\in(0,1)$. The second algorithm produces a planar graph that preserves the input metric up to a factor of $(1+\epsilon)$.

We study constant-round LOCAL approximation for additive local vertex-subset minimization problems. Given a $k$-uniform $\alpha$-approximation on a hereditary source class closed under disjoint union, Bonamy, Das, Gavoille, Picavet, Suomela, and Wesolek obtained ratio $\alpha(d+1)+1$ on locally nice target classes of asymptotic dimension $d$. We prove two transfers with ratios $\alpha+1+\eta$ and $\alpha+\eta$ for every $\eta>0$. These bounds require the stronger local niceness assumption at a larger scale that depends on $\eta$. The first algorithm keeps their repair construction and increases the radius used to detect errors. We average over partitions of the graph to bound the retained cost without the factor $d+1$. These partitions are used only in the analysis. The second algorithm tests several deletion widths around the errors. In each component of the repair zone, it chooses a smallest union of retained choices and an exact repair. Averaging over the widths bounds the cost counted twice and yields ratio $\alpha+\eta$. Both transfers are deterministic and computable, use arbitrary distinct numerical identifiers, and need no knowledge of the graph size. Their outputs also satisfy local uniformity guarantees. For 2-domination on graphs of bounded Euler genus, the same planar source gives ratio $19$ through the earlier transfer and $6+\eta$ through ours. For minimum dominating set, our transfer gives ratio $7+\varepsilon$ on graphs formed by attaching a clique of arbitrary size at one vertex of a planar graph, using the source algorithm of Amiri and Siebertz. This class satisfies our target assumptions and allows nonempty error sets. Its Euler genus is unbounded, so their guarantee for graphs of bounded Euler genus does not cover the whole class.