Papers

We study collision-free movement problems on graphs, where the task is to coordinate a set of robots so that they reach a target formation satisfying a desired property while minimizing the total travel distance. This framework extends two classical models: (a) minimizing movement [Demaine et al., TALG '09, '14], which does not enforce collision avoidance, and (b) coordinated motion planning or multi-agent path finding [Eiben et al., SoCG '23, Deligkas et al., ICALP '24, among many others], where each robot is assigned an explicit target position. We focus on the setting where the target formation of the robots should be connected. We analyze the parameterized complexity of the problem with respect to the number of (main) robots and the total travel length on grid graphs and two natural generalizations thereof: planar graphs and unit disk graphs.

We study fundamental information-theoretic limits of robust stochastic optimization when the distribution is known only through its exact moment sequence. We develop a unified framework that produces families of distinct distributions sharing all moments yet inducing radically different optimal decisions, thereby establishing strong impossibility results for a range of decision problems under moment ambiguity. Our approach gives two explicit constructions: a binary and an $N$-way construction showing that distributions with identical moment sequences can nevertheless exhibit arbitrarily different quantiles, order-statistics and threshold regions, forcing incompatible optimal actions. These families of distributions yield, in fact, strong impossibility results across several stochastic optimization problems. First, for the newsvendor problem, moment equivalence causes quantile ambiguity, inducing any fixed or randomized order quantity to fail arbitrarily badly. Second, for revenue maximization, no deterministic or randomized posted pricing scheme can secure a nontrivial approximation relative to the full-information benchmark. Third, for the secretary with cardinal observations setting, the worst-case robust value over all exact moment disclosures is exactly the classical $1/e$ finite-horizon value as opposed to the celebrated result of $0.58$ success probability with full-information by Gilbert and Mosteller (J. Am. Stat. Assoc., 1966). We also recover and expand upon the recent impossibility result of Correa et al. (STOC, 2026) for prophet inequalities with moment knowledge. Indeed, exact moment knowledge can yield at best a $\Theta(1/\log n)$ competitive ratio, even when competing against relaxed benchmarks based on expected $r$-th order statistics or when the algorithm is allowed to select $r$ items.

We give a deterministic $O(m)$-time algorithm for exact modular subset sum over every modulus $m$. The input gives distinct residues and their multiplicities. The algorithm reports all reachable residues and answers one target query. It returns a witness when the target is reachable. The algorithm uses $O(m)$ auxiliary words on an arithmetic word-RAM. This improves Potępa's deterministic $O(m\log m\,\alpha(m))$-time bound under the same input convention. The running time matches the cost of explicitly reporting all $m$ reachability bits. We represent reachable residues as runs along cycles of repeated addition. Newly reached residues pay for scans of partial runs. We process prime factors in increasing order so that cycle rebuilding takes linear time. A theorem on subset sums of distinct units limits the number of adaptive boundary batches to $O(m^{3/4})$. Radix sorting their $O(m)$ total keys also takes $O(m)$ time.

Odd Cycle Transversal is a classic $\mathsf{NP}$-hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite, or equivalently, a maximum-weight induced bipartite subgraph. We show that Odd Cycle Transversal is quasi-polynomial-time solvable on $kP_4$-free graphs, for every fixed $k \in \mathbb{N}$. In fact, we provide an $n^{O_k(\log n)}$-time algorithm for the more general \textsc{Max-Weight List $2$-Colorable Induced Subgraph}, where the notation $O_{k}(\cdot)$ hides factors depending on $k$. Paired with known results from the literature, this allows us to obtain a complete complexity dichotomy for these two problems on $H$-free graphs into cases solvable in quasi-polynomial time and cases which are $\mathsf{NP}$-hard, in particular resolving an open problem of Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024]. Our algorithms are based on a new structural tool that may be of independent interest. We introduce the notion of $H$-amiable family and show that, for every fixed graph $H$ without isolated vertices and every fixed $k\ge2$, every $kH$-free graph admits an $H$-amiable family of quasi-polynomial size that can be constructed in quasi-polynomial time. Besides yielding the aforementioned algorithms, this result gives, for every fixed connected graph $H$ and every fixed $k\ge2$, a reduction from Max-Weight Independent Set on $kH$-free graphs to the same problem on $H$-free graphs with $n^{O_{H,k}(\log n)}$ overhead. In this setting, it improves the $n^{O_{H,k}(\log^3 n)}$ overhead obtained by specializing the general reduction of Gartland and Lokshtanov [FOCS 2020].

