Papers

In this work, we prove that computing the edge ranking of a tree in parallel is P-Complete. An optimal tree edge ranking assigns positive integer ranks to the edges such that any two edges with the same rank are separated by an edge of higher rank, while minimizing the highest rank. Tree edge ranking abstracts several classical problems such as parallel assembly in manufacturing, minimum-height dendrograms, reversible pebble game and edge-query binary search on trees. Its parallel complexity remained open for over thirty years, since the seminal work of de la Torre, Greenlaw, and Schäffer [SODA'93], and was listed as an open problem in the book Limits to Parallel Computation by Greenlaw, Hoover, and Ruzzo [1995]. We prove that deciding whether a tree has edge ranking at most $K$ is P-Complete, already for trees of diameter six. Our reduction is from NOR-CVP and simulates a greedy procedure underlying known sequential approaches. Despite ruling out NC algorithms, we prove that this hardness barrier can be bypassed in the well-known model of Massively Parallel Computation (MPC) with strongly sublinear local memory, showing that $O(\log n)$ MPC rounds suffice to solve the hard tree-edge ranking instances used to prove P-Completeness. Specifically, we present a deterministic MPC algorithm that computes an optimal edge ranking of an $n$-vertex tree of diameter $D$ in $O(\log D+\log\log n)$ rounds with $O(n^{3/4}D^{1/4})$ local memory. Our algorithm circumvents the linear-memory barrier by compressing the information required to produce a lexicographically minimal ranking from subtree merges. Overall, this result reinforces the strict separation between NC and what can be computed efficiently in MPC.

Large-scale information retrieval systems, including retrieval-augmented generation (RAG) and recommendation engines, widely use multi-layered hierarchical data structures for ultra-fast approximate nearest-neighbor search in high-dimensional vector spaces. However, the geometric conditions that ensure accurate and efficient greedy navigation remain poorly understood. In this work, we study the efficiency of greedy navigation on a hierarchy of proximity graphs constructed from \(n\) data points on the \(d\)-dimensional torus~$\mathbb{T}^d$. We identify a deterministic coverage condition under which, given any query $q\in \mathbb{T}^d$, greedy search returns a point within $(1+\varepsilon)$-factor of the distance to the closest point. This coverage property holds with high probability when the data is distributed as a homogeneous Poisson process, a Hermitian determinantal process, or a bounded-density Cox process, as long as $d = o(\log n/\log \log n)$. Under the same assumptions, the expected number of greedy hops for a fixed query is \(O\!\left(\exp\!\left(\tfrac12 d\log d+O(d)\right)\log n\right)\), yielding logarithmic expected hop count in fixed dimension.

We identify explicit closed-form and variational formulae for interpolating the exact values and derivatives through order $s$ of a $C^{s,1}$ function $f:\mathbb{R}^d\to\mathbb{R}$ at $N$ distinct points in $[0,1]^d$. The reconstruction satisfies bounds on its global $C^{s,1}$ seminorm and its Lipschitz constant on $[0,1]^d$ that are independent of the sample size $N$, the latter being the sharp Whitney condition. For $s\ge2$, the reconstruction is real analytic away from the data points and definable in the o-minimal structure $\mathbb{R}_{\exp}$. Our nonlinear extension formula coincides with the formula of McShane (1934) for $s=0$ and with the formulae of Le Gruyer and Phan (2015) and Azagra, Le Gruyer, and Mudarra (2018) for $s=1$, and is new for $s\ge2$. For fixed $d$ and $s\ge2$, our closed-form formula is computable away from the data points by a circuit using only elementary unary and binary real operations, with $\mathcal{O}(N)$ gates and $\mathcal{O}(\log N)$ depth. This yields $\mathcal{O}(N)$ storage and $\mathcal{O}(\log N)$ parallel evaluation time. From the supplied coefficients and weights, the circuit can be compiled with $\mathcal{O}(N)$ one-time work in the exact-real word-RAM model. Thus, in this supplied-data setting, our nonlinear construction improves by a logarithmic factor on the $\mathcal{O}(N\log N)$ initialization bound of Fefferman and Klartag (2009), while retaining linear storage and attaining logarithmic query time through parallel evaluation.

We study vehicle routing with vehicles of different speeds on a complete undirected graph whose vertex set consists of a depot and a set of clients, where the distances satisfy the triangle inequality. Each vehicle has a specified speed, and if the total length traveled by a vehicle of speed $s$ is $L$, its completion time is $L/s$. In the heterogeneous traveling salesman problem (HetTSP), each vehicle executes one tour starting and ending at the depot, and the tours collectively visit all clients. The objective is to minimize the maximum completion time among the vehicles. We give a $6$-approximation algorithm for HetTSP, improving the previous $90(1+\delta)$-approximation for any fixed $\delta>0$. We also consider two versions of the heterogeneous capacitated vehicle routing problem (HetCVRP). Each client has a demand, and the vehicles have identical capacities. A vehicle may execute several tours, each starting and ending at the depot, and reload at the depot between consecutive tours; the total demand delivered on each tour cannot exceed the vehicle capacity. In the split-delivery version of HetCVRP, the demand of a client may be divided among multiple visits, possibly by different vehicles. We give a $\frac92+2\sqrt3<7.965$-approximation algorithm for this problem. In the unsplit-delivery version of HetCVRP, the entire demand of each client must be delivered in a single visit. We give a $\frac{11}{2}+3\sqrt2<9.743$-approximation algorithm, improving the previous $450(1+\delta)$-approximation for any fixed $\delta>0$.

The Simplex method is among the most widely used approaches for solving linear programs. Starting at a vertex solution of the feasible region, the algorithm proceeds through a sequence of basis exchanges (known as pivots), each corresponding to a move along an improving edge of the polyhedron toward a better vertex. A central challenge affecting the efficiency of the Simplex method is degeneracy, which can cause long sequences of pivot operations that fail to change the current vertex solution. In this paper, we prove the existence of a pivot rule which is able to escape degeneracy and follow any given shadow edge-direction when initialized at some compatible basis, with a linear number of degenerate Simplex pivots. As a byproduct of our result, we obtain an improved bound on the number of degenerate Simplex pivots needed to solve linear programs defined on 0/1 polytopes.

While there have been many recent advances in getting better tradeoffs for directed distance structures such as hopsets, shortcut sets and distance preservers, most known algorithms are inefficient. In this work we provide three results: - Faster algorithms for directed $(1+\epsilon)$-hopsets, matching the state-of-the-art size/hopbound trade-offs of Bernstein & Wein [SODA23]. Our algorithm is first designed for DAGs and then extended to general graphs (up to $n^{o(1)}$ factors) using the recent DAG projection result of Haeupler, Jiang, and Saranurak [STOC26]. - Faster deterministic algorithms for constructing shortcut sets, matching the state-of-the-art size/hopbound tradeoffs of Kogan & Parter [SODA22A]. - Using our improved directed hopset construction, we get significantly faster algorithms for computing source-wise distance preservers. This algorithm is based on speeding-up reductions of Kogan & Parter [SODA22B] by using certain structural properties of our hopsets.

In this paper, we refine the dynamic programming framework based on the sphere cut decomposition designed by Dorn, Penninkx, Bodlaender, and Fomin (ESA 2005) to obtain faster subexponential algorithms for connectivity problems on planar graphs. We investigate the relationship between these problems and meanders, which are simple closed planar loops that intersect a fixed line in a given number of points. By combining dynamic programming with techniques from meandric system analysis and the use of fast matrix multiplication by Dorn (ESA 2006), we obtain improved algorithms for planar connectivity problems. We show that the number of meanders on $2n$ crossings $M_n$ is $\mathcal O^*(12.806^n)$, which improves the previous upper bound of $\mathcal O^*(12.901^n)$ by Albert and Paterson (FPSAC 2004). This then gives the best-known classical upper bounds on the deterministic time complexity of several planar graph problems with polynomially-bounded weights, namely $\mathcal O(2^{5.543\sqrt n})$ for the Planar Travelling Salesman problem, $\mathcal O(2^{5.796\sqrt n})$ for Planar Longest Cycle/Path, $\mathcal O(2^{8.251\sqrt n})$ for Planar Connected Dominating Set and $\mathcal O(2^{8.037\sqrt n})$ for Planar Steiner Tree. Notably, this leads to the best-known deterministic complexity $\mathcal O(2^{5.543\sqrt{n}})$ for the Planar Hamiltonian Cycle problem.

Selection is a task that chooses one element from a finite public candidate range to maximize a data-dependent score. In differential privacy (DP), the exponential mechanism (EM) samples a candidate at a temperature calibrated to the global sensitivity. In this paper, we study when dataset-dependent sensitivity can safely replace global sensitivity in private selection. We propose three valid approaches. First, a private, high-probability upper bound on local sensitivity yields approximate DP, and the method extends to finite higher-order sensitivity hierarchies. Second, our Propose-Test-Release (PTR) variant privately searches a finite public grid for a temperature scale rather than fixing it in advance. Third, smooth sensitivity supports several designs. A candidate-independent smooth geometric construction produces a sensitivity envelope that is admissible under the local dampening framework, which privacy is guaranteed for any admissible envelope. Additionally, a separate logarithmic transformation utilizes smooth sensitivity to produce a smoothed candidate score function with advantages: having controlled global sensitivity, and preserving the maximizers of the original utility score, i.e., candidates maximizing the utility. Both of the designs yield range-independent pure DP. Besides that, we also give two approximate DP private selectors using smooth sensitivity: a direct EM with smooth sensitivity calibrated to the candidate range and privacy parameters that matches a theoretical lower bound up to some constant factor, and one using a privatized smooth upper scale by analyzing the logarithmic transform of the smoothness. For every proposed mechanism, we derive a high-probability regret bound under its stated conditions.

We study deterministic relative approximation of the total variation distance between two Gibbs distributions induced by spin systems on the same bounded-degree graph. For the hard-core model, we give a deterministic polynomial-time $\varepsilon$-relative-error approximation when both external-field vectors lie in $[b,(1-\eta)\lambda_{\mathrm c}(\Delta)]^V$, where $b>0$ and $\eta\in(0,1)$ are fixed and $\lambda_{\mathrm c}(\Delta)$ is the hard-core uniqueness threshold. For the Ising model, we obtain deterministic polynomial-time algorithms in two settings: the ferromagnetic Lee–Yang regime and the antiferromagnetic correlation-decay regime. We develop a new deterministic framework that reduces this task to estimating suitably chosen partition functions.

Recovering latent geometric structure from graph observations is a well-studied problem in statistical inference. Kapralov, Trevisan, and Wrzos-Kaminska (2026) introduced the problem of recovering the coordinate structure of the Boolean hypercube from a small random sample of its edges. More specifically, there are $n=2^d$ vertices, each corresponding to a distinct "feature" vector in $\{\pm 1\}^d$. Between each pair whose feature vectors are at Hamming distance one, an edge is observed independently with probability $p$. As long as the expected degree $pd$ is $\gtrsim \log d = \log \log n$, we give a polynomial-time algorithm that, given only the graph of observed edges, correctly recovers the entire feature vector of all but a vanishing fraction of vertices. This matches the information-theoretic guarantee of Kapralov, Trevisan, and Wrzos-Kaminska in polynomial rather than exponential time, resolving the algorithmic question left open by their work. Our algorithm combines a degree-$4$ sum-of-squares certificate for the structure of balanced near-minimum cuts with a rounding scheme originally developed for tensor decomposition by Ma, Shi, and Steurer (2016). The analysis relies on two novel ingredients: a sum-of-squares version of the Friedgut-Kalai-Naor theorem in Boolean Fourier analysis and a spectral concentration result for the observed subgraph of the hypercube. Finally, we provide a justification for why higher-degree sum-of-squares might be needed by showing a limitation of the basic SDP relaxation of this problem.

We study the matroid secretary problem with a nonnegative monotone submodular objective. Elements arrive in uniformly random order, and every acceptance decision is immediate and irrevocable. We give an $8.699$-competitive algorithm for arbitrary matroids. The algorithm first rejects a randomly sized initial segment of the arrival sequence as a learning set and runs submodular greedy on all elements in this set. Each later element receives a fixed weight equal to the marginal value it would have when inserted into the stored greedy sequence. On these fixed weights, the algorithm runs a linear-objective matroid secretary subroutine. The algorithm uses $O(nr)$ value queries and $O(n^2)$ independence queries, where $r$ is the matroid rank.

We study the classical problem of scheduling jobs with random processing times on $m$ identical machines to minimize the expected sum of completion times, for Bernoulli jobs: job $j$ takes time $p_j$ with probability $q_j$ and time $0$ otherwise, and its outcome is revealed when it starts. The benchmark is an optimal adaptive policy. We give a quasi-polynomial-time approximation scheme for every number of machines. Previously, quasi-polynomial time was known to give an $O(\log N)$-approximation, and approximation schemes were known only for a constant number of distinct sizes. The scheme rests on a simple observation: it suffices to round the times at which machines become free, rather than the times at which jobs start, to a grid whose width is proportional to the job size, and an optimal policy stretched by a factor close to one already respects such grids. We also show that every policy that fixes the order of the jobs in advance loses a factor $\Omega(\log N)$, already on two machines, so a constant factor requires adapting the order to the observed outcomes. Further results include a polynomial-time adaptive rule with ratio $\min\{m,1+\sum_j q_j\}$, a simpler approximation scheme for a constant number of sizes, and #P-hardness of computing the optimal expected cost on two machines.

Dualizing monotone Boolean functions (or equivalently, enumerating minimal transversals in hypergraphs) is a long-standing problem whose output-polynomial-time solvability remains open. While various special cases have been extensively studied, the state-of-the-art algorithm for the general case, due to Fredman and Khachiyan, runs in quasipolynomial time. This paper presents a subexponential-time reduction from 3SAT to the complement of Dual: Given a 3CNF formula with $n$ variables, the reduction constructs hypergraphs $H$ and $L$ of total size $2^{O(n^{2/3}(\log n)^{1/3})}$ such that $L \subseteq Tr(H)$ and the formula is satisfiable if and only if $L\neq Tr(H)$, where $Tr(H)$ is the set of minimal transversals of $H$. As a consequence of this reduction, assuming the Exponential Time Hypothesis (ETH), neither Dual nor Dualization admits an algorithm running in $N^{o(\sqrt{\log N/\log\log N})}$ time, where $N$ is the input size for Dual and the combined input and output size for Dualization. In particular, Dualization cannot be solved in output-polynomial time under ETH.

Addario-Berry, Reed, Scott, and Wood (JoCG 2026) proved that the $n$-dimensional associahedron has chromatic number at most $22500\cdot\log_3 n+O(1)$. We present a much simpler proof that the chromatic number of the $n-1$-dimensional associahedron is at most $6 \log_2 n + 18$. Since this paper's appearance as a preliminary abstract in the Japan Conference on Discrete and Computational Geometry, Graphs, and Games held from September 7-10, 2026, the bound has been improved to $O(\log \log n)$ by Oum and Wood (arXiv September 30, 2026). It is hoped that the simple method here could give insights to further improvements.

A link stream is a set of interactions between pairs of vertices, each one lasting during some time interval, and a clique of a link stream is a set of vertices together with a time interval during which all of them interact. A clique is maximal if neither its vertex set nor its interval can be enlarged. All known algorithms listing the maximal cliques of a link stream may spend time exponential in the size of a clique for each clique they output. Here, we approach the question under the light of two parameters of the instantaneous graphs of the stream, their maximum degree $\Delta$ and their degeneracy $k$. We prove that a link stream with $m$ links has $O(m\Delta^2 3^{\Delta/3})$ maximal cliques, and that a link stream with $n$ vertices and $|\mathcal{T}|$ distinct end times has $O(n|\mathcal{T}|k^2 3^{k/3})$ maximal cliques. Both bounds are tight up to a factor polynomial in $\Delta$ and $k$ respectively, and the second one improves the factor $2^k$ of previous bounds to $3^{k/3}$. Then we present two algorithms. The first one has setup time $O(m\log m)$ and polynomial time delay $\mathrm{poly}(\Delta)\log m$. The second one has setup time $O(m\log m+mk^2\log^3 n)$ and polynomial time delay $\mathrm{poly}(k)\log m$. To the best of our knowledge, these are the first algorithms with polynomial time delay for this problem. We also give an online version of the second algorithm, and we show that our results apply to the $\Delta$-cliques and $(\Delta,\gamma)$-cliques of temporal graphs.

We study distribution testing with access to non-adaptive conditional samples. Specifically, we give tight bounds for equivalence testing, determining whether two unknown distributions are equal to or $\varepsilon$-far from each other in total variation distance. Our algorithm and lower bound show that $\tilde \Theta\left(\frac{\log n}{\varepsilon^2}\right)$ queries are necessary and sufficient for this problem. These results demonstrate that the complexity of uniformity, identity, and equivalence testing with non-adaptive conditional samples are all $\tilde \Theta(\log n)$.

The Travelling Salesman Problem (TSP) is a classic combinatorial optimisation problem which is NP-hard in optimisation form and NP-complete as a decision problem. The standard question asks for the shortest tour that visits every city exactly once and returns to the origin. This paper studies a threshold-fraction variant, which we call the robust TSP, formulated as a promise problem: given a distance threshold $K$ and a promised fraction $p$, decide whether at least a fraction $p$ of all tours have total length at most $K$, or whether no such tour exists. We show that Grover's quantum search algorithm decides this problem using $O(1/\sqrt{p})$ oracle queries, independent of the number of cities $N$, with each query implemented by a quantum circuit of polynomial size in $N$. For any fixed robustness level $p$, the total runtime is therefore polynomial in $N$. Measured in oracle queries, the quantum algorithm offers a quadratic improvement in the dependence on $1/p$ over classical random sampling, which needs $\Theta(1/p)$ samples; because each quantum query is costly, however, it is faster in total running time only when $p$ is very small (roughly below $N^{-4}$), where the number of queries is no longer constant. We describe the problem formulation, detail the oracle construction (edge-length loading, sequential quantum addition, and threshold comparison), and analyse the query complexity to achieve the required result.

We study online scheduling of parallel jobs on $m$ identical processors to minimize maximum flow time. Each arriving job is represented by a directed acyclic graph (DAG) whose vertices are unit-time subjobs and whose edges specify precedence constraints. We consider non-clairvoyant algorithms: the DAG is not known when a job arrives, and each subjob is revealed only when it becomes ready. Agrawal, Moseley, Newman, and Pruhs (SPAA 2024) showed that First-In-First-Out (FIFO) has competitive ratio $\Omega(\log m)$ even when every job is an out-tree. They also proved that FIFO is $O(\log m)$-competitive in several natural settings and asked whether this guarantee extends to general instances. More broadly, they asked whether any non-clairvoyant algorithm can be $O(1)$-competitive. We answer both questions in the negative by proving a lower bound of $\Omega(\min\{m,\mathrm{OPT}\})$ for every non-clairvoyant online algorithm, where $\mathrm{OPT}$ is the maximum flow time of an optimal offline schedule. In particular, every non-clairvoyant algorithm has competitive ratio $\Omega(m)$ on some instance with $\mathrm{OPT} \ge m$. The lower bound holds even when every job is an out-forest. We complement these lower bounds with an asymptotically optimal non-clairvoyant algorithm. FIFO is $O(m)$-competitive, but can have competitive ratio $\Omega(m)$ even when $\mathrm{OPT}=O(1)$. For instances with small $\mathrm{OPT}$, we design a Small-Frontier-First algorithm that is $O(\mathrm{OPT})$-competitive. Combining the two algorithms yields an $O(\min\{m,\mathrm{OPT}\})$-competitive non-clairvoyant algorithm.

String attractors provide a compact way of representing the complete factor structure of a word: a set of positions is an attractor if every distinct factor has at least one occurrence crossing one of the selected positions. Although the minimum attractor size is known for several classical families of words, describing all optimal attractors is typically much more difficult, since it requires understanding the geometry of all factor occurrences rather than constructing a single optimal solution. We give a complete description for the finite Thue–Morse words. Earlier work proved that four positions are necessary and sufficient for every order $n\geq 4$, but the collection of all smallest attractors remained unknown. For every $n\geq 6$, writing $h=2^{n-3}$, we prove that the smallest attractors are exactly the two reflected families where the four offsets are chosen independently from $\{0,1\}$. Hence there are exactly $32$ smallest attractors for every $n\geq6$. The initial cases are genuinely exceptional: $t_5$ has $40$ smallest attractors and $t_4$ has $87$. We also study the attractor condition independently of optimality. For every $n\geq5$, we characterize the complete antichain of inclusion-minimal factor coverages of $t_n$. It consists precisely of the coverages of $aa$, $bb$, and the eight minimal unique substrings of every generation $t_m$, $4\leq m\leq n$. Thus there are exactly $8n-22$ canonical constraints, forming an irredundant exact certificate for attractors of arbitrary cardinality. When attention is restricted to four-position sets, this linear-size system collapses to a constant one: it is enough to test the $24$ minimal unique substrings coming from three consecutive generations, and sixteen of these already force the two optimal families. We also show that three generations are necessary within this natural consecutive-generation hierarchy.

We prove an $\Omega((\log n/\log\log n)^2)$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in $n$-node directed acyclic graphs under edge insertions. This improves the $\widetilde{\Omega}(\log^{3/2} n)$ lower bound of Larsen and Yu [SICOMP 2025], and matches the strongest lower bound known for any dynamic problem. The same bound holds for incremental undirected shortest paths and subgraph connectivity. To prove it, we bring the recent framework of Ko [FOCS 2026], which gave this bound for Pătraşcu's multiphase problem with Inner Product, to the multiphase problem with Disjointness. Our main technical contribution is to show that verification in Ko's 2.5-round multiphase communication game makes a one-sided corruption bound suffice in place of discrepancy, which Disjointness lacks.

We give a randomized reduction from global minimum cut in a directed graph with $n$ vertices and $m$ weighted edges to maximum-flow computations on graphs of total size $\widetilde{O}(m)$. For polynomially bounded integral weights, this yields the first almost-linear $m^{1+o(1)}$-time algorithm [vdBCK+23], improving the previous $m^{1+o(1)}\min\{\sqrt{n},n/m^{1/3}\}$ bound [CLN+22]. Previous work reduced finding the minimum cut to constructing a 1-respecting arborescence, a directed spanning tree with exactly one edge crossing a minimum cut [CLN+22]. They then construct such a tree by sampling from a $(1+\epsilon)$-approximate arborescence packing, which currently requires superlinear time. Our algorithm sidesteps constructing the packing entirely and relies on a novel iterative arborescence sampling procedure. We show that, after $O(\log n)$ rounds of sampling, our final arborescence 1-respects the minimum cut with constant probability.

Chekuri, Gupta, Newman, Rabinovich, and Sinclair [SODA'03] showed that $k$-outerplanar graphs can be embedded into trees and $\ell_1$ with distortion $2^{O(k)}$. Their result is perhaps the strongest evidence supporting the still-open planar $\ell_1$-embedding conjecture: planar metrics can be embedded into $\ell_1$ with constant distortion. However, the exponential dependency on $k$ in their distortion bound remains the state of the art. Their embedding is obtained by a so-called onion-peeling approach: removing one layer of the graph at a time at the cost of incurring $O(1)$ distortion multiplicatively, and recursively embedding the resulting $(k-1)$-outerplanar graph. In this paper, we devise a new onion peeling approach that peels $k/2$ layers off the input $k$-outerplanar graph at every step. As a result, we obtain the first embedding of $k$-outerplanar graphs into trees and $\ell_1$ with distortion $\operatorname{poly}(k)$, an exponential improvement over the best-known distortion bound [SODA'03]. Our result of embeddings into trees comes closer to the distortion lower bound $\Omega(k)$ for $k$-outerplanar graphs.

Let $P$ be a set of $n$ points in the plane. Given an integer $K$ with $1\le K\le {n\choose 2}$, the distance selection problem asks for the $K$-th smallest distance among all pairwise distances of the points of $P$. The problem has been studied extensively over the past four decades. Recently, Chan and Zheng (2023) gave a randomized algorithm with $O(n^{4/3})$ expected running time, while the best known deterministic algorithm runs in $O(n^{4/3}\log n)$ time. In this paper, we present a deterministic $O(n^{4/3})$-time algorithm for the problem, matching the best known randomized complexity. We also consider the more general bichromatic version of the problem, where two point sets $A$ and $B$ are given, with $m=|A|$ and $n=|B|$, and the goal is to find the $K$-th smallest distance among the $mn$ distances between points of $A$ and points of $B$. For this problem, the best previously known algorithm runs in $O((m\log n+n\log m+m^{2/3}n^{2/3})\log(m+n))$ time. We present a new deterministic algorithm with running time $O(m\log^2 n+n\log^2 m+m^{2/3}n^{2/3})$.

Given value-oracle access to a symmetric submodular function $f:2^V\to\mathbb{R}$ with $|V|=n$, a nontrivial minimizer can be found using $O(n^3)$ value queries. We study the weaker comparison model, in which a query on $S,T\subseteq V$ reveals only whether $f(S)$ is smaller than, equal to, or larger than $f(T)$. We give a deterministic polynomial-time algorithm that finds a nontrivial minimizer of any symmetric submodular function using $O(n^3)$ comparisons, matching the best-known deterministic value-oracle bound despite not knowing the function values. More generally, the same $O(n^3)$-comparison bound holds for minimization over the nonempty members of any downward-closed family. Our algorithm combines the minimum-capacity ordering recently introduced by Iwata and Konno with the contraction framework of Goemans and Soto. Applying this result to weighted graph cut functions resolves the main open question of Cohen-Addad et al., who gave an $\widetilde{O}(n^3)$-comparison algorithm that runs in exponential time and asked whether a weighted minimum cut can be found in polynomial time using comparisons. For graphs with $m$ edges of integer weight at most $B$, we also give a deterministic polynomial-time algorithm that finds a minimum cut using \[ \widetilde{O}\!\left(n^2+\min\!\left\{mB,\,nB^2\right\}\right) \] comparisons, improving on the $O(n^3)$ bound when $B$ is small. Finally, we show that every randomized algorithm that outputs a minimum cut with probability at least $2/3$ makes $\Omega(n \log n)$ expected comparisons in the worst case. Under the stronger assumption that all edge weights are polynomially bounded integers, we obtain an $\Omega(n \log \log n)$ expected comparison lower bound. These bounds contrast with the value-oracle model, where no $\omega(n)$ lower bound is known even for deterministic algorithms.

The (min,+)-convolution of two sequences A and B of length n is the sequence C with C[k] = min_{i+j=k} (A[i]+B[j]). For bounded inputs, whose entries are integers in {0,...,O(n)}, prior work computes it in truly subquadratic time when the inputs are monotone; the algorithm of Chi, Duan, Xie, and Zhang (STOC 2022) takes expected O~(n^{1.5}) time. We introduce a monotonicity measure ranging from 0 (monotone) to 1/2 (entirely non-monotone): a sequence has monotonicity alpha if it can be partitioned into O(n^alpha) monotone subsequences, and by the Erdos-Szekeres theorem every sequence has monotonicity at most 1/2. We show that truly subquadratic time is achievable even when just one input is barely monotone, that is, has monotonicity 1/2 - Omega(1): if A has monotonicity alpha, we compute the convolution in expected time O~(n^{5/3+2alpha/3}) for every bounded B. If B has monotonicity beta as well, the expected time improves to O~(n^{(3+alpha+beta)/2}), which matches the monotone case for alpha = beta = 0; this algorithm also allows infinite entries placed arbitrarily. We complement these algorithms with fine-grained reductions. Bounded (min,+)-convolution reduces to bounded monotone (min,+)-convolution of length N = O(n^{1.5}), so an O(N^{4/3-eps})-time algorithm for monotone inputs would give an O(n^{2-3eps/2})-time algorithm for bounded inputs. Similarly, entries bounded by n reduce to entries bounded by N^x on sequences of length N = Theta(n^{2/(1+x)}). We also show that if only A has entries in {0,...,M}, we can compute the convolution in O~(n(M+1)) time, and in O~(n^{1.5} sqrt(M)) time if A may also contain +infinity.

Taxonomic classifiers based on exact matches differ in which matches they use and in how each match splits its credit among the taxa containing it: Kraken~2 gives a $k$-mer's credit to the lowest common ancestor of those taxa, SPUMONI~2 labels each position of the read, Tagger gives each maximal exact match (MEM) one label, and Cliffy splits a match's credit evenly over a roughly logarithmic sample of the taxa. We compare these schemes on the same long MEMs, mainly on short 16S rRNA reads classified to genera with SILVA, where credit proportional to the number of occurrences of the MEM in each taxon is the most accurate, by 1.0 to 6.8 percentage points. We compute long MEMs with Boyer–Moore–Li on a run-length compressed suffix array, and count their occurrences in each taxon with a complete, run-length compressed tag array, in time proportional to the number of tag runs in the MEM's BWT interval, without locating any occurrence. We bound the number of tag runs in terms of the BWT runs and of how often suffixes with long common prefixes have different tags, and show that tags constant on $d$ blocks of the text have a macro scheme with at most $r + 2d$ phrases. On SILVA our index takes 1.44\,GB and classifies a read in 66\,$\mu$s with one thread at 93.8% accuracy, about what Cliffy reports for its 9\,GB index; over minimizer digests it takes 0.49\,GB and reaches 92.5%, against 84.2% for Cliffy's digested index on the same reads. On nanopore reads from whole genomes, where almost every long MEM occurs in one species, we instead use each read's longest MEMs, found in one pass of a variant of Boyer–Moore–Li with a $k$-mer filter, which assigns 99.6% of the reads to their species with no length threshold.

In this note, we extend the matrix-multiplication analysis by OpenAI to rectangular products and prove $\omega(1,k,1)\le2$ for $0\le k\le\frac{1}{2}$, and $\omega(1,k,1)\le1+k+\frac{1}{4k}$ for $k\ge\frac{1}{2}$. In particular, $\omega(1, \frac{1}{2},1)=2$ and the dual exponent satisfies $\alpha\ge\frac{1}{2}$. The proof uses explicit degenerations of convolution tensors, multinomial counting, and Strassen's spectral theorem. An angular constraint on three dot-product parameters gives both the rectangular curve and a bound for $\omega(a,b,c)$. As an application, Zwick's algorithm for all-pairs shortest paths in directed unweighted graphs runs in $O(n^{2.5})$ time. Combining the rectangular bound with the $(\min,+)$-product improvement of Alman and Vassilevska Williams further gives $O(n^{2.4999})$ running time.

We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas. For every sufficiently large $k$ and density $0 < \alpha \le 2^k/k^{16}$, we prove that, with high probability over the formula, there is a sampler whose output distribution is within total variation distance $\varepsilon$ of the uniform distribution on satisfying assignments and whose expected running time is at most $(nk(\alpha+1)/\varepsilon)^C$, for a universal constant $C$. Our algorithm improves the counting and sampling algorithms obtained by Chen, Lonkar, Wang, Yang, and Yin (STOC 2025) at the density $2^k/\operatorname{poly}(k)$ with running time $(n/\varepsilon)^{\operatorname{poly}(k,\alpha)}$. Our result achieves this density region for sampling with a polynomial degree independent of both the width and the density. Our algorithm separates a high-degree core from the remaining variables, and combines a recursive sampler for the residual formulas with approximate block heat-bath updates on the core. We adapt the recursive insertion-chain framework of Jain, Mizgerd, and Pham (2026) from $2$-trees to ordinary connected violation sets. Expansion and random literal signs yield uniform moment bounds for the resulting correlated lists across all residual formulas, allowing the signed-flow analysis to give a universal polynomial running-time degree. A polymer expansion and an exploration bound establish a polynomial spectral gap for the core dynamics.

We show that the subset sum problem can be solved in time $O(2^{0.499999n})$, breaking the $2^{n/2}$ meet-in-the-middle barrier. Our approach builds on the representation technique framework of Randolph and Węgrzycki (STOC 2026). We choose a representation for which testing the compatibility of pairs of partial solution vectors is exactly the partial match problem. To beat exponent $1/2$ for subset sum, it then suffices to give a nontrivial partial match algorithm in a certain parameter regime. We achieve this by designing a depth-2 linear circuit for the partial match matrix, which yields an efficient algorithm via the framework of Alman and Li (FOCS 2025).

We give a polynomial-time algorithm for approximating the partition function of mean-field mixed $p$-spin models to arbitrarily high accuracy throughout the second-moment regime. This improves the quasipolynomial-time algorithm of Bencs, Huang, Lee, Liu, and Regts (arXiv:2507.15616) and answers their open question. In particular, our result covers the entire replica-symmetric regime of the Sherrington–Kirkpatrick model. The algorithm is deterministic, runs in time polynomial in $n$ and $1/\varepsilon$, and succeeds for every typical realization of the disorder. Our main technical contribution is a new algorithmic application of color coding to the classical high-temperature expansion introduced by Aizenman, Lebowitz, and Ruelle in their study of fluctuations of the Sherrington–Kirkpatrick partition function. We combine this approach with the zero-freeness established by Bencs et al. (arXiv:2507.15616) to convert additive approximations into multiplicative ones.