arXane › Computer Science › Computer Science
Wednesday, 4 November 2026: 48 new papers, 13 cross-lists and 57 replacements in Data Structures and Algorithms (cs.DS), in arXiv's order, with full abstracts. The same papers as arXiv's own listing, set as a newspaper; every title links to arXiv.
A tournament is an orientation of a complete graph. A vertex $v$ controls a vertex $u\neq v$ if there is a directed path of length at most two from $v$ to $u$, and a $\delta$-king is one that controls at least $\delta(n-1)$ vertices. In the query complexity model, each query reveals the orientation of an edge. Shen, Sheng and Wu [SICOMP'03] established an $\Omega(n^{4/3})$ lower bound on the deterministic query complexity of finding a $1$-king, and a non-matching upper bound of $O(n^{3/2})$. Neither bound has been improved in over two decades, despite substantial progress on variants of the problem. For $\delta$-kings with $\delta < 1$, Biswas, Jayapaul, Raman and Satti [Discrete Applied Mathematics'22] showed that $O(n^{4/3})$ queries suffice to find a $\frac12$-king. Lachish, Reidl and Trehan [FSTTCS'22] improved this guarantee to $\frac12+\frac{2}{17}$ using $\widetilde{O}(n^{4/3})$ 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 $\varepsilon\in(0,1)$, we give a deterministic algorithm that finds a $(1-\varepsilon)$-king using $O(n^{4/3})$ queries. The design of our algorithm is informed by a structural analysis combining a sparse regularity lemma due to Allen, Kohayakawa, Mota and Parente [Electronic Journal of Combinatorics'14] with a new sampling argument based on a reachability theorem of Afek, Gafni and Linial [arXiv'19].
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_{\max}$ error for converting a fractional flow into an unsplittable one.
The Hyperclique Hypothesis postulates that, for all constants $k > h \geq 3$, detecting a $k$-clique in an $h$-uniform hypergraph with $n$ vertices requires time $n^{k-o(1)}$. This hypothesis is false: there is an algebraic algorithm that detects (and even counts) $k$-cliques in $h$-uniform hypergraphs in time $O(n^{(1-\epsilon_h)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.
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 $\Theta(n \log n)$ bits to achieve constant error, while a nonlinear protocol only requires $O(\log n)$ bits.
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 \cite{BGG18} 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 ingredients give a $(20/3+\eps)$-approximation; starting each penalty run from the preceding solution improves the guarantee to $60/11+\eps$.
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.
We study online metric matching with $n$ servers and $n$ requests drawn independently from an unknown distribution. Each request must be matched immediately and irrevocably to an unused server, and the algorithm receives no samples before the process starts. We give a randomized algorithm that is $O((\log\log\log n)^2)$-competitive on arbitrary metric spaces and $O(1)$-competitive on tree metrics. These guarantees match the corresponding bounds for known i.i.d. request distributions in [GGPW19] up to constant factors. More generally, our competitive ratio is $O(\alpha(n))$ whenever the Fair-Bias algorithm introduced in that work has competitive ratio $\alpha(n)$ for known i.i.d. arrivals on the same class of metrics. Consequently, proving that Fair-Bias is constant-competitive on general metrics would also yield a constant-competitive algorithm for unknown i.i.d. arrivals.
A tester decides whether a graph has a property or is far from having it. A distance estimator asks for more: it must approximately determine how many edges need to be changed. A property is said to be testable if there is a tester with a number of queries bounded independently of the graph's order for each conceivable distance. Similarly, if a property admits an estimator with a number of queries bounded independently of the graph's order, it is said to be estimable. Fischer and Newman proved that, in the dense graph model, every testable property is also estimable. We show that the passage from testing to estimation requires only a polynomial increase in query complexity. This resolves a long-standing open problem in property testing, previously tackled by Fiat and Ron, by Hoppen, Kohayakawa, Lang, Lefmann, and Stagni, and by Gishboliner, Kushnir, and Shapira.
The seminal result of Czumaj and Sohler [STOC'04] showed that a 2-approximation of the value of metric TSP can be obtained with sublinear queries. Whether sublinear algorithms can break the 2-approximation barrier has remained a major open problem. See problem 71 on sublinear.info. This paper resolves this open problem. We show there are fixed $\varepsilon, \delta > 0$ such that a $(2-\delta)$-approximation of metric TSP value can be obtained with $O(n^{2-\varepsilon})$ queries. Here $n$ is the number of vertices, and the input size is $\Theta(n^2)$.
The binary perceptron is a random constraint satisfaction problem that asks for a sign vector satisfying a system of random linear inequalities. Its solution space has a strikingly extreme geometry: at every positive constraint density, all but a vanishing fraction of the solutions are isolated. Yet polynomial-time algorithms find solutions at small enough constraint density, which raises the question of how efficient algorithms navigate such a landscape. Linear programming is a natural algorithm to study here, but its analysis has so far been limited to a single round. Li, Schramm, and Zhou (STOC 2025) analyzed one linear program followed by iterative rounding. In this work, we overcome this limitation and give a precise analysis of iterated linear programming for the binary perceptron. (1) For Gaussian matrices and any fixed number of rounds, we characterize the iterated linear programs exactly through a deterministic state-evolution recursion. (2) Adding a final rounding step, we obtain a randomized polynomial-time algorithm for the binary perceptron. Numerical evaluations of the recursion provide evidence that it succeeds at constraint density $\alpha=0.60$ with zero margin, well beyond the range $\alpha\le0.1$ guaranteed by the single-LP analysis and $\alpha\approx0.327$ (Jo and Lee, 2026), the best guarantee so far. (3) We establish universality, showing that the same characterization holds for matrices with i.i.d. entries drawn from any centered, unit-variance subgaussian law. The key idea of our proof is that, although conditioning on earlier rounds makes the matrix non-Gaussian, its conditional law can be computed explicitly and remains close to a Gaussian law, so the convex Gaussian min-max theorem applies in every round. For universality, we compare Gaussian and subgaussian matrices through the Lindeberg principle, using a regularized version of each linear program.
We give classical randomized algorithms in a word RAM model that break the $2^{n/2}$ barrier for both discrete Gaussian sampling (DGS) and the Shortest Vector Problem (SVP). For every fixed $\alpha>1$, shifted DGS on arbitrary lattices at width $\sigma\ge\alpha\eta_{1/2}(L)$ takes $$ (3/2)^{n/2+o(n)}\text{ time} \qquad\text{and}\qquad (4/3)^{n/2+o(n)}\text{ space}. $$ These bounds match the Becker--Ducas--Gama--Laarhoven (BDGL) heuristic sieving exponents. At widths at least $3\eta_{1/2}(L)/2$, the same total cost suffices for an entire batch of $\lfloor(4/3)^{n/2}\rfloor$ samples jointly close to independent target Gaussians. For SVP on arbitrary lattices, our algorithm returns a shortest nonzero vector with high probability in $$ 2^{0.4130n+o(n)}\text{ time} \qquad\text{and}\qquad 2^{0.3138n+o(n)}\text{ space}. $$ As a corollary, we obtain centered DGS at every width with the same exponents, answering a question of Stephens-Davidowitz (SODA 2016). We introduce Gaussian difference dynamics (GDD), a framework for tracking expected counts and pairwise clustering of vectors through repeated differencing. A closed recursion for the first two counting moments controls these quantities relative to a Gaussian reference, without requiring independence within intermediate lists. Accurate moment bounds let us extract a Gaussian sample by weighted selection, while the weaker bounds needed to establish a shortest vector representation allow us to retain more differences. We perform these transitions on thin spherical shells, where the Gaussian rejection weights can be renormalized at subexponential cost. For batch sampling, we combine this geometry with the double rejection technique of Doulgerakis and Laarhoven to control the joint distribution of outputs while reusing vectors.
We study time--space tradeoffs for computing Boolean functions $f:\{0,1\}^n \to \{0,1\}$ in the random query model. On input $x$, a branching program receives independent samples $(i,x(i))$, where $i$ is uniform in $[n]$. We want to evaluate $f(x)$ while minimizing the width $2^S$ and the length $T$ of the branching program. There is a simple upper bound of $T = \tilde{O}(n)$, $S = O(n)$: coupon-collector shows that $\tilde{O}(n)$ samples suffice, and they can be stored in $O(n)$ space. Raz and Zhan (ITCS 2020) introduced this model and studied the zero-error setting. In the bounded-error setting, Dinur (SODA 2024) proved $TS = \tilde{\Omega}(n \cdot inf[f])$, where $inf[f]$ is the total influence of $f$. For many functions with low influence such as Equality and Tribes, this lower bound can leave a substantial gap from the best known upper bounds. Our main result is a stronger lower bound of $T(S+\log T) = \Omega(n \cdot sens[g])$ for any XOR-function $g(x,y)= f(x \oplus y)$, where $sens[g]$ is the sensitivity of $g$. Through simple corollaries, we get tight nearly-quadratic time--space lower bounds for Tribes and Equality, despite their low influence. Our proof introduces a new notion of information complexity tailored to the random query model along with a corresponding direct-sum argument which may be of independent interest. Dinur also proved a tight bound of $TS = \Omega(n^2)$ for Majority, whose influence is only $\Theta(\sqrt{n})$, and asked whether an alternative characterization of Boolean functions could give a unified proof of tight results for a broader class of functions, including Majority. We answer this open question by proving $TS = \tilde{\Omega}(n \cdot dgn[f])$, where $dgn[f]$ is the degeneracy of the sensitivity graph of $f$ (for Majority, this is $\Theta(n)$). We also prove that this bound is tight for all symmetric functions up to logarithmic factors.
We characterize the optimal space for one-pass spanning-forest computation in dynamic streams of $v$-vertex simple graphs with failure probability at most $\delta$. Nelson and Yu proved an $\Omega(v\log^2v\log(v/\delta))$-bit lower bound, establishing the AGM algorithm's optimality for each fixed $0<\epsilon<1$ and $2^{-v^{1-\epsilon}}<\delta\le1/4$. We resolve the remaining high-confidence regime: for every $0<\delta\le1/4$, matching lower bounds and an algorithm give \[ \Theta\!\left(\min\left\{v^2,\;v\log(v/\delta)\log^2\!\left(2+\frac{v}{\log(v/\delta)}\right)\right\}\right) \] bits, improving space by up to a factor of $\Theta((\log v/\log\log v)^2)$ in this regime. We also study streams with at most $Z$ previously inserted edges deleted and not yet reinserted at report time, where the integer $Z\ge0$ is given in advance. Total deletions, restorations, and intermediate absence counts are unrestricted. For a single report and every $0<\delta\le1/4$, matching lower bounds and a one-pass randomized algorithm yield optimal space $\Theta(\mathcal L(v,Z,\log(1/\delta)))$ bits, where $x_Z(t)=\min\{Z+1,v,\sqrt{vt}\}$ and \[ \mathcal L(v,Z,t)=v\log v\min\{\log^2v,\log^2(Z+2)\} +vt\log\!\left(1+\frac{x_Z(t)}t\right)\log\!\left(1+\frac v{x_Z(t)}\right). \] At zero error, a lower bound for all zero-error algorithms and a matching deterministic algorithm give optimal space \[ \Theta\!\left(\min\{v^2,v(Z+1)\log(1+v/(Z+1))\}\right) \] bits. Together, these results characterize the memory required across all confidence levels and report-time edge-loss bounds.
Binary prefix coding assigns prefix-free binary words to symbols to minimize their frequency-weighted cost. Huffman solved the equal-letter-cost case in polynomial time in 1952 [Proc. IRE'52]. For unequal letter costs, Karp gave an integer-programming formulation in 1961 [IRE Trans. Inf. Theory'61]. Exact polynomial-time algorithms for fixed integer costs were given by Golin and Rote [IEEE Trans. Inf. Theory'98] and Bradford, Golin, Larmore, and Rytter [J. Algorithms'02]. For input-dependent costs, Golin, Mathieu, and Young gave a polynomial-time approximation scheme [SICOMP'12]. The exact complexity when letter costs are part of the input had remained unresolved. We resolve this $65$-year-old problem by proving that deciding whether there exists a binary prefix-free code of frequency-weighted cost at most a given threshold is NP-complete, even when the letter costs are consecutive positive integers $(M,M+1)$ supplied as part of the input. All frequencies, letter costs, and thresholds are encoded in binary. Consequently, finding an optimal code is NP-hard. Our proof uses two polynomial-time reductions, starting from Planar Independent Set. The intermediate problem prescribes the number of leaves at each depth of a full ordered binary tree and minimizes a signed linear score on their sorted right-edge counts. The first reduction represents an independent-set verification program by a tree growing level by level. A fixed-profile identity converts narrow coordinate restrictions into linear penalties that enforce the computation. The second reduction adds large dyadic terms to the symbol frequencies to force prescribed depths. These terms contribute a constant to the weighted number of ones, leaving smaller signed perturbations to reproduce the tree score.
The Steiner tree problem is the canonical generalization of minimum spanning tree (MST). When connectivity is required only among a fixed subset of vertices (terminals), the goal is to maintain a minimum-cost tree connecting these terminals as the graph undergoes edge updates. While dynamic MST has been studied since the 1980s~[Frederickson, STOC'83, SICOMP'85], and the first sublinear-in-$n$ dynamic MST algorithm dates back almost thirty-five years to Eppstein, Galil, Italiano, and Nissenzweig~[FOCS'92, JACM'97], achieving sublinear-in-$n$ update time for dynamic Steiner tree has long remained open, as a single edge update can invalidate many routes in the underlying terminal metric closure. We present the first fully dynamic algorithm for Steiner tree that achieves a constant-factor approximation with sublinear-in-$n$ update time. For any fixed $0<\zeta<1/2$, our deterministic algorithm maintains an $O_\zeta(1)$-approximate Steiner tree for undirected graphs with polynomially bounded edge weights in $\widetilde O(n^{1/2+\zeta})$ amortized update time, answering cost queries in $O(1)$ time, and reporting an explicit tree in $\widetilde O(n^{1+\zeta})$ time. Our approach combines periodic terminal-metric rebuilds on a dynamic spanner with a top-tree dynamic program that localizes edge deletions and reconnects surviving components through a dynamic distance sparsifier. Along the way, we give a simpler randomized insertion-only algorithm with a better, explicit approximation ratio.
We study binary search for a target drawn from a distribution on $n$ ordered elements. The cost is the expected number of comparison queries. In our distributionally robust framework, the algorithm knows only an uncertainty set containing the distribution and minimizes its worst-case approximation ratio against an optimal strategy that knows the distribution. Collections of uncertainty sets capture different forms of information: quantiles, moments, general linear measurements, or approximate CDFs. This framework quantifies how much and what form of information is needed for near-optimal search. Our main result separates moments from general linear measurements. Although $n-1$ moments determine the distribution exactly, for every constant $\delta\in(0,1)$, the first $n^{1-\delta}$ exact moments can be as uninformative for search as no information: the worst-case approximation ratio remains $\Omega(\log n)$. In contrast, for every constant $\varepsilon\in(0,1)$, $O(n^\varepsilon\log^4 n)$ suitably chosen linear measurements suffice for an $O(1/\varepsilon)$-approximation. The limitation lies in the measurements chosen, rather than linearity itself. Using LP duality and polynomial bounds of Rakhmanov and Bernstein, we construct distributions with identical moments and mass concentrated at different positions. For the upper bound, we combine dyadic sketches and Johnson--Lindenstrauss embeddings with a truncated median-search algorithm that converts uniform CDF approximation into search guarantees. Measuring information in bits, we prove a lower bound of $\Omega(1/\varepsilon)$ on the approximation ratio for summaries of any form using at most $\frac12 n^\varepsilon\log n$ bits, for every sufficiently small constant $\varepsilon>0$. Quantiles match this within constant factors. For Kolmogorov balls of radius $n^{-\varepsilon}$ the optimal approximation ratio is $\Theta(1/\varepsilon)$.
We present the first four All-Pairs Approximate Shortest Paths (APASP) algorithms for decremental weighted undirected graphs. We extend the hierarchy induced edge sets of Baswana and Kavitha [FOCS'06 and SICOMP'10] to the decremental setting. At any point in time, for any $u,v$, $W_{i}$ denotes the weight of the $i$-th heaviest edge on any shortest path between them in the current graph. For any $\varepsilon>0$, our first algorithm maintains $(1+\varepsilon,2W_{2})$-APASP in $\tilde{O}(n^{\frac{3}{2}+o(1)}m^{\frac{1}{2}})$ total update time, matching a single static computation of Cohen and Zwick [SODA'97 and JALG'01], up to a subpolynomial factor. It also improves the stretch of the $(2+\varepsilon)$-APASP algorithm of Dory, Forster, Nazari and de Vos [ICALP'24]. Our second algorithm maintains $(1+\varepsilon,2W_{1}+2W_{2})$-APASP in $\tilde{O}(n^{\frac{7}{3}})$ total update time, improving upon Chechik's $(3+\varepsilon)$-APASP algorithm [FOCS'18] for $m=\Omega(n^{\frac{11}{6}})$. We also obtain two $(1+\varepsilon,2\cdot(k-1)W_{1})$-APASP algorithms with total update times $\tilde{O}(n^{2-\frac{1}{k}+o(1)}m^{\frac{1}{k}})$ and $\tilde{O}(n^{2+\frac{2}{3k-2}+o(1)})$, adapting the static $+2\sum_{i=1}^{k-1}W_{i}$-APASP algorithms of Cohen and Zwick [SODA'97 and JALG'01] and Roditty and Sapir [FSTTCS'25]. For unweighted graphs, we present $(1+\varepsilon,2)$-APASP in $\tilde{O}(n^{\frac{7}{3}})$ total update time and $(1+\varepsilon,2\cdot(k-1))$-APASP in $\tilde{O}(n^{2+\frac{1}{3k-4}+o(1)})$. Combined with the results of Dory, Forster, Nazari and de Vos [ICALP'24], these match the fastest combinatorial static bounds of Dor, Halperin and Zwick [FOCS'96 and SICOMP'00] up to subpolynomial factors.
We show that for every $\gamma>0$ and every sufficiently large $\Delta$, the Glauber dynamics for proper $q$-colorings of any $n$-vertex graph of maximum degree $\Delta$ has spectral gap $\Omega_\gamma(1/n)$, and hence mixing time $O_\gamma(n^2\log q)$, whenever $q\ge(1+1/\mathrm{e}+\gamma)\Delta$. Our proof establishes a Bochner-type inequality by exploiting the spectral gaps of hard-core models hidden in the color classes. The constant $1+1/\mathrm{e}\approx1.368$ comes from the uniqueness threshold $\approx\mathrm{e}/\Delta$ of the hard-core model on the infinite $\Delta$-regular tree.
We study the offline release of a public family of $k$ statistical queries on a database of $N$ records from a public universe of size $d$, under pure $\varepsilon$-differential privacy. We give an efficient algorithm that, with probability at least $1-\beta$, answers all queries simultaneously to error $$O\left(\min\left\{1,\sqrt{\frac{\log(d/\beta)\log k}{N\varepsilon}}\right\}\right).$$ The output is a synthetic histogram on the data universe, and its running time depends polynomially on $N,d$ and $k$. This resolves a conjecture of Nikolov and Ullman (2021) with an efficient, polynomial-time construction. Fitzsimons (2026) recently established the same square-root error scale via an information-theoretic construction that relies on a computationally intractable Lipschitz envelope over the exponential space of possible outputs. In contrast, we introduce an input-side smoothing approach: we run a selection-only multiplicative-weights process after a single sparse Laplace perturbation of the input histogram. Departing from standard first-order stability analyses, we investigate the stability of stability by establishing a uniform lower bound on the second-order log-derivatives of the output transcript across $T$ rounds of multiplicative weight updates. We then develop an analytic smoothing principle showing that this curvature bound allows a sparse, coordinate-wise perturbation to guarantee pure differential privacy globally, attaining optimal utility through a conceptually simple, polynomial-time pure-DP mechanism.
In a seminal work [STOC'01; JACM'05], Thorup and Zwick showed that every weighted undirected graph admits a tree cover where each vertex belongs to $O(kn^{1/k})$ trees in expectation, and every pair has a path of stretch at most $2k-1$ in some tree. In this paper, we extend this structural property to directed graphs with nonnegative edge weights. Let $\mathrm{dist}_G(u \leftrightarrows v) = \mathrm{dist}_G(u \to v) + \mathrm{dist}_G(v \to u)$ denote the roundtrip distance. For every integer $k$, we construct a collection $\mathcal{T}$ of tree-pairs, each consisting of an in-tree and an out-tree rooted at the same vertex. Each vertex belongs to $O(kn^{1/k})$ tree-pairs in expectation, and for every ordered pair $(u, v)$ some tree-pair $T_{in}\cup T_{out} \in \mathcal{T}$ satisfies $\mathrm{dist}_{T_{in}\cup T_{out}}(u \to v) \le \mathrm{dist}_G(u \to v) + (k-1)\mathrm{dist}_G(u \leftrightarrows v).$ We call this a \emph{$k$-strong (roundtrip) tree cover}. While prior techniques partition distances into geometric scales and build separate structures for each scale, our construction handles all distances simultaneously within a single, unified hierarchy. This yields the first directed tree cover for general $k$ matching the classic Thorup-Zwick stretch-size trade-off. Our cover immediately implies improved constructions of roundtrip spanners, path-reporting distance oracles, and compact routing schemes, as well as their source-wise and prioritized variants. We also provide faster algorithms for these structures: for general $k \ge 4$, all the above objects can be constructed in $\widetilde{O}(\min\{mn, n^{2.5}\})$ expected time, breaking the $mn$ barrier in dense directed graphs.
Dor, Halperin and Zwick [FOCS'96; SICOMP'00] showed that $(2-\varepsilon)$-APASP is at least as hard as BMM for every fixed $0<\varepsilon<1$. Zwick [FOCS'98; JACM'02] gave a $2$-APASP algorithm in $\widetilde O(n^{\omega+o(1)}\log W_{\max})$ runtime, where $W_{\max}$ is the maximum edge weight. Bringmann, K{\"u}nnemann and W{\k{e}}grzycki [STOC'19] removed this logarithmic factor. Using OpenAI's recent bound $\omega\leq\frac{9}{4}$ gives $\widetilde O\left(n^{\frac{9}{4}+o(1)}\right)$ time. We present two weighted undirected $2$-APASP algorithms. The first uses $(\min,\max)$-products. Earlier rectangular FMM bounds of Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou [SODA'24] and Alman, Duan, Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou [SODA'25] give $\widetilde O(n^{2.36999465})$ runtime, below the previous $\omega\leq2.371177$ of Dupont, Eisenberger, Kozlovskii, Mehrabian, Ruiz, See, Zhou, Alman, Vassilevska Williams and Balog [arXiv'26]. Current rectangular FMM bounds give $\widetilde O(n^{2.34549151})$, independent of $W_{\max}$. For integer weights, our second algorithm has $\widetilde O(n^{\omega-\frac{(\omega-2)^2}{\omega-1}+o(1)}\log^{O(1)}W_{\max})$ runtime, with exponent below $\omega$ whenever $\omega>2$. The rectangular bounds of Uzna{\'n}ski [arXiv'26] or of Amanov, van den Berg and Zuiddam [arXiv'26] give $\widetilde O(n^{2.17157288}\log^{O(1)}W_{\max})$.
Min-max multi-criteria optimization asks for a single feasible solution minimizing the maximum of its costs under $\ell$ nonnegative cost functions, a formulation that captures both fairness across groups and robustness across scenarios. It has proved hard to approximate even for basic problems: for robust shortest paths, polylogarithmic approximations are known only in quasi-polynomial time. For network design, the best known guarantee is an $\ell$-approximation, which is tight for the natural LP relaxation. We show that exponentially better and nearly optimal guarantees are achievable for two fundamental network design problems. For multi-criteria connectivity augmentation (MC-CAP), which asks to increase the edge connectivity of a given undirected graph by one, we give a randomized polynomial-time $O(\log \ell)$-approximation algorithm. Applying our augmentation procedure iteratively and analyzing its randomized choices jointly across iterations yields an $O(\log k \log \ell)$-approximation for the multi-criteria $k$-edge-connected spanning subgraph (MC-$k$-ECSS) problem, for every $k \geq 2$. We complement these algorithms with a nearly matching lower bound: for every fixed $\varepsilon > 0$, MC-CAP admits no polynomial-time $O(\log^{1-\varepsilon} \ell)$-approximation, even when the underlying graph is a star, unless $\mathsf{NP}\subseteq\mathsf{DTIME}\bigl(n^{\log^{O(1)}n}\bigr)$. The same hardness extends to the MC-$k$-ECSS problem.
Compact routing schemes route messages along short paths while every vertex stores little information. We study the trade-off between the stretch and the storage of compact routing schemes in undirected graphs, in four models: labeled and name-independent schemes, with average or worst-case local storage. We improve the best known stretch in all four models. Our main result is a labeled routing scheme with expected stretch $2k-1$ and $\widetilde O(n^{1/k})$ average local storage, in which only the routing is randomized. Under the Erd\H{o}s girth conjecture, no scheme with this storage has stretch below $2k-1$, so our scheme is optimal, up to polylogarithmic factors in the storage. With deterministic routing, we obtain stretch $\approx2.47k$, the best known deterministic stretch with average storage. Worst-case local storage is the classical setting of compact routing. The leading coefficient $4$ in the stretch $4k-5$ of Thorup and Zwick~[SPAA'01] was improved only by Chechik~[PODC'13], to $\approx3.68$ in unweighted graphs. In unweighted graphs, we obtain expected stretch $(\frac83k+O(1),O(k))$, and deterministic stretch $\approx3.05k$. Name-independent routing is harder, since the source knows only the name of the destination. The best known stretch with $\widetilde O(n^{1/k})$ local storage in unweighted graphs was $96k$, by Abraham, Gavoille, and Malkhi~[DISC'04]. We improve it by more than a factor of $8$. With average storage, we obtain expected stretch $4k-5$, which matches the labeled scheme of Thorup and Zwick. With worst-case storage in unweighted graphs, we obtain expected stretch $(8k+O(1),O(k))$. All our schemes for unweighted graphs extend to weighted graphs with a small loss in the stretch, and still improve the previous unweighted bounds.
Testing expansion asks to distinguish graphs of large conductance from graphs that are far from having large conductance. We study a relaxation in which only part of the graph is required to expand: does an $n$-vertex graph of bounded degree contain an induced expander on a constant fraction of its vertices, when the rest of the graph, including the edges leaving the expander, is arbitrary? Let $P_{\alpha,\phi}$ denote the property of containing an induced subgraph on at least $\alpha n$ vertices with inner conductance at least $\phi$. For every constant $\kappa\in(0,1)$, we give a tester that accepts graphs in $P_{\alpha,\phi}$ and rejects graphs outside $P_{\kappa\alpha,\mu\phi^2}$, where $\mu=\Theta_{\alpha,\kappa}(1/\log n)$, using $O_{\alpha,\kappa}(\sqrt n\,\phi^{-2}\log n)$ queries. For fixed $\alpha\in(0,1]$, $\kappa\in(0,1)$, and $0<\phi\le9/20$, we further show that distinguishing these two classes requires $\Omega_{\alpha,\kappa,\phi}(n^{1/2+c_{\kappa,\phi}\mu})$ queries for every sufficiently large $n$ and every $0<\mu\le1$, where $c_{\kappa,\phi}>0$. The bound holds for adaptive algorithms, uniformly in $\mu$. Hence, for testers with $\sqrt n\,\mathrm{polylog}(n)$ queries, the logarithmic loss in conductance is necessary up to a $\log\log n$ factor. The same tester also permits distance-based rejection at a weaker conductance while retaining the original core size. Our tester compares the endpoint distributions of random walks from different vertices with each other, rather than with the uniform distribution. Its analysis uses the trace chain, which observes the walk only at its visits to the unknown expanding core. Our lower bound builds on the noisy-parity construction of [CKK+18], using vector-valued parity labels in $\mathbb F_2^r$ to create many hidden classes, each too small to contain a qualifying induced expander.
In this paper, we study exact online integer priority queues under differential obliviousness in the balls-and-bins model. Given a public upper bound $T$ on the number of operations and assuming that the priorities are bounded by a polynomial in $T$, we construct an $(\eps,\delta)$-differentially oblivious priority queue supporting insertion and minimum extraction, which requires $\polylog(T)$ private memory. For constant $\varepsilon>0$ and $\delta=\exp(-\Theta(\log^2 T))$, our construction incurs $O(\log T/\log\log T)$ expected amortized total work per operation, which breaks the $\Omega(\log T)$ barrier for fully oblivious priority queues~[Jacob et al., SODA'2019]. Further, we prove a matching lower bound for $(\eps,\delta)$-differentially oblivious priority queues with $\varepsilon=O(1)$ and $\delta=o(1)$, which indicates that our construction is asymptotically optimal in terms of total work.
The best-known approximation factor for constrained correlation clustering stood at three for nearly two decades, until a recent improvement to below $16/7$. We give a randomized polynomial-time $(2+\varepsilon)$-approximation using \emph{Repulsion}, a recursive operation that separates a metric ball from its complement. Repulsion naturally respects hard constraints and admits a short potential-based analysis; as a warm-up, radius-$2/3$ Repulsion rounds the standard metric LP into a feasible partition of cost at most three times its objective. The $(2+\varepsilon)$-approximation takes a two-stage approach, first removing must-links with arbitrarily small loss in the approximation ratio. The second stage combines lossless, constraint-aware preclustering with the bounded sub-cluster LP framework of Cao, Cohen-Addad, Lee, Li, Newman, and Vogl (STOC 2024). Repeated positive conditioning and sampling produce candidate sets, which radius-one Repulsion partitions into feasible clusters at controlled cost. We also give an approximation-preserving reduction from vertex cover to cluster deletion, a special case with only cannot-links. Apart from establishing a matching factor-two hardness threshold under the Unique Games Conjecture, it motivates our two-stage approach and Repulsion.
We give a near-linear-time sampler for the zero-field ferromagnetic Ising model throughout the tree-uniqueness regime, including the threshold itself. The method also gives sampling algorithms for the XY and integer Potts models. On an $n$-vertex graph with $m$ edges and maximum degree at most $\Delta$, we obtain the following expected-work bounds, with total variation error at most $\varepsilon$. 1.Near-linear Ising sampling. For $\Delta\ge3$, the work is $O(n+m\log^3(n/\varepsilon))$ throughout the tree-uniqueness regime, including the threshold $\beta=\Delta/(\Delta-2)$. 2.Almost-linear XY sampling. For $\Delta\ge8$, we sample the XY model in $\widetilde O(m+n^{1+o(1)})$ expected work at inverse-polynomial accuracy up to and including the robust phase-transition threshold on the $\Delta$-regular tree. 3.Near-linear Potts sampling. For integer $q\ge3$, we sample the $q$-state Potts model in $\widetilde O(n+q^{O(1)}m)$ expected work whenever $\beta-1\le 0.1(\beta_{\mathrm{od}}(q,\Delta)-1)$, where $\beta_{\mathrm{od}}$ is the ordered/disordered coexistence parameter. We express the even-subgraph representation of critical Ising as a polymer model that admits near-linear-time sampling, thereby bypassing the critical slowdown of Glauber and Swendsen--Wang dynamics. Building on the low-degree approximation approach of Miao and Yin, we establish general spectral conditions for fast polymer sampling. We verify these conditions through explorations that also implement the sampler efficiently, and apply the same framework to flow representations of the XY and Potts models. We also establish polynomial-time counting and sampling for the ferromagnetic XY model at every fixed temperature.
Efficient graph algorithms often use techniques that are specific to integer-valued inputs and do not work for real-valued versions of the problems. Is it a limitation of current techniques, or are the real-valued variants inherently harder? One way to study this question is through real-to-integer reductions. We give (randomized, combinatorial) subcubic real-to-integer reductions for two central graph problems in fine-grained complexity: All-Pairs Shortest Paths and Exact Triangle. That is, we show that if the integer variants of these problems can be solved in truly subcubic time, then the real variants can also be solved in truly subcubic time. Our work extends and combines techniques from three previous works: (1) our real-to-integer reduction for the 3SUM problem (Fischer, Polak, Schmidt, FOCS 2026), which itself combines the Frank--Tardos theorem from optimization with Freiman's theorem from additive combinatorics; (2) universe reduction for APSP (Fischer, STOC 2026), which we generalize to reals and use to reduce the doubling of the set of edge weights; and (3) the ``Fredman's trick meets dominance product'' technique (Chan, Vassilevska Williams, Xu, STOC 2023), which is needed to adapt the prior real-to-integer framework from equality constraints to inequalities. As a corollary, our reduction combined with Yuval's fast Integer APSP algorithm in the real RAM model with multiplication (IPL 1976) shows that the Real APSP Hypothesis is false in this model, which also follows from the very recent breakthrough by Alman and Vassilevska Williams using a very different approach.
Regular expression matching asks whether a string of length $n$ belongs to the language described by a regular expression of length $m$. We give an algorithm that solves this problem in linear space and $O(nm \log \log n/\log^2 n + n + m)$ time. This improves the leading term of the previous best worst-case constant-alphabet time bound by a factor of $\sqrt{\log n}$. The key new technique is a two-dimensional tabulation specialized to the regular expression.
Given intervals and points on a line, each point with a demand, and a budget $K$, Maximum Interval Multicover asks for at most $K$ intervals that satisfy as many points as possible, a point being satisfied if it lies in at least as many chosen intervals as its demand. One application is committee elections in which each candidate is approved by consecutive voters and voters have individual demands. Xu, Ran and Zhang introduced the problem and gave a $1/2$-approximation; the objective is not submodular when demands exceed one. Li, Tu, Zhang and Cao gave a polynomial-time approximation scheme (PTAS) for the minimization counterpart, unweighted partial interval multicover, and asked for its complexity. We prove that both problems are NP-hard, even for intervals of equal length; as their optima are integers bounded by the input size, neither has a fully polynomial-time approximation scheme unless $\mathrm{P}=\mathrm{NP}$. We then give a PTAS for Maximum Interval Multicover, also for arbitrary nonnegative nondecreasing rewards for the coverage of each point. Building on a decomposition from Nonner's PTAS for Densest $k$-Subgraph on interval graphs, our scheme cuts the line into pieces at a small loss and solves every piece exactly. The key dynamic program handles intervals crossing a common point by choosing an interleaving of their left and right endpoints rather than sweeping along the line; it needs only two counters to track these intervals. The same algorithm yields PTASes on convex bipartite graphs for Bipartite Dense Subgraph, improving on the ratio $2/3$ of Backer and Keil for the subclass of bipartite permutation graphs, and on interval graphs for Maximum $k$-Vertex Cover and weighted clique counts.
A hypergraph $H = (V,E)$ describes a set system over a vertex universe $V$. Hypergraphs are increasingly popular in network science, as they represent interactions between subsets of vertices. A natural challenge is to design a data structure for $H$ to quickly answer basic questions about it, e.g. how many neighbors a vertex $v$ has or whether a hyperedge contains a vertex subset $S$. Such questions are trivial for graphs, for which we simply inspect the adjacency list. The gold standard, from a data structures perspective, would be near-linear time preprocessing and query answering in (poly)logarithmic time. Since this is unlikely for arbitrary $H$, we ask for well-motivated hypergraph properties that can make such a goal possible. We introduce bidegeneracy, a measure of hypergraph sparsity that strictly generalizes many other measures, including bounded degree, bounded rank, and bounded $\infty$-degeneracy. We show that bounded bidegeneracy yields fast hypergraph data structures. For a large set of fundamental queries, including their listing and sampling versions, we obtain near-linear preprocessing and (poly)logarithmic query time. Moreover, direct reductions from assumptions like the Orthogonal Vectors Conjecture suggest that, without assumptions on the input, these structures require almost-quadratic preprocessing or almost-linear query time. We use bidegeneracy to compute a compressed representation of $H$ and perform careful reductions to stabbing and searching problems in $\mathbb{R}^d$. Our framework significantly extends the well-studied "partial matching" problem of finding database entries through wildcard search. It also uncovers an intriguing connection between hypergraph sparsity, compression, and the complexity of hypergraph primitives. We also find remarkably low bidegeneracy in hypergraph datasets from the literature, suggesting practical consequences.
We study testing acyclicity of directed graphs in the bounded-degree incidence-lists model, where a tester can query the outneighbors of a vertex but not its inneighbors. Despite significant effort, no tester with $o(n)$ queries is known, while the best established lower bounds are $\widetilde\Omega(n^{5/9})$ for one-sided testers (Chen, Randolph, Servedio, and Sun, 2022) and $\Omega(n^{1/3})$ for two-sided testers (Bender and Ron, 2002). We show that a query exponent arbitrarily close to one is necessary: for every fixed $\eta\in(0,1)$, there exists a constant $\varepsilon_\eta>0$ such that, for every constant $d\ge2$, every randomized adaptive two-sided $\varepsilon_\eta$-tester for acyclicity of simple $n$-vertex directed graphs whose indegrees and outdegrees are at most $d$ makes $\Omega(n^{1-\eta})$ queries. Our proof overcomes two barriers. First, in previous constructions, the acyclic part of the graph is easy to recognize, which helps an algorithm stay inside the cyclic part. We hide a high-girth cyclic core inside a hierarchy of acyclic masking regions, in which each region imitates the levels below it and can be told apart from them only through rare events, and an iterated information-theoretic argument shows that every exploration observes only small, low-diameter forest components of the core. Second, a two-sided tester may exploit the statistics of collisions without ever seeing a cycle, and at a near-linear budget collisions are unavoidable. We compare complete transcripts with those of an acyclic input built on a fixed core by counting injective embeddings of the observed forest: in high-girth cores, all connected collision patterns of bounded order contribute identically, which makes the two transcript distributions statistically indistinguishable.
We study the problem of sorting on the Parallel Random Access Machine (PRAM), Parallel Comparison Model (PCM) and Parallel External Memory Model (PEM). On PRAM, we present a Concurrent Read Exclusive Write algorithm that runs in $O(\log n)$ time with $n$ processors; our algorithm is very different from Cole's Merge Sort. On PCM, we present the first optimal algorithm for sorting after AKS; our algorithm runs in $O(\log n/\log\alpha)$ comparison rounds with $n\alpha$ processors, for $1\leq\alpha\leq n$. On PEM, we present a Concurrent Read Exclusive Write algorithm that sorts $N$ elements in $O\left(\log\frac{N}{B}\right)$ I/O rounds with $p\geq \frac{N}{B}$ processors.
We study online metric facility location in the batched random-order model. An adversary partitions $n$ clients into $B$ nonempty batches, which arrive in uniformly random order. Each batch is revealed in full, and its clients must be connected to open facilities before the next batch arrives. Openings and assignments are irrevocable, and the objective is to minimize the total opening and connection cost. For both uniform and nonuniform opening costs, we prove that the tight competitive ratio is \[ \Theta\!\left(\min\left\{\log(B+1), \sqrt{\log(n-B+2)}\right\}\right). \] Thus, the ratio is constant both when there is a single batch and when every batch is a singleton, but intermediate numbers of batches can require a $\Theta(\sqrt{\log n})$ ratio. Our algorithms build on Meyerson's algorithm (2001) and do not need to know $n$ nor $B$. A key algorithmic novelty is that we process the clients in a batch one by one in uniform random order (hence neglecting the global properties of the batch). We present a novel analysis of this algorithm that hinges on the random order of the batches, as well as of the clients within each batch. We also provide a matching competitive ratio lower bound already for uniform costs, and even when the entire metric is known in advance.
We give an improved algorithm for weighted directed planar diameter that runs in $\widetilde{O}(n^{3/2})$ time. This improves upon the $\widetilde{O}(n^{5/3})$ time algorithm for weighted directed planar diameter of Gawrychowski, Kaplan, Mozes, Sharir, and Weimann [SIAM J. Comput. 2021] and the recent $\widetilde{O}(n^{8/5})$ time algorithm for unweighted undirected planar diameter of Fredslund-Hansen, Mozes, and Weimann [SOSA 2027]. The main new result is an improved data structure for computing the farthest vertex when given feasible planar distances to the vertices on the outer face. The critical insight is the fact that normalized distances to the vertices of a face behave like pseudolines, for which we can leverage range searching and upper envelope data structures. Using the farthest vertex data structure, we are able to compute all vertex eccentricities and diameter in $\widetilde{O}(n^{3/2})$.
We consider monotone submodular maximization subject to a matroid constraint. The seminal continuous greedy algorithm of Calinescu, Chekuri, P\'{a}l, and Vondr\'{a}k~[SICOMP'11] achieves the tight approximation of $(1-1/e)$. Since then, a line of works by Badanidiyuru and Vondr\'{a}k~[SODA'14], Buchbinder, Feldman, and Schwartz~[SODA'15 \& MOR'17], Kobayashi and Terao~[ICALP'24], Buchbinder and Feldman~[FOCS'24 \& SICOMP'25], and Buchbinder and Feldman~[STOC'25] has developed efficient $(1-1/e-\varepsilon)$-approximation algorithms for this problem. We present a combinatorial randomized $(1-1/e-\varepsilon)$-approximation algorithm that requires $\tilde{O}_{\varepsilon}(n)$ independence-oracle and value-oracle queries, where $n$ is the number of elements in the matroid. This is the first $(1-1/e-\varepsilon)$-approximation algorithm with both independence-oracle and value-oracle query complexities nearly-linear in $n$ and polynomial in $1/\varepsilon$. To achieve this, we develop a new local search algorithm, which we call \emph{protected local search}, based on the potential function of Buchbinder and Feldman~[FOCS'24 \& SICOMP'25].
Assigning applicants to posts in the presence of applicant preferences and quotas associated with posts is extensively investigated. For a post, a lower quota guarantees, and an upper quota limits the number of applicants assigned to it. Typically, quotas are assumed to be fixed, which need not be the case in practice. We address this by introducing a soft quota setting, in which every post is associated with two values - lower target and upper target - which together denote a range for the intended number of applicants in any assignment. Unlike the fixed quota setting, we allow the number of applicants assigned to a post to fall outside the range. This leads to assignments with deviation. Here, we study the problem of computing an assignment that has two orthogonal optimization objectives - minimizing the deviation (maximum or total) with respect to soft quotas and ensuring optimality with respect to preferences of applicants (rank-maximality or fairness). The order in which these objectives are considered, the different possibilities to optimize deviation combined with the well-studied notions of optimality with respect to preferences open up a range of optimization problems of practical importance. We present efficient algorithms based on flow networks to solve these optimization problems. We also consider a generalization of the soft quota setting, where every deviation is associated with a cost. We show extensions of our algorithms for solving the problems in this setting.
We study (non-induced) subgraph counting under interactive local edge differential privacy (LEDP). Given a fixed pattern graph $H$ with $k$ vertices, $\ell\ge1$ edges, and $q$ connected components, our goal is to approximately count its copies in an arbitrary $n$-vertex undirected graph while preserving edge privacy. We give two complementary accuracy guarantees. First, for every $H$, we give Linear Noise Cancellation (LNC), a two-round $\varepsilon$-LEDP algorithm with additive error and root mean square error both $O(n^{k-3/2}/\varepsilon^\ell)$ on every $n$-vertex graph. For fixed sufficiently small $\varepsilon$, this improves the optimal noninteractive additive error for triangles by a factor of $\sqrt n$ and gives the same improvement in worst-case root mean square error for all cliques on at least three vertices. To our knowledge, this is the first separation between interactive and noninteractive LEDP subgraph counting, showing that a single additional round can improve worst-case accuracy polynomially. Second, we determine how accuracy improves when the graph has maximum degree at most a public bound $d$. Our Predict and Correct (PC) framework gives an $(\ell+2)$-round $\varepsilon$-LEDP algorithm with additive error $O(n^{q-1/2}d^{k-q-1}\log^{3\ell-2}n/\varepsilon^\ell)$. For connected patterns, its polynomial factor is $\sqrt n\,d^{k-2}$, giving sublinear error on constant-degree graphs at fixed privacy. We prove matching lower bounds in $n$ and $d$, up to logarithmic factors at fixed privacy, even under arbitrary interaction and approximate privacy with sufficiently small $\delta$. At $d=\Theta(n)$, the lower bound also establishes the optimality of LNC's dependence on $n$.
In the semi-streaming model, the edges of an $n$-vertex graph arrive in a stream, and an algorithm makes multiple passes over that stream while using only $\widetilde{O}(n)$ space. The number of passes needed to compute single-source reachability in directed graphs is a long-standing open question in streaming algorithms, going back to Henzinger, Raghavan, and Rajagopalan (1998). The best known semi-streaming algorithm uses $n^{1/2+o(1)}$ passes due to Jambulapati, Liu, and Sidford (2019), while the best lower bound is $\Omega(\log n/\log\log n)$ passes due to Guruswami and Onak (2016). We give streaming algorithms for computing single-source reachability and shortest paths on $n$-vertex directed graphs using $\widetilde{O}(n)$ space and $n^{1/3+o(1)}$ passes. Our algorithms are based on implicit hopsets, which are large hopsets that can be represented implicitly in $\widetilde{O}(n)$ space. We introduce this notion and give new constructions for implicit hopsets with small hopbound. Along the way, we obtain new work-depth tradeoffs for parallel shortest paths in directed graphs, improving the recent result of Ashvinkumar, Bernstein, Probst Gutenberg, and Saranurak (2026).
We show that for any fixed $k$, there exists $\varepsilon_k > 0$ such that, given a $(k-1)$-uniform hypergraph $H$ on $n$ vertices, one can count the number of $k$-hypercliques in $H$ in $O(n^{k-\varepsilon_k})$ time. This refutes the hyperclique conjecture of Lincoln, Vassilevska Williams, and Williams (SODA 2018). Our result follows from the uniform construction of a family of arithmetic circuits of size $O(n^{k-\varepsilon_k})$ for the $k$-hyperclique tensor, a natural higher-order generalization of the matrix multiplication tensor. We obtain two corollaries. First, for every $k$, there exists $\varepsilon > 0$ such that Max-$k$SAT can be solved in $2^{(1-\varepsilon)n} \cdot \mathrm{poly}(m,n)$ time. Second, for every $k$, there exists $\varepsilon > 0$ such that arithmetic progressions of length $k$ in subsets of $\{0,1,\ldots,n\}$ can be detected in $n^{2-\varepsilon}$ time. Both corollaries refute other prominent conjectures in the literature.
In classical gossiping, each participant initially knows a distinct piece of information. Whenever two participants call each other, they exchange everything they know. We study Gossiping: given an undirected multigraph whose vertices represent participants and whose edges represent available calls, decide whether the calls can be ordered so that every participant learns all information, using each edge at most once. Equivalently, can one time label per edge make the graph temporally connected by strict temporal paths? This recognition problem is NP-complete; we study its parameterized complexity. After linear-time preprocessing, we give an exact $O(3^{n/3}n^3)$-time algorithm and a deterministic $2^{O(tw)}n$-time algorithm, where $n$ is the number of vertices and $tw$ is the treewidth of the underlying simple graph. We introduce a Tree Contraction Rule that extends the treewidth algorithm to single-exponential algorithms for parameters that may remain small on dense graphs, such as tree-independence number and clique-width, without requiring a decomposition as input. For the excess $\delta=m-(2n-4)$ over the minimum number of calls, where $m$ is the number of edges, we give a randomized $2^{O(\delta)}n^3$-time algorithm with one-sided error. Its main subroutine solves Rooted Independent Cycle: finding a cycle through four prescribed vertices whose edges are independent in a represented linear matroid. We solve this problem deterministically in $2^{O(r)}m$ arithmetic operations over the finite field representing the matroid, where $r$ is its rank. Gossiping is polynomial-time solvable at maximum degree four, counting parallel edges, but NP-complete on planar simple graphs of maximum degree five. The treewidth algorithm yields a $2^{O(\sqrt n)}$-time algorithm on planar graphs.
Using the bisection bound of Monien and Preis, Fomin and H{\o}ie proved in 2006 that every graph of maximum degree 3 on $n$ vertices has pathwidth at most $n/6+o(n)$. We prove that the pathwidth, bisection width and cutwidth of these graphs are at most $c_3 n+o(n)$, where $c_3=\frac{3}{4\pi}\arccos\frac56\approx0.1398$. For bisection width this improves the bound $n/6+o(n)$ of Monien and Preis (2006) and extends to all such graphs the bound that Lichev and Mitsche (2023) obtained for random cubic graphs. For maximum degree 4, we prove that bisection width and cutwidth are at most $n/3+o(n)$, improving the bound $2n/5+o(n)$ of Monien and Preis for 4-regular graphs, and that pathwidth is at most $0.2458n$, improving the bound $n/3$ of Fomin, Gaspers, Saurabh and Stepanov (2009). We show that every graph with $m$ edges has pathwidth at most $7m/48+o(n)$, improving the bound $13m/75$ of Scott and Sorkin (2007), and we give further bounds of the form $\sum_{d\ge3}a_d n_d+o(n)$ with $a_d<1$, where $n_d$ is the number of vertices of degree $d$. The path decompositions, and linear orderings of the stated cutwidth, can be computed in polynomial time. Instead of deriving pathwidth bounds from bisection width, we give each vertex a Gaussian label, a weighted sum of independent standard normal variables over a ball around it, and sweep a threshold through the labels; the bags are frontiers, the vertices above the threshold with a neighbor below it. We bound the probability that a vertex lies in a frontier by comparison with an explicit Gaussian model of a vertex and its neighbors. Faster exact algorithms follow: for feedback vertex set and the traveling salesperson problem on graphs of bounded maximum or average degree, and on general graphs for minimum weight dominating set (by branching until the instance is sparse), Max 2-CSP and counting subgraphs with $k$ edges (by the bound in $m$).
We prove that every connected $n$-vertex graph admits a probabilistic embedding into its spanning trees with expected distance stretch $O(\log n)$. This settles the logarithmic stretch conjecture of Alon, Karp, Peleg, and West, whose spanning-tree game appeared at the 1991 DIMACS Workshop on On-Line Algorithms and in SIAM Journal on Computing in 1995. A weighted form of the theorem also yields a distribution over spanning trees with capacities exactly equal to their fundamental graph cuts. Every tree dominates every graph cut, every cut is approximated within $O(\log n)$ in expectation, and the same capacity distribution defines an $O(\log n)$-competitive fractional oblivious routing. The distance and capacity distributions may differ. Diamond graphs give matching logarithmic lower bounds for stretch, congestion, and cut distortion. For rational input, both distributions are constructed deterministically in polynomial time and use at most $m$ trees, where $m$ is the number of graph edges. We prove an $\Omega(m/\rho)$ support lower bound for congestion $\rho$; in particular, $(1-o(1))m$ trees can be necessary for near-unit congestion, even when the optimum tends to one. Thus linear dependence on $m$ is unavoidable in this regime. The weighted theorem combines a protected-geodesic petal decomposition with a pathwise entropy bound for locally selected centers. A local averaging inequality derandomizes the radii, and an adaptive rational packing procedure constructs the distributions.
Let $\mu$ be a probability distribution on a spin system with $n$ sites and possibly infinite spin spaces. We prove local-to-global spectral-gap bounds for block Glauber dynamics. Given a symmetric, entrywise nonnegative matrix $A$ with zero diagonal and $\lambda_{\max}(A)<1$ encoding local spectral bounds for a spin system, we derive global spectral-gap bounds for block dynamics on its marginal distributions. These bounds are sharp: the Gaussian system with covariance $(I-A)^{-1}$ attains equality for every choice of disjoint blocks. Our proof extends the Bochner method through an abstract inequality for orthogonal projections on Hilbert spaces. As an application, we prove that Glauber dynamics for the $O(N)$ model, with $N\geq 2$, arbitrary external fields, and couplings of either sign, has spectral gap at least $(1-\|J_{\mathrm{abs}}\|_{\mathrm{op}}/N)/n$, where $J$ is the interaction matrix and $J_{\mathrm{abs}}=(|J_{ij}|)$. We also obtain spectral bounds for swap walks and local spectral expansion of partite simplicial complexes. For complexes formed from disjoint groups of ranks in random flags of subspaces over $\mathbb F_q$, we obtain a one-sided local spectral expansion bound of $2\sqrt q/(q+1)$. This bound is independent of the number and sizes of each group, and is nontrivial for every prime power $q$. Finally, for random forests $F$ of any finite graph with arbitrary positive edge weights, we prove that \[ \Pr(e,f\in F)\le \frac{4}{3} \Pr(e\in F)\Pr(f\in F) \] for distinct edges $e,f$, improving the factor 2 supplied by general log-concavity bounds for matroid independent sets. The argument combines our extended Bochner method with the analysis of an auxiliary real stable polynomial.
We study two fairness objectives for allocating $m$ indivisible items among $n$ agents with subadditive valuations: the max-min objective, also known as the Santa Claus problem, which maximizes the smallest value of an agent, and the weighted Nash social welfare, which maximizes the weighted geometric mean of the agents' values. For the max-min allocation problem, we give a randomized polynomial-time $O(\sqrt n)$-approximation algorithm for subadditive valuations with demand queries, improving the $2n-1$ bound of Khot and Ponnuswami. For additive valuations and for submodular valuations with value queries, we give simpler $O(\sqrt n)$-approximation algorithms. For additive valuations, this improves the $O(\sqrt{n\log n})$ bound of Saha and Srinivasan. For these two classes, $O(m^\varepsilon)$-approximation algorithms are also known for every constant $\varepsilon>0$. Our ratios depend only on $n$ and match, up to constants, the $\Omega(\sqrt n)$ integrality gap of the configuration LP. For the weighted Nash social welfare problem with subadditive valuations and demand queries, we give an $O(\Gamma(w))$-approximation algorithm, where $\Gamma(w)=\exp\bigl((\ln n-H(w))/2\bigr)$ and $H(w)$ is the entropy of the weight vector $w$. The factor $\Gamma(w)$ equals $1$ for equal weights and is at most $\sqrt n$ for all weights. We show that this ratio is tight for algorithms analyzed against the configuration LP: for every weight vector, the configuration LP has an integrality gap of $\Theta(\Gamma(w))$, even for XOS valuations, and this gap is $\Omega(\sqrt n)$ when one agent has almost all the weight. For submodular valuations, the configuration LP has a constant integrality gap for all weights.
A defining feature of the linear-probing hash table is its spatial locality: at load factor $1 - \varepsilon$, the hash table can be implemented so that each operation scans a single contiguous region of expected size $O(1/\varepsilon)$ (this is known as the \emph{scan cost}). This guarantee, however, relies on all items having unit size. In this paper, we ask whether it is possible to achieve a similar guarantee, but in a hash table that stores items of arbitrary lengths $|x| \ge 1$. The main result of the paper is a new hash table called \emph{Catalan hashing}, which supports amortized expected scan cost $O(|x|/\varepsilon)$ for positive queries, $O(1/\varepsilon)$ for negative queries, and $O(|x|\varepsilon^{-1}\log^{1+\delta}|x|)$ for insertions/deletions, for any constant $\delta > 0$. As a corollary, we obtain the same bounds in the cache-oblivious model, with a scan cost of $S$ translating to $1 + O(S/B)$ I/Os. Along the way, we introduce several high-level techniques that may be of independent interest; this includes a novel way of using erasure codes in order to perform write optimization within a hash table, and a connection to scheduling that allows us to place elements in a way which avoids clustering at high load factors.
We introduce Gaussian partitioning, an algorithmic primitive for distributions smooth with respect to a Gaussian. It partitions space into polyhedral regions so that almost all mass lies in thin strips restricting a few orthogonal directions. Within each strip, the conditional distribution approximately matches low-degree Gaussian moments in the unrestricted directions. Our construction builds on logconcave partitioning of Diakonikolas, Kane, and Ma (FOCS 2026). Under input marginals smooth with respect to the standard Gaussian, we obtain agnostic learners with error $(1+c)\mathrm{opt}+\epsilon$ for broad classes of Boolean multi-index models, including functions of halfspaces, low-dimensional convex concepts, and low-dimensional polynomial threshold functions. For functions of $k$ halfspaces, both agnostic and testable agnostic learners achieve this error with dimension dependence $d^{\mathrm{poly}(k/c)}$, improving the previous exponential dependence on $k/c$ in the agnostic exponent. For learning from positive examples with imperfect unlabeled data (PUI), we give algorithms and Statistical Query (SQ) lower bounds that qualitatively characterize complexity through Gaussian moment matching. For fixed smoothness and positive-mass parameters, we learn intersections of $k$ halfspaces with dimension dependence $d^{O(\log(k/\epsilon))}$ and matching SQ lower bounds, improving the previous $d^{\mathrm{poly}(1/\epsilon)}$ upper bound even for one halfspace. A general reduction from agnostic reliable learning to PUI yields negative reliable learners for these intersections with the same dimension dependence, for fixed smoothness. Finally, for PQ learning and testable learning with distribution shift, we prove qualitatively optimal SQ lower bounds of $d^{\Omega(1/\epsilon^2)}$, even for intersections of two halfspaces with Gaussian training data and arbitrary test distributions.
We study approximation algorithms for All-Pairs Shortest Paths (APSP) in directed graphs under the roundtrip metric. In directed graphs, even finite-factor approximation of ordinary one-way distances must distinguish reachable from unreachable vertex pairs, and therefore computes transitive closure, a problem equivalent to Boolean matrix multiplication (BMM) under standard reductions. The roundtrip distance, defined as $\text{dist}_G(u \leftrightarrows v) = \text{dist}_G(u \to v) + \text{dist}_G(v \to u)$, offers a natural and robust relaxation. It measures the cost of traveling from $u$ to $v$ and back, satisfies the triangle inequality, and is inherently symmetric. While this metric has become central to the study of directed roundtrip spanners and compact routing, the fundamental problem of all-pairs roundtrip distance approximation has remained largely unexplored. In this work, we present a comprehensive study of roundtrip APSP and distance oracles, presenting several new lower and upper bounds. On the algorithmic side, our main result is a combinatorial algorithm that computes a stretch-$3$ approximation to all-pairs roundtrip distances in $\widetilde{O}(n^2 + \min\{m\sqrt{n},\, m^{1/3}n^{5/3}\})$ time. For edge weights in $[1,W]$, we also obtain a $(3+\varepsilon)$-approximation in $\widetilde O((n^{2.037}+nm^{2/3})\log(nW)/\varepsilon)$ time and a $(4+\varepsilon)$-approximation in $\widetilde O(n^{2.032}\log(nW)/\varepsilon)$ time using fast matrix multiplication. On the hardness side, we show that any stretch below $3$ would imply a breakthrough for BMM. We also obtain additional tradeoffs between stretch and running time.
This note is an exposition of the recent preprints from OpenAI that establish the bound $\omega \leq 9/4$ on the matrix multiplication exponent. We argue that the heart of these preprints is a new technique, which we formulate as the untwisting lemma for semidirect sums of tensors. This gives a generally applicable method for analyzing tensors. We also discuss further consequences of this method, as well as the relation between the OpenAI proof and previous work.
The vertices of a Boolean birthday graph are partial assignments on $\ell$-subsets of $n$ variables. Although a satisfying assignment induces a $K$-clique for $K=\binom n\ell$, an arbitrary selection of $K$ vertices may repeat some views and omit others. This makes soundness substantially harder than under uniform view sampling. For bounded-occurrence, constant-gap Boolean ternary CSPs whose constraints each involve three distinct variables (allowing arbitrary Boolean predicates), we prove that the graph's maximum induced $K$-vertex density satisfies \[ \rho^*(K)\le 2\exp\!\left(-c\, \frac{\ell^3}{n^2\log(en/\ell)}\right) \] for $2\le\ell\le x_0n$ and $\ell\log(en/\ell)\ge C_0\log(n+1)$, with positive constants depending only on the source parameters. The argument refines the biclique counting method by charging the entropy of an adversarially chosen flattening to mutual information and a combinatorial obstruction energy. In the overlapping parameter range it strengthens the explicit soundness exponent previously established for this graph. We also establish an unconditional stability theorem for arbitrary sets $H$ of exactly $K$ distinct local assignments, with missing views and multiple answers: $f_*(H)\le34(n/\ell)q_{\mathrm{con}}(H)$ for every $1\le\ell\le n$. It gives a complementary additive near-clique soundness bound. We do not derive a new fine-grained hardness theorem.
We study the following family of search problems: given a system of equations $x+y+z\equiv 0\pmod p$ promised to admit a solution that is nonconstant on every equation, find a $c$-colouring of the variables that makes no equation monochromatic. For $p\in\{2,3\}$, the problem recovers known tractable Promise Constraint Satisfaction Problems (PCSPs). For $p > 3$, we obtain a complete complexity classification: the problem is polynomial-time solvable for $c \geq 4$, yet even its decision version is NP-hard for $c = 3$, and it is not well-defined for $c = 2$. Our main conceptual contribution is a general tractability framework for PCSPs based on Abelian embeddings, a notion introduced by Bhangale, Khot, and Minzer [STOC 2022] in the study of quantitative approximation of satisfiable CSPs. We show that suitable Abelian embeddings yield polynomial-time PCSP reductions realised by singleton algorithms in the sense of Zhuk [FOCS 2026]. On the hardness side, the promise relation is far removed from the reconfigurable regime covered by the conditional hardness framework of Banakh, Barsukov, and Nakajima [LICS 2026]; our proof instead relies on a new additive-combinatorial rigidity theorem classifying special $3$-colourings of $\mathbb{Z}_p$.
Let $f\in\mathbb Z[x]$ be a polynomial of degree $n$ with integer coefficients of absolute value less than $2^b$. Using Pan's approximate factorization theorem, we give a deterministic algorithm that finds all distinct integer roots of $f$ in $\widetilde O(nb)$ bit operations. This matches the bit size of the input up to logarithmic factors and does not require $f$ to be square-free. Since we were unable to verify parts of the running time analysis of Pan's theorem, we also give a self-contained deterministic algorithm with running time $\widetilde O(nb+\min(n,b)^3b^2)$, which is $\widetilde O(nb)$ whenever $b\leq n^{1/4}$. This answers a question of Harvey and Hittmeir (2022), who asked whether integer roots can be found deterministically in quasilinear time, conditionally on Pan's theorem, and unconditionally for $b\leq n^{1/4}$. The fastest previous deterministic algorithm, due to Nir, takes $\widetilde O(n^{3/2}b)$ bit operations and works only for square-free polynomials. Instead of $p$-adic lifting, we combine approximate complex root finding with exact polynomial evaluation. We first approximate the complex roots of the polynomial formed by the top $\min(n,b)+1$ coefficients of $f$. Every integer root $r$ of $f$ with $|r|\geq 2$ lies within distance $2$ of some complex root of this truncated polynomial. Rounding the real parts of the approximate roots therefore gives a list of $O(\min(n,b))$ candidate integers that is guaranteed to contain all integer roots of $f$. Although a single candidate can have up to $b$ bits, a bound via the Mahler measure shows that the bit lengths of all candidates sum to $O(b)$. This allows us to test all candidates by exact multipoint evaluation in $\widetilde O(nb)$ bit operations.
We study the geometric bin packing problem for simple polygonal regions, i.e., non-degenerate, connected, rational regions, in the minimum number of unit-square bins, allowing only translations. We even consider packing general non-convex objects, possibly with holes, where we can then pack smaller objects. Previous schemes cover squares (MOR'06), circles and other $L_p$-balls (Algorithmica'16), sufficiently skewed rectangles (Algorithmica'23), and convex fat objects with a constant number of distinct shapes under resource augmentation (arXiv'24, WAOA'23). The result for circles and other $L_p$-balls needs bin augmentation to obtain rational packing realizations. For restricted classes of $L$-shaped polygons, Gerlach et al. (SoCG'26) give constant worst-case guarantees, while for general non-convex objects, bounding-box reductions give just approximation factors that depend on fatness. Against this background, we present a general framework that provides asymptotic polynomial-time approximation schemes (APTAS) for bin packing of any fixed class of simple polygonal regions satisfying just two assumptions. First, covering any object by the grid cells intersecting its interior in any sufficiently fine square grid, relative to the object's bounding box, increases its area by at most a small fraction. Second, the class can be partitioned into a constant number of sequences such that each object in a sequence can be translated to fit inside every preceding object. In particular, certain classes of star-shaped polygons and more general polygonal regions, including some with simple holes, satisfy both assumptions. In addition, our framework does not require a bound on the objects' boundary complexity. We emphasize that our results require no bin augmentation whatsoever and yield explicit, exact rational packings of polynomial encoding length for all input objects.
We study randomized allocations (lotteries) of indivisible chores under additive costs and introduce the notion of MMS1, which requires each agent's bundle to satisfy the maximin share (MMS) bound after the removal of at most one chore. Our main result establishes that every instance admits an ex-ante proportional lottery in whose support every allocation is MMS1 and all but $o(n)$ agents satisfy MMS. Consequently, every realized allocation can be made MMS by disposing of at most $o(n)$ chores. The proposed framework further achieves ex-ante proportionality alongside ex-post $4/3$-MMS, $o(n)$-AMMS, or $1$-out-of-$d$ MMS for $d=(1-o(1))n$. These guarantees substantially improve upon state-of-the-art bounds for MMS allocation for chores with disposal or subsidy, best-of-both-worlds fairness, approximate AMMS, and ordinal MMS approximations.
We study deterministic algorithms for locally checkable graph problems in the synchronous LOCAL model with crash failures, where a crashing node may send messages to only some neighbors. We introduce consistent neighborhoods: partial radius-$R$ views that agree locally across surviving edges and are complete without crashes. For $R=T+\ell+1$, these views allow local simulation of $T$-round fault-free algorithms that remain correct on subgraphs, satisfying constraints wherever the radius-$\ell$ checking neighborhood contains no crash. On graphs with at most $n$ nodes and maximum degree at most $\Delta\geq3$, we construct these views in $O(\min\{n,(\Delta-1)^R,R\Delta f\})$ rounds when a crash bound $f\geq1$ is globally known; the first two bounds require no knowledge of $f$. For $\Delta=2$ or girth greater than $2R$, including forests, $O(R)$ rounds suffice. Our upper bounds are essentially tight in suitable parameter regimes. One crash can force $\Omega(n)$ rounds even for $R=3$ on diameter-two graphs. For each fixed $\Delta\geq3$ and sufficiently large $R$, we prove a $(\Delta-1)^{R-O(\sqrt R)}$ lower bound even with crashes restricted to round beginnings. We also prove an $\Omega(\Delta Rf)$ lower bound when $R\geq4\lceil\log_{\Delta-1}f\rceil+4$ and $n\geq\Delta Rf$. For locally checkable labeling (LCL) problems, we preserve $O(\log^* n)$ complexity under any number of crashes whenever this bound holds without faults on all graphs with a fixed degree bound. In contrast, we construct an LCL on graphs of maximum degree at most five with fault-free complexity $\Theta(\log n)$ and crash-tolerant complexity $\Theta(n)$. Finally, any fault-free sinkless-orientation algorithm can be transformed to tolerate any number of crashes with only one additional round, guaranteeing correctness even at surviving nodes adjacent to crashes.
The Nash-Williams--Tutte theorem characterizes the existence of $k$ edge-disjoint spanning trees by a condition on every vertex partition. We prove that, for simple graphs, the same condition guarantees $k$ edge-disjoint spanning trees, each of diameter $O(n/\delta)$ and with $O((n/\delta)\log(\delta+1))$ internal vertices, where $n$ is the number of vertices and $\delta$ is the minimum degree. Both bounds hold simultaneously for every tree, with absolute implicit constants independent of $k$, and each is asymptotically optimal in general. Our proof is constructive and yields a randomized algorithm with expected running time $\tilde{O}(n^5)$. We derive applications to short edge-disjoint routes and weak linkages, small Steiner trees, and survivable networks with short paths. The joint bounds also yield low-diameter spanning Eulerian subgraphs and short tours for postman and general routing problems.
We give an algorithm for PAC learning intersections of $k$ degree-2 polynomial threshold functions over $R^d$ under a Gaussian distribution. Our algorithm achieves classification error $\epsilon$ using $d^{O(k)}2^{O_k(\log^3(1/\epsilon))}$ time and samples, improving over the $d^{O(k^2/\epsilon^2)}$ running time of the polynomial regression approach. To our knowledge, our result is the first to obtain a dimension exponent independent of the accuracy parameter, even for $k=2$. We complement our algorithmic result with an SQ lower bound showing that the complexity dependence of $d^{\Omega(k)}$ is unavoidable. Lifting the input to polynomial features turns the target into an intersection of $k$ halfspaces. This suggests using the first two labeled moments for subspace recovery. In the lifted space, however, these moments can reveal nothing. Our starting point is a Gaussian comparison theorem showing that, for sufficiently regular defining quadratics, the labeled moments needed for subspace recovery are approximately preserved. To handle arbitrary defining quadratics, we establish a new structural result showing that every direction with significant resampling influence can be detected through degree-$O(k)$ moments. These results yield an initial $d^{O(k)}2^{\mathrm{poly}_k(1/\epsilon)}$-time learner using adaptive restrictions. To improve the exponential dependence on $1/\epsilon$, we develop a two-stage dimension-reduction approach that avoids the costly adaptive partitioning. After identifying a subspace containing all directions with large influence, we use generalized regularity and Gaussian comparison to recover the remaining relevant quadratic features through a new derivative-based moment operator. The recovered features support an intersection close to the target. Combining them with robust hinge-loss minimization gives our quasipolynomial-time learner.
We prove a quantum analogue of the classical moment matching method, a popular framework used to prove lower bounds in property testing. For two random variables $X_0$ and $X_1$ whose moments match up to the first $r-1$ moments, the classical moment matching method says that no classical algorithm can reliably distinguish between input instances of length $N$ constructed from $X_0$ and $X_1$, respectively, unless it performs at least $\Omega(N^{1-1/r})$ queries. While this method has been widely explored since its inception in the seminal work of Raskhodnikova, Ron, Shpilka, and Smith (STOC 2007) to prove lower bounds for symmetric properties, it has remained an open question whether a quantum analogue of it could be proved. We prove two variants of this quantum moment matching method, which are incomparable. Our first quantum query lower bound scales as $\Omega(N^{1/2-1/(2r)})$, while our second moment matching theorem yields a sharper lower bound of $\Omega(N^{1/2-1/(2(2^r-1))})$, albeit for smaller parameter ranges. Our results combine a new continuous hybrid argument with the polynomial method. The continuous hybrid argument compares two hard input distributions generated from i.i.d. samples by continuously varying both distributions, keeping them identically distributed at every intermediate stage. It reduces the comparison to the effect of changing the distribution of a single sample. The polynomial method then cancels the terms determined by the matched moments. We apply these moment matching theorems to prove new optimal lower bounds on $k$-distinctness, $k$-star-freeness, planarity and outerplanarity testing, as well as to improve prior lower bounds on image size testing and $K$-junta testing by logarithmic factors. A key advantage of our framework is its simplicity: it reduces quantum lower bound proofs to the construction of suitable moment-matching distributions.
Colonel Blotto is a fundamental resource-allocation game in which two players divide their budgets across battlefields, and the higher allocation on each battlefield wins its value. The problem of computing an equilibrium efficiently has remained unresolved for its classical continuous version with arbitrary budgets and with values that may vary across battlefields but are the same for both players. We give a fully polynomial-time approximation scheme that computes an $\varepsilon$-Nash equilibrium in time polynomial in the input length and $1/\varepsilon$, and nearly linear in the input length for fixed $\varepsilon$. For sufficiently balanced budgets and battlefield values, we also compute exact equilibria in linear time.
Given a class of machine learning models and sample access to a data distribution with binary labels, which computational task is harder: training a discriminative model that distinguishes positive and negative labels as well as the best member of the class, or training a generative model whose outputs are indistinguishable from real data by all members of the class? We prove that these two fundamental tasks in computational learning theory are not just closely related, but actually equivalent to each other in complexity. One direction of this equivalence was previously known. Indeed, the powerful regularity lemma in complexity theory gives an efficient oracle reduction from the indistinguishability task (a.k.a. multiaccuracy) to the distinguishing task (a.k.a. agnostic learning) in the style of boosting algorithms. Our main contribution is an efficient oracle reduction in the other direction. Taking this idea further, we show that a multiaccuracy oracle is a remarkably powerful primitive, achieving not just agnostic learning but also a wide range of seemingly more demanding learning objectives via similarly efficient and direct constructions. Our results crucially use the power of making adaptive queries to the oracle, and stand in stark contrast to prior work, which showed that post-processing a single multiaccurate predictor is insufficient for even weak forms of learning. On a technical level, we draw a connection between our (offline) problem and a version of no-regret learning in the online setting, which allows us to use follow-the-leader type algorithms to modify the label distribution and aggregate the predictions of the multiaccuracy oracle.
In the graph collision problem, the task is to decide whether a known graph on $n$ vertices contains an edge with both endpoints marked, given query access to the input bits specifying the marked vertices. We first refute the conjectured $\Omega(n^{2/3})$ query lower bound with a bounded error quantum algorithm using $\widetilde O(n^{92/139})$ queries. We then refine this approach to obtain a $\widetilde O(n^{11/17})$ query algorithm. We also obtain a $\widetilde O((nq)^{11/17})$ query bound for all (partial) Boolean output functions with positive certificate complexity at most 2 and alphabet size $q$, contrasting a known $\Omega(n^{2/3})$ lower bound for such problems with large alphabet sizes. We complement these algorithms with an $\Omega(\sqrt{n\log n})$ quantum query lower bound for graph collision, exceeding the $O(\sqrt n)$ certificate complexity barrier for the positive adversary method.