Lee and Sidford [LS19] showed that the linear program $\min\{c^\top x\ :\ A^\top x=b,\ l\leq x\leq u\}$ over $x\in\mathbb{R}^m$, where $A\in\mathbb{R}^{m\times n}$, can be solved to accuracy $\epsilon$ using $O(\sqrt n\log^{13}m\cdot\log(mU/\epsilon))$ solves of linear systems in $A^\top\mathbf DA$ for positive diagonal matrices $\mathbf D$, where $U$ bounds the magnitudes of the input and of the initial point. Theirs is the first such bound governed by $\mathrm{rank}(A)=n$ rather than by the number of constraints $m$. Song [Son19] mentioned that reducing the $\log^{13}m$ factor is an interesting future direction. Given an interior point and a finite certified magnitude bound $U$, we give an algorithm that uses $O(\sqrt n\log^{4}m\cdot\log(mU/\epsilon))$ solves of such linear systems, improving the Lee–Sidford bound by a factor of $\log^{9}m$. We conjecture that $O(\sqrt n\log(mU/\epsilon))$ such linear-system solves suffice.

Packing and covering problems for geometric regions have been studied under many notions of complexity, including VC-dimension, union complexity, shallow-cell complexity, and fatness. Although these restrictions often yield constant-factor approximation algorithms, they do not by themselves generally lead to PTASs. A recurring feature of known hardness constructions is that one region may be pierced by many others: a region $B$ pierces $A$ when $A\setminus B$ is disconnected. We study geometric instances through the piercing degree. Since piercing is symmetric for Jordan regions, this is the maximum degree of the corresponding piercing graph. Our main result is that, for every fixed piercing degree, the standard local-search algorithms give PTASs for the unweighted Discrete Independent Set and Set Cover problems. The proof constructs a sublinear balanced separator for an appropriate locality graph and applies it adaptively throughout the recursive local-search analysis. This guarantee depends only on the piercing degree; in particular, it places no bound on the number of components created by an individual piercing pair. We also prove a polynomial shallow-trace bound depending only on the piercing degree. As consequences, for every fixed piercing degree, weighted Set Cover admits a deterministic $C_r$-approximation and weighted Discrete Independent Set admits a deterministic $O(r+1)$-approximation. These results extend the known guarantees for non-piercing families and apply, for example, to axis-parallel rectangles when every rectangle is pierced by only a bounded number of other rectangles.

We give explicit algorithms that factor elements of the standard diagram monoids into their usual generators. These algorithms generalize sorting from permutations to partial matchings and set partitions. In every case the worst-case complexity is $n^2$, which is optimal for algorithms that explicitly list the factors. We also determine the average complexity of our algorithms.

Let $\lambda$ denote the ratio of the length of a longest common subsequence of two length-$n$ strings to $n$. Rubinstein, Seddighin, Song and Sun [RSSS19] gave an $\Omega(\lambda^3)$-approximation for LCS running in $\widetilde O(n^{39/20})$ time, where $39/20=1.95$. Song [Son19] mentioned that improving the $n^{1.95}$ running time is an interesting open question. We give an algorithm that computes an $\Omega(\lambda^3)$-approximation of the longest common subsequence in $n^{8/5+o(1)}$ time. This improves the exponent $1.95$ to $1.6+o(1)$.

We initiate the study of prophet trading, an online trading model in which a trader interacts with sellers and buyers who arrive in a uniformly random order and whose prices are drawn independently from a common known distribution. The trader aims to maximize the expected gain from trade (GFT), with performance measured against an omniscient prophet that knows the realized arrival order and all prices in advance. Unlike the classical prophet inequality problem, the trader must make both purchasing and selling decisions while managing the inventory, which makes both the prophet benchmark and the analysis of online algorithms substantially more intricate. For arbitrary numbers of buyers and sellers, we propose a simple threshold-based algorithm and prove a distribution-free competitive ratio of~2, which is the best possible. Our main technical contribution is an exact characterization of the inventory process induced by threshold trading. By expressing the algorithm's expected GFT in terms of the cumulative holding probability at buyer arrivals, we derive an exact formula for this inventory term, which serves as the foundation of our analysis and yields sharper guarantees in several important special cases. For balanced trading (with $n$ sellers and $n$ buyers), we improve the competitive ratio to $(2n^2-n)/((n+4^{-n}-1)(n+1))$, which is strictly less than 2 for every $n>1$. For the single-seller case, we sharpen the analysis of the fixed-threshold algorithm to obtain an asymptotic competitive ratio of $2e^2/(e^2+1)\approx1.76$. Furthermore, by exploiting the additional structure of this setting, we design an adaptive-threshold algorithm whose competitive ratio approaches $e/(e-1)\approx 1.58$. Due to a symmetry property of our general algorithmic idea, the same $1.76$-competitive guarantee also holds for the single-buyer case.

We establish matching polynomial query bounds for low-rank approximation from exact matrix–vector products. Given an unknown matrix $A\in\mathbb{R}^{m\times n}$, at each step a randomized algorithm chooses either $v\in\mathbb{R}^n$ and receives $Av$, or $u\in\mathbb{R}^m$ and receives $A^\top u$. The choice may depend measurably on all previous queries and replies and on the algorithm's private randomness; each vector product costs one query. The output is a rank-$k$ right projector with Schatten-$p$ residual at most $1+\varepsilon$ times optimal. Write $N=\min\{m,n\}$ and let $Q_p^*$ denote the worst-case query budget for success probability $2/3$ on every input. For every $1\le k<N$ and sufficiently small $\varepsilon$, our lower bounds, combined with existing Krylov upper bounds, give $Q_p^*=\widetilde{\Theta}\!\left(\min\{N,k\min\{p^{1/6}\varepsilon^{-1/3},\varepsilon^{-1/2}\}\}\right)$ $(2\le p<\infty)$, $Q_\infty^*=\widetilde{\Theta}\!\left(\min\{N,k\varepsilon^{-1/2}\}\right)$. These bounds have universal constants and allow $p$ to vary with the problem parameters, identifying the transition at $p\varepsilon\asymp1$. A complementary result for each fixed $1\le p<2$ gives $\widetilde{\Theta}_p(\min\{N,k\varepsilon^{-1/3}\})$, with constants and an accuracy threshold that may depend on $p$. Together, the results recover this fixed-norm rate for every fixed finite $p$, supplying the multiplicative rank dependence missing from previous lower bounds. Tildes suppress logarithmic factors. The proof extends adaptive Wishart deferred decisions to a rectangular factor with a $k$-dimensional nullspace. Posterior overlap gives a short fixed-norm argument, while persistence of small compression eigenvalues controls growing $p$ and the spectral endpoint. Exact range recovery handles target costs of order $k$; the Wishart family covers the remaining regimes.

We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington-Kirkpatrick (SK) model with $o_n(1)$ error in total-variation distance (TVD) at any inverse-temperature $\beta < 1$. The algorithm combines algorithmic stochastic localization (ASL) with rejection sampling over path-space via Jarzynski's equality (JE). The analysis extends the authors' prior $\beta < 1/2$ result [arXiv:2605.03718] by replacing all global regularity requirements in the stochastic differential equation (SDE) error analysis with local regularity around likely trajectories. The relaxed regularity is established using Celentano's proof of the local strong convexity of the TAP free energy [arXiv:2208.09550]. The analysis utilizes the cavity interpolation theory and free probability toolkit developed in the authors' previous result, where the former applies nearly verbatim and the latter applies supplemented with Lipschitz and $C^2$ extensions of various functions. The ASL and JE analysis arises from using the TAP free energy as an efficiently computable proxy for the actual free energy of the stochastically localized Gibbs measure [$ \S $ 3, arXiv:2605.03718]. We give a list of \vocab{desiderata} encapsulating the approximation and regularity properties required of the TAP free energy, relaxing those of [$ \S $ 2.5, arXiv:2605.03718] to only require local regularity. These generic desiderata are potentially applicable in other settings where a free energy surrogate exists, giving algorithmic sampling guarantees while bypassing the usual functional inequalities based approach.

This paper settles the Matroid Secretary Problem with an $e$-probability-competitive algorithm. The algorithm is ordinal and accesses arrived elements only through comparison and independence oracles, and has expected polynomial time and oracle complexity.

We give a polynomial-time algorithm that constructs, in every connected $n$-vertex graph of minimum degree at least $7$, a spanning tree with at least $\frac{25200}{46189}n>0.5455\,n$ leaves. No bound specific to minimum degree $7$ was known: the best bound available for this class was $\frac{11}{21}n\approx0.5238\,n$, inherited from Simarova's theorem for minimum degree~$6$. The algorithm and its analysis are carried out for an arbitrary minimum degree $\delta$, and yield a recursion that gives an explicit lower bound on the number of leaves for every $\delta$. The resulting bounds improve all previously known ones for every $\delta\ge7$; for $\delta=8,9,10$ they are $0.5850\,n$, $0.6151\,n$ and $0.6413\,n$, and they are tabulated for $\delta\le25$ at the end of the paper.

We prove nearly quadratic lower bounds for randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership oracle model. For linear optimization, this matches the known nearly quadratic upper bound up to a polylog factor in the dimension. For uniform sampling, this improves on the previous linear lower bound. Our construction also implies the same lower bound for volume estimation.

The Lempel-Ziv (LZ77) factorization decomposes a text into the least possible number $z$ of phrases that each refer to an earlier occurrence. It is this phrase count, rather than the encoded size, that governs the size of LZ-based compressed indexes, and computing a factorization with few phrases is a time and space bottleneck in their construction. In practice, computing LZ77 quickly has so far required building a suffix array. Ellert [SPIRE 2023] gave algorithms that compute the exact LZ77 factorization, and a 3-approximation of it, in sublinear working space. They have remained unimplemented, because two of their components resist a direct implementation: a lookup table that degenerates to patterns of length at most two for realistic inputs, and an orthogonal range reporting data structure that is impractical. We replace both, fine-tune every remaining stage, and obtain the first practical implementation, which runs in space close to the text rather than to the suffix array. On one thread, our 3-approximation factorizes 12-19x faster than the classical LPF algorithm while using 14x less memory; on 32 threads, even our exact algorithm is 1.4–2.9x faster than parallel LPF, at 9x less memory. In practice the approximation ratio stays far below 3. As a side result, passing only its perfect phrases to a downstream compressor yields a precompressor that is on par with the state of the art [Dinklage, SEA 2026] in compression ratio, and better in memory consumption and parallel throughput.

We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) \] copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron–Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.

Approximate pattern matching (APM) on highly repetitive texts is a central task in bioinformatics. Bi-directional r-indexes support left- and right-extension of a pattern and thereby accelerate APM algorithms based on search schemes, but existing variants – br-index and b-move – suffer from two bottlenecks: $O(\sigma)$ character-predecessor/-successor queries on the run-length-encoded BWT per extension, and predecessor queries on sparse bit vectors to maintain a value in the suffix array interval and to access the PLCP array while locating. We present Move-rb, a bi-directional r-index built on the optimized r-index Move-r. Although Move-rb is 2x larger than br-index, it is up to 24% smaller than b-move, answers APM queries 1-4 orders of magnitude faster than br-index, 1.9-10x faster than b-move and up to 5.5x faster than the state-of-the-art bi-directional (uncompressed) FM-index columba, which is 36-42x larger. Memory usage (including index size) during APM locate queries is reduced by 1.5x (up to 6.5x) for Hamming distance and 2.5x (up to 7.4x) for edit distance. Move-rb can be constructed 3-14x faster while using 19-141x less memory than br-index, b-move and columba. A variant using a relative Lempel-Ziv-encoded suffix array locates up to 10x faster while being 1.2-2.4x larger. We achieve these speedups by optimizing index operations and search scheme APM algorithms: Without a direction switch, Move-rb computes an all-$k$-character extension in output-optimal $O(k)$ time and a single-character extension in the same time. Augmenting Move-rb with $O((r+\overleftarrow{r})\log(n/r_{\min})\log\sigma)$ bits reduces a single-character extension to $O(\log\sigma)$ time, where $r$ and $\overleftarrow{r}$ are the numbers of runs in the BWT of the text and its reverse, and $r_{\min}=\min(r,\overleftarrow{r})$. A direction switch incurs only $O(\log\log_\omega(n/r_{\min}))$ additional time.

In this paper, we consider the problem of refuting $\mathbb{F}_2$-linear equations with random right-hand sides. Formally, we give a sub-exponential $2^{O(n/\log n)}$-time randomized algorithm that takes as input an arbitrary $m \times n$ matrix $A$ and a uniformly random vector $b \in \mathbb{F}_2^m$, and outputs a witness showing that no assignment satisfies more than a $\frac{1}{2}+\epsilon$ fraction of the equations provided that $m \geq 2^{O(n/\log n)}$. The setting above is the semirandom refutation variant of the famous work [BKW03] that gives a $2^{O(n/\log n)}$-time search algorithm for the learning parity with noise (LPN) problem with $m \geq 2^{O(n/\log n)}$ equations. Building on the search algorithm of [Lyub05], we also give a $2^{O(n/\log \log n)}$-time refutation algorithm that succeeds with only $m \geq n^{1 + \gamma}$ equations, for a small constant $\gamma$. Finally, we prove that our algorithm is not captured by the sum-of-squares hierarchy by proving a degree-$\Omega(n)$ sum-of-squares lower bound, showing that ”[BKW03]-style” algorithms achieve better runtime than can be done under sum-of-squares. We thus obtain a natural example of a noise-tolerant signal recovery problem that exhibits a nontrivial gap between the performance of efficient algorithms and that of those based on the sum-of-squares hierarchy.

The Komlós conjecture, now a theorem, asserts that whenever the columns of a matrix $A\in\mathbb{R}^{m\times n}$ have Euclidean norm at most one, some signs $\varepsilon\in\{-1,1\}^n$ make every coordinate of $A\varepsilon$ bounded by an absolute constant. Guo, Fang, and Lu gave the first polynomial-time algorithm for finding such signs, a deterministic spectral signing procedure with discrepancy $8272$ and running time $O((mn^9+n^{10})\log(m+n))$. We give a deterministic algorithm that finds signs with $\|A\varepsilon\|_\infty<99$ using $O(mn+n^{\omega+2}\log^3 n)$ arithmetic operations, where $\omega>2$ is any fixed attainable matrix-multiplication exponent; with the current bounds on $\omega$ this is $\widetilde O(mn+n^{4.372})$. Our algorithm uses the same framework: it rounds a single fractional coloring and watches all rows through the top eigenvalue of a Gram matrix of energy-corrected barriers. Steps follow flat directions, rescaled so that no barrier near its threshold moves faster than a constant, and the regularizer grows as coordinates freeze; together these bound the number of updates by $O(n^2\log n)$. A weak quadratic charge on the tracked row sums leaves $O(n\log^2 n)$ rows to evaluate at any time, and a motion clock bounds when any other row could approach its barrier. Each update is a short sequence of matrix products. Its direction is read off by conditional expectations from a polynomial soft projector, its small constraint residual is repaired in affine row representations, and one identity accounts for every change of representation. For rational input the algorithm has polynomial bit complexity.

Zero Forcing (ZF) and Power Dominating Set (PDS) mark vertices in a graph based on a common forcing process starting from a problem-specific set of initially marked vertices. ZF initially marks the selected vertices while PDS additionally marks their neighbors. In the forcing process, a marked vertex with only one unmarked neighbor may force that neighbor which then becomes marked, too. A solution marks the entire graph by exhaustive application of this rule. One variant generalizes the forcing threshold; vertices may force when they have a fixed number of $k$ unmarked neighbors. Another variant limits propagation to a fixed number of rounds. We classify the parameterized complexity of the problem variants obtained by combining these choices of initialization, round limit and forcing threshold. We show that with appropriate choices, these variants range in parameterized complexity from fixed-parameter tractable to complete for every even layer $W[2\ell]$ of the $W$-hierarchy, and up to $W[P]$-complete. Our results demonstrate that small changes in any one of these three dimensions can lead to a sharp change in problem complexity.

Choosing Shellsort gaps is a well-known open problem. For over sixty years, successful sequences have relied on human-designed formulas, numerical searches, or number-theoretic constructions. Although stronger general bounds exist for dense or mainly theoretical families, the worst-case upper bound for a short, sparse, and practically competitive construction has not advanced beyond $N^{4/3}$ for decades. We ask whether the sequence itself can instead be learned from execution. We present an RL-driven, self-supervised system that searches over executable gap generators. Every proposal is valid by construction, and executed candidates return exact comparison and move counts; no classical sequence is used as a target. Across five independent searches, the system discovers a common rational-geometric family. A second self-supervised stage tunes only a finite prefix, producing the practical sequence $1,3,8,20,47,116,300,585,1416,3303,\ldots$. Once frozen, it obtains the lowest equal-task average operation count among seven classical baselines on 25 large tasks with $10^7<N\leq 10^8$. We complete the learned tail without changing its practical behavior: only beyond $10^{1000}$, a zero-density set of unit companions $h_s+1$ removes the remaining congruence barriers. The resulting sparse sequence has matching polynomial upper and lower exponents, up to polylogarithmic factors: $\Omega(N^{1.024296451657\ldots}) \leq T(N) \leq O(N^{1.024296451657\ldots}\operatorname{polylog} N)$. The lower bound follows from Zang's recent theorem for rational-geometric sequences; our contribution is the matching upper bound. Thus one exact sequence connects self-supervised discovery, large-scale practical performance, and a substantial step below the classical $N^{4/3}$ bound for sparse practical Shellsort sequences.

We study a variation of the classical Maximum (Minimum) Leaf Spanning Tree problem. In many applications, Depth-First Search (DFS) is used to compute a spanning tree of a graph. Such a search tree is constructed by connecting each vertex $v$ with the last vertex the search has visited before $v$ and we call this a last-in tree. By restricting the Maximum (Minimum) Leaf Spanning Tree problem to last-in trees of a graph search, we ask for a search ordering that leads to the largest (smallest) number of leaves in its search tree. Recently, Bergougnoux et al. [Journal of Computer and System Sciences 154 (2025)] have studied the parameterized complexity of these problems for DFS. They showed that the minimization problem is para-$\mathsf{NP}$-hard and the maximization problem is $\mathsf{W}[1]$-hard when parameterized by the number of leaves. When parameterized by the number of internal vertices, both problems have polynomial kernels. Here, we examine whether these results also hold for the variant Lexicographic DFS (LDFS). We show that the hardness results of DFS can be transferred to LDFS. We also present exponential kernels for the number of internal vertices as the parameter. We complement this by showing that polynomial kernels do not exist, unless $\mathsf{NP} \subseteq \mathsf{coNP} / \mathsf{poly}$. We also consider last-in trees of searches that do not follow the DFS scheme. In contrast to (L)DFS, minimizing the number of internal vertices is para-$\mathsf{NP}$-hard for several searches including Breadth-First Search.

We study the \textsc{$k$-Disjoint Paths} problem on a graph embedded on a surface with bounded Euler genus. Given a graph $G$ with $n$ vertices and $k$ vertex pairs embedded on a surface of Euler genus $g$, we present a $2^{O(k^2+g^2)}n$-time algorithm that computes $k$ pairwise vertex-disjoint paths connecting the given vertex pairs if such paths exist. Our approach relies on the decomposition of $G$ into $O(k+g)$ planar subgraphs while bounding the complexity of the boundaries between these subgraphs. This approach enables the use of techniques for compressing linkages in planar graphs. Moreover, our techniques yield two kernels of size polynomial in $k$, $g$, and the treewidth of the graph, and of size $2^{O(k+g)}$. These results extend recent advances on \textsc{$k$-Disjoint Paths} on planar graphs [Cho et al. SODA 2023] and [Włodarczyk and Zehavi FOCS 2023] to surface-embedded graphs.

The $k$ vertex-disjoint paths problem asks whether, given a graph $G$ and $k$ pairs of vertices $(s_1,t_1)$, \ldots, $(s_k,t_k)$, $G$ has $k$ pairwise vertex-disjoint paths connecting $s_i$ and $t_i$ for all $1\leq i\leq k$. If $G$ is undirected, then this problem is NP-complete, but there exist FPT algorithms parameterized by $k$.Since these algorithms involve an extremely large function on $k$, algorithms for restricted graphs have also been investigated. In particular, a $2^{2tw\log tw+O(tw)}\cdot n$ time algorithm for undirected graphs with $n$ vertices and treewidth $tw$ is proposed by Scheffler (Technical Report 396, TU Berlin, '94), and it is proved by Lokshtanov, Marx, and Saurabh (SIAM J. Comput. '18) that, under the ETH, there exists no $2^{o(pw\log pw)}\cdot n^{O(1)}$ time algorithm for either directed or undirected graphs with pathwidth $pw$ and for $k=\Omega(pw^4)$. It has not been known whether the lower bound also holds for a smaller $k$. In this paper, we prove that, for both the directed and undirected cases, there is an algorithm faster than Lokshtanov et al.'s lower bound for $k=tw^{o(1)}$ by proposing a $2^{O((tw+k)\log k)}\cdot n$ time algorithm. Besides, we prove a lower bound that, under the SETH, there exists no $(2-\epsilon)^{pw\log pw}\cdot n^{O(1)}$ time algorithm for directed graphs and for a general $k$. This lower bound is tight because, with slight modifications, Scheffler's algorithm runs in $2^{pw\log pw+O(pw)}\cdot n$ time also for directed graphs.

In this paper, the parameterized complexity of the multiplicative $\alpha$-spanner problem with independent weights and lengths on undirected graphs is considered for the first time. All prior FPT results (except one on DAGs) assume basic instances (i.e., with unit weights and lengths) and are parameterized in the stretch factor $\alpha$ and the (in practice typically non-constant) number of removed edges. We show that several parameterizations do not allow FPT algorithms. However, our exclusion approach generalizes an existing algorithm for basic instances to arbitrary weights and lengths. It is parameterized by the total removed weight and a new tightness parameter. The latter is more precise than $\alpha$ and allows us to also improve the best known result for basic instances. Our second algorithm, called inclusion approach, uses the natural parameterization in the spanner's total weight. We prove that this sole parameter leaves a W[2]-hard problem, but also show FPT algorithms exist when augmented with secondary parameters.

We give a deterministic polynomial kernel for Odd Cycle Transversal, derandomizing the randomized kernel of Kratsch and Wahlström (TALG 2014). Our algorithm uses a deterministic polynomial-time construction of almost multilinear representations of gammoids. Such a representation assigns a block of columns to each element so that, for every subset of elements, the normalized matrix rank approximates its matroid rank to within a prescribed additive error $\delta$. The construction builds on recent breakthroughs in NC algorithms for matching. Our kernelization algorithm then computes the required representative families from these representations.

We initiate the study of approximating the top eigenvalue and eigenvector of a random symmetric matrix $ A \in \mathbb{R}^{n\times n} $ using $ q(A)b $ where $q$ is a degree-$d$ polynomial and $b$ is a standard Gaussian vector independent of $A$. For spiked GOE $ Y = \lambda vv^\top + X $, we identify $ d_\star = \frac{\log(n)}{2\log(\lambda)} $ to be the critical degree threshold above which accurate approximation of the top eigenvalue and eigenvector is possible. This sharpens the common belief that spectral methods can be implemented by $ O(\log(n)) $-step power iterations and offers a precise connection between spectral methods and low-degree polynomial algorithms, a popular proxy for all polynomial-time algorithms. For GOE $X$, we identify $ d_\star = n^{1/3+o(1)} $ to be the critical degree threshold for top eigenvector approximation, whereas constant degree suffices for top eigenvalue approximation. Moreover, in the limit where $ d/n^{1/3} $ converges to a positive finite constant, we compute the exact asymptotic eigenvector approximation accuracy in terms of the expected squared overlap. These results significantly improve upon predictions made in randomized numerical linear algebra for deterministic data matrices that the iteration count of power methods with random initialization is governed by the inverse spectral gap. Technically, our analyses leverage extremal properties of Chebyshev polynomials and draw upon the rich literature of random matrix theory.

We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions $v,w:E\to R_{\ge 0}$, and a threshold $L\in R_{\ge 0}$, find $opt v(S)$ where S is either an independent set or a base of M satisfying a budget-type constraint: $w(S)\le L$ or $w(S)\ge L$, and $opt\in\{min,max\}$. P-MOL provides a unified representation for a broad family of NP-hard optimization problems, including budgeted matroid independent set, constrained minimum-basis, and knapsack-cover variants with a matroid constraint. Also, it naturally extends to multiple matroid constraints. In particular, we consider the matroid intersection cover (MIC) problem, where feasibility is defined by the common independent sets of two matroids and one seeks minimum $v(S)$ subject to $w(S)\ge L$. Our main result is a unified EPTAS for all nontrivial P-MOL variants, obtained by generalizing a technique of Hassin and Levin (SIAM J. Comput., 2004) for solving the constrained minimum spanning tree problem. Specifically, for any fixed $\epsilon>0$, we present an algorithm running in time $|E|^{O(1)} (1/{\epsilon^2})^{O(1/{\epsilon})}$ that outputs a feasible solution S whose value is at most $(1+\epsilon)OPT$ for minimization variants and at least $(1-\epsilon)OPT$ for maximization variants. This resolves the complexity status of all members of P-MOL, as none of these problems admits an FPTAS (Doron-Arad, Kulik and Shachnai, ICALP'24). Finally, we separate the P-MOL family from its extension to matroid intersection. We show that an EPTAS is unlikely to exist for the matroid intersection variant of P-MOL under a covering constraint, whereas an EPTAS is known to exist under a budget constraint. This highlights a qualitative difference between these two types of linear constraints that does not arise in the single-matroid setting.

The Girard–Hutchinson estimator provides an extremely simple randomized estimate of the Frobenius norm of a matrix $A$ that can only be accessed implicitly via matrix-vector products. In particular, if $\Omega$ is a random Gaussian matrix with $r = O(1/\varepsilon^2)$ columns, than $\frac{1}{r}\|A\Omega\|_F^2$ provides a $(1\pm \varepsilon)$ multiplicative approximation to $\|A\|_F^2$ with high probability. In this work, we introduce a closely related estimator, given by \begin{align*} {\frac{1}{r}\|A\Omega\|_F^2 + \frac{1}{r}\|\Psi^T A\|_F^2 - \frac{1}{r^2}\|\Psi^T A\Omega\|_F^2}, \end{align*} where $\Psi$ is a second, independent random Gaussian matrix with $r$ columns. We prove that this estimator yields a $(1\pm\varepsilon)$ multiplicative approximation to $\|A\|_F^2$ when $r = O(1/\varepsilon)$, a quadratic improvement over Girard–Hutchinson. This dependence on $\varepsilon$ is optimal. Our method, which we call Hutch# (pronounced “Hutch sharp”), matches the complexity of the Hutch++ algorithm [Meyer, Musco, Musco, Woodruff, 2021]. However, unlike Hutch++, Hutch# uses only non-adaptive matrix-vector products with $A$ and $A^T$ and requires no orthogonalization or other advanced linear algebra steps. Thus, Hutch# combines the simplicity of the Girard–Hutchinson estimator and the optimal query complexity of Hutch++.

In the classical list update problem, a set of items must be stored in a list-type structure, where accessing the $i$-th element costs $i$. Items will be queried in an IID manner according to some probability distribution $p$ on the items. We want to minimize the expected cost of each query. The optimal order is to place the items in decreasing order of probability $p_1 \geq p_2 \geq \cdots$ with expected cost $\mathsf{OPT} = \sum_j j p_j$, but the probability vector $p$ is generally unknown. Thus we use a self-organizing list following the transposition rule: an item is transposed 1 position forward whenever it is queried. Coester (2026) proved that, at stationarity measure for the transposition rule, the expected cost of a query is at most $\mathsf{OPT} + 1$. However, this Markov chain may have arbitrarily slow mixing time. We prove that, for arbitrary $p$ and arbitrary initial orderings $\sigma$, after polynomially many queries in the number of items, the expected cost of a query is at most $\mathsf{OPT} + O(1)$.