Papers

The Minimum Vertex Cover problem is a fundamental combinatorial optimization problem, aiming to identify a minimum subset of vertices in a graph such that every edge is incident to at least one vertex in this subset. Among its variants, the Min-Power-Cover problem stands out due to its practical applications, such as camera placement at intersections: in an edge-weighted graph, an edge is covered if one of its endpoints is assigned a power value at least as large as the edge's weight. In this paper, we introduce the Emergency Vertex Cover (Em-VC) problem where an edge may be covered not only by its endpoints, but also by a distant vertex, provided the vertex is given sufficient power to "cover" the cumulative weight of the edges along a shortest path to one of the edge's endpoints plus the weight of the edge. Em-VC is motivated by different practical scenarios, e.g. the need for urban disaster response, where ensuring accessibility to all road segments (edges of the graph) is crucial for effective aid delivery. We prove that Em-VC is NP-hard, derive lower bounds, and design a polynomial-time algorithm for its continuous version. Moreover, we present a 4/3-approximation algorithm for the discrete case and identify several special graph classes for which the problem can be solved in polynomial time.

We propose a framework for the systematic study of integrality gaps of combinatorial optimization problems with respect to a fixed linear programming formulation. The method, called integrality gap preserving reduction, consists of iteratively shrinking the input universe of the problem while guaranteeing that gap-maximizing instances remain selected. When the subset of remaining instances becomes specific enough, we calculate the integrality gap explicitly. Besides applying integrality gap preserving reductions to three well-known optimization problems via their standard linear programming formulations (weighted vertex cover problem, multiple knapsack problem, and unrelated machine scheduling problem), we analyse the restricted assignment problem via its configuration LP relaxation. We prove that the integrality gap is equal to $1$ for three “easy” subclasses of the problem that are either solvable in polynomial time or admit a PTAS (e.g., the all-one processing time case). For some remaining cases, we improve the current lower bound using our technique.

Computing influence spread under the Independent Cascade (IC) model is #P-hard, and influence maximization is commonly approached using Monte Carlo or reverse-reachable-set sampling. We study IC diffusion on bounded-treewidth graphs. Using probability distributions over separator reachability relations, we obtain exact influence evaluation in $O(n2^{O(w^2)}\operatorname{poly}(w))$ time for a graph with $n$ nodes and treewidth $w$. Our main contribution is an exact all-marginal-gains algorithm. We introduce variable artificial source edges and show that, at a deterministic seed set, the derivative with respect to each source-edge probability equals the corresponding greedy marginal gain. Reverse-mode differentiation therefore computes all marginal gains simultaneously with the same asymptotic complexity as one exact influence evaluation. This yields an exact implementation of classical greedy influence maximization in $O(Kn2^{O(w^2)}\operatorname{poly}(w))$ time, linear in graph size for fixed $w$ and seed budget $K$. We also show that the separator-relation representation has tight $2^{\Theta(w^2)}$ state complexity within exact context-independent compositional separator summaries. This contrasts with the NP-hardness of globally optimal IC influence maximization already on graphs of treewidth one and pathwidth two. Experiments on synthetic bounded-treewidth networks are consistent with linear scaling for fixed width and show that runtime is largely insensitive to propagation and seed-activation probabilities. In demanding diffusion regimes, the method substantially outperforms reverse-reachable-set and optimized Monte Carlo greedy baselines while computing greedy marginal gains exactly.

Most existing graph streaming algorithms assume the ideal scenario where each edge arrives only once. Real-world graph streams, such as communication or transaction logs, often contain many repeated occurrences of the same edge. In general, the algorithms developed for the single-edge arrival case can fail when edges can arrive multiple times. Motivated by this, we study the repeated-edge arrival graph streaming model where an edge is allowed to arrive multiple times. In this work, we study the triangle counting problem in the repeated-edge arrival model: approximate the number of triangles in the underlying simple graph despite arbitrary edge repetitions. We design the first algorithms for triangle counting with optimal space complexity. In particular, we present a single-pass algorithm that computes an $(\varepsilon,\delta)$-approximation of the number of triangles with optimal space complexity. We introduce right-to-be-forgotten graph streaming (RFGS) model, where a forget operation can cause all previous occurrences of an edge to disappear. We show that our single-pass algorithm can be extended to the RFGS model with optimal space complexity. Finally, we present optimal constant-pass algorithms that compute an $(\varepsilon,\delta)$-approximation of the number of triangles and cliques for the repeated-edge arrival graph streams.

In previous papers, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. In particular, we defined a complexity measure called Arithmetic Repetition Complexity (ARC) which admits a polynomial-time prediction algorithm with a mistake bound quasilinear in the complexity. Here, we show a weaker complexity measure related to ARC that admits an especially efficient prediction algorithm: an algorithm that runs in quasilinear time and polylog space for appropriate highly-structured sequences. The complexity measure is defined via a restricted class of "zipline programs" (a variant of straight-line programs), which we call layered. We thus get a less expressive measure with a more efficient algorithm (compared to our results for ARC), demonstrating a possible tradeoff.

There is increasing interest in queries about the context of a string $P$ in a longer text $T$, i.e., the set of all string pairs $(L,R)$, with $|L|=|R|=q$, for a given $q$, such that the string $LPR$ occurs in $T$. Such contextual queries are important in several domains but are challenging to answer efficiently. This is because the length of $T$ in applications is massive and existing indexes do not directly encode the context of a given $P$, which is key for answering retrieval queries efficiently. Our work introduces the ZigZag Trie (ZZT), a new full-text index to specifically address these challenges. This index reorganizes the text so that, for any $P$, all possible strings $L$ and $R$ growing symmetrically around $P$ are grouped into a common subtree of the index, allowing their efficient retrieval. We show how to construct the ZZT of $T$, which has size $\mathcal{O}(n)$ where $n=|T|$, in $\mathcal{O}(n\log n)$ time and $\mathcal{O}(n)$ space. On top of ZZT, we design specialized indexes that, for a query pattern $P$, answer four new types of contextual queries: (I) finding the longest string $LPR$ that occurs at least $\tau$ times in $T$, for a fixed $\tau$; (II) finding the longest string $LPR$ that occurs in at least $\tau$ texts of a text collection, for a fixed $\tau$; (III) reporting the total number of distinct contexts of $P$ in $T$; and (IV) retrieving, for a given $q$, the $k$ pairs $(L,R)$ of $P$ with the highest scores according to a given scoring function. Our indexes answer queries of type I, II, and III in optimal time, and of type IV in near-optimal time. Moreover, their size, construction space, and construction time are linear or near-linear in $n$, given ZZT. Using real billion-letter datasets, we show that our indexes answer queries orders of magnitude faster than baselines and perform similarly or better in index size and construction space and time.

Marcus, Spielman, and Srivastava [MSS15] established the existence of Kadison–Singer partitions. We provide polynomial-time algorithms for the Kadison–Singer problem. For Hermitian matrices $A_1,\ldots,A_m\in\mathbb C^{n\times n}$ of rank at most one, we give two algorithms that find signs $\sigma\in\{\pm1\}^m$ satisfying $\|\sum_i \sigma_iA_i\|\le C\|\sum_i A_i^2\|^{1/2}$. The deterministic algorithm achieves $C=3.3443$ using $\widetilde O(mn^2+n^{4.75})$ arithmetic operations. The randomized algorithm achieves $C=4.8628$ using $\widetilde O(mn^2+n^{3.58})$ arithmetic operations in expectation. For vectors satisfying $\sum_i a_ia_i^*=I$ and $\|a_i\|^2\le\alpha$, the algorithms yield partitions $[m]=I_1\cup I_2$ satisfying $\|\sum_{i\in I_j}a_ia_i^*-I/2\|\le (C/2)\sqrt\alpha$ for $j=1,2$.

A splay tree is a self-adjusting binary search tree that allows access, insertion, and deletion to be performed in amortized $O(\log n)$ time, where $n$ is the number of stored elements. The sequential access theorem states that, when the elements of a splay tree are accessed in increasing order, the amortized cost per operation becomes a constant. In this paper, we show that the upper bound for this constant is at most $5.5$ by refining the existing analysis and introducing a new potential function. Furthermore, we complement our result by showing that there exists a splay tree for which the constant is lower-bounded by almost $4$.

We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck–Fiala problem when the sets have bounded size. Let $A$ be an arbitrary matrix $A\in\{0,1\}^{m\times n}$ with at most $d$ ones per column and at most $s$ ones per row. Let $\log^*$ denote the iterated logarithm and $\ell_j$ denote the $j$-fold composition of log. Assume $s\le\exp(O(\sqrt d))$. We provide an efficient algorithm that, for arbitrary sparsity $d$, gives $O(\sqrt d(1+\log^*n))$ discrepancy. Moreover, if $d\ge\ell_j(n)$ for a fixed integer $j\ge1$, the algorithm gives $O_j(\sqrt d)$ discrepancy. The proof is a bootstrapping scheme using the Bansal-Jiang algorithm.

We show that $\bigl(\frac{\log n}{\log\log n}\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\log k)}$-time algorithms under ETH. This improves upon the previous best factors $\bigl(\frac{\log n}{\log\log n}\bigr)^{1/k}$ in (Lin, 2019) and $(\log n)^{1/\operatorname{poly}(k)}$ in (Karthik, Laekhanukit, and Manurangsi, 2019). Here $k$ is the yes-case guarantee and $n$ is the number of candidate sets. While the best approximation ratio is still $O(\log n)$ via the greedy algorithm, closing this $1/k$ gap in the exponent has been a longstanding open problem; we remove this loss via a simple direct reduction. The construction is self-contained and does not rely on the parameterized inapproximability hypothesis (PIH). Starting with sparse parameterized 2-CSP instances (Karthik, Marx, Pilipczuk, and Souza, 2024), we build a monotone CNF formula, which is equivalent to a SetCover instance. To obtain a $k$-versus-$h$ gap, the reduction enumerates all hash functions from $\Sigma$ to $[2h]$ and all unsatisfiable 2-CSP instances on the same constraint graph with alphabet $[2h]$. For each such instance, it asks for a certificate that the hashed label pairs are not all contained in that instance. Perfect hashing makes this enumeration efficient for $h=\log n/\log\log n$.

The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost tour covering all clients in a metric graph. The metric multiple-depot TSP (MD-TSP) is a natural extension, where the graph contains depots and clients, and the objective is to compute a minimum-cost set of tours covering all clients, with each tour starting and ending at the same depot. When the number of depots is part of the input, an adaptation of the Christofides–Serdyukov heuristic yields an approximation ratio of $2$. In this paper, we introduce a $(1+1/\sqrt{2})$-approximation algorithm. Like the Christofides–Serdyukov heuristic, our algorithm first computes a rooted spanning forest (RSF), then a matching to correct its odd degrees, and finally obtains a solution by shortcutting. However, instead of using a minimum-cost RSF, we construct an RSF by a primal-dual algorithm for a natural cut relaxation. The algorithm grows rootless components and the component containing all depots at different rates, adding an edge when its dual constraint becomes tight. Vertex labels record the times at which clients first become connected to a depot. The two-speed growth provides a joint bound on the forest cost and two label-dependent terms that also arise in bounding the parity-correction cost. Balancing the coefficients of these two terms by setting both to $\sqrt{2}-1$ yields the claimed approximation ratio.

We consider the question of designing a universal family of sets $F \subset 2^{[n]}$ such that for any function $f:2^{[n]} \to R_{\geq 0}$ in a certain class, we have $$\max_{S \in F} f(S) \geq c(n) \cdot \max_{S \subset [n]} f(S).$$ We prove that there is a family of subpolynomial size such that for any nonnegative submodular function, $c(n) = \Omega(\frac{\log \log n}{\log n})$, and there is a family of logarithmic size such that $c(n) = \Omega(\frac{1}{\log n})$. We also prove that pairwise independence (which achieves a constant factor for graph cut functions), or even $k$-wise independence, does not imply a bound better than $O(\frac{1}{\sqrt{\log n}})$ for submodular functions. On the other hand, we prove that for any polynomially representable subclass of nonnegative submodular functions (such as the matroid connectivity functions for matroid representable over $F_q$), a constant-factor universal family of polynomial size always exists. For absolute XOS functions (a class that we introduce, in the form $f(S) = \max_i |\sum_{j \in S} w_{ij} + c_i|$ where $w_{ij}, c_i \in R$), we design a family of polynomial size such that $c(n) \geq \sqrt{\frac{\log n}{n}}$, and prove that there is no polynomial-size family achieving a factor better than $O(\sqrt{\frac{\log n}{n}})$.

Local-to-global techniques for establishing spectral gaps have played a central role in the modern theory of Markov chain mixing times and the theory of high-dimensional expanders. One of the most striking results in this burgeoning literature is that a spectral gap for the global down-up walk on the facets of a pure simplicial complex can be reduced to sufficiently strong spectral expansion of just the codimension-2 links of the complex, a phenomenon colloquially referred to as "trickle-down". These types of theorems have had many important applications, including rapid mixing of the exchange walk on the bases of any matroid. In this primarily expository article, we give streamlined proofs of two such theorems in the literature, one by Oppenheim (2018) and one by Leake and Oveis Gharan (2025), via an integrated Bochner method. Moreover, in the latter setting, we quantitatively strengthen the dependence of the global spectral gap on the dimension of the complex and the spectral influence, resolving an open question of Leake and Oveis Gharan. Disclaimer: The proofs were developed through a couple of rounds of interaction with GPT-5.6 Sol Ultra. We later discovered that Guo and Zhang (2026) had independently proven the same strengthening of the trickle-down theorem of Leake and Oveis Gharan using an extremely similar argument, also found by GPT-5.6 Sol Ultra. The focus of their paper is the complexity of approximating the partition function of spin systems on planar graphs, not on the trickle-down phenomenon itself. In contrast, our motivation is primarily expository, and we hope to bring Bochner-type methods and their connections with the trickle-down phenomenon to the attention of a wider community of researchers.

In the Steiner Point Removal problem, we are given a graph $G=(V,E)$ with an edge-length function $\ell_G: E\rightarrow \mathbb{R}_+$ and a subset $T\subseteq V$ of terminals. The goal is to find a minor $H=(T, E_H)$ of $G$ on vertex set $T$ such that the shortest path metric derived from $G$ on the edges of $H$ preserves the distance between every pair of terminals within a small multiplicative stretch. Filtser proved that a stretch of $O(\log |T|)$ can be achieved (in polynomial time), while Chen and Tan more recently proved a lower bound of $\Omega\left(\sqrt{\frac{\log |T|}{\log\log |T|}}\right)$ on the achievable stretch. Their lower bound is via a simple construction involving low-degree high-girth graphs. The existence of such graphs is guaranteed through the existence of low-degree high-girth expanders. In this work, we improve the lower bound to $\Omega(\sqrt{\log |T|})$ using the same simple construction of Chen and Tan but with a more careful analysis that exploits the expansion property.

Figured-bass realization can be described as a sequence of choices constrained both within each sonority and between successive sonorities. This paper gives an explicit mathematical model of a restricted, examination-style four-part realization problem. Pitch spelling, range, chord membership, doubling, omission, spacing, crossing, overlap, melodic motion, consecutive perfect intervals, and selected resolution requirements are expressed as predicates. We distinguish hard constraints from optional preference costs. Four labeled notes are represented visually as the vertices of a quadrilateral and computationally as one ordered voicing state. Legal progressions become paths through a layered graph. We prove that feasibility and minimum-cost realization are polynomial-time problems for a fixed number of voices with explicit finite note domains and fixed local rules. For fixed ranges, a fixed note alphabet, and adjacent-event rules, the number of graph operations is linear in the number of events. Worked two-, four-, and eight-beat examples illustrate legality, optimization, and the failure of a greedy choice. The result concerns the stated formal model; it is not a claim that every musical judgment is captured by local predicates.

The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\varepsilon)(\alpha+2)$-approximation for the size of the maximum matching in a graph of arboricity at most $\alpha$. The algorithm uses $O(\varepsilon^{-4/3}\alpha^{4/3}n^{2/3} \text{polylog} n)$ space. For constant $\alpha$ and $\varepsilon$, this improves the best known previous space bound from $O(n^{4/5} \text{polylog} n)$ to $O(n^{2/3} \text{polylog} n)$. The algorithm is a linear sketch and requires no bounds on the number of deletions or on the arboricity of intermediate graphs.

A directed feedback vertex set of a digraph is a set of vertices whose removal destroys all directed cycles. The Directed Feedback Vertex Set (DFVS) problem asks for such a set of minimum cardinality or minimum total weight. Although general DFVS admits no constant-factor approximation under the {Unique Games Conjecture}, tournaments admit a randomized factor-$2$ approximation due to Lokshtanov et al. [SODA'20]. We extend this guarantee to two broader classes of structured digraphs, both of which also contain sparse digraphs. Our first and main result is a randomized polynomial-time factor-$2$ approximation for weighted DFVS on locally semicomplete digraphs (LSDs), a class that strictly generalizes semicomplete digraphs and tournaments. To the best of our knowledge, this is the first non-trivial constant-factor approximation for DFVS on LSDs, even in the unweighted setting. Our second result is a randomized polynomial-time factor-$2$ approximation for weighted DFVS on quasi-transitive digraphs, improving the recent deterministic $9/4$-approximation of Ghorbani and Mnich~[ICALP'26]. The algorithm follows from a simple recursive application of our composition framework. The factor $2$ is optimal under the {Unique Games Conjecture}, since tournaments are subclass of LSDs as well as quasi-transitive digraphs.

The strong matroid secretary conjecture asserts that every matroid admits a $1/e$-competitive secretary algorithm, matching the classical single-choice guarantee. We formulate a finite linear program whose value is the optimal ordinal competitive ratio of any fixed matroid; for all matroids of positive rank on seven elements and nearly all on eight, this value exceeds $1/e$. The same computations suggested that the optimal ratio is monotone under truncation of the matroid; we prove this for uniform matroids, where the ratio is strictly increasing in the rank, and refute it for a graphic matroid. Guided by this evidence, we prove the conjecture for every linear matroid, a class that includes graphic matroids, regular matroids, laminar matroids, and gammoids, giving a $1/e$-competitive ordinal secretary algorithm. The algorithm maintains bounds on the expected intersection dimension of the accepted span with every ambient subspace. Uncrossing and separation show that these bounds can be preserved while admitting each current greedy-basis element with a prescribed probability and the construction uses finite linear programs. For every matroid, we also give a single-sample prophet algorithm with competitive ratio $1/2$ in any fixed arrival order independent of the samples and values. Its output, including the selected values, has exactly the law of an independent fair thinning of an optimum from a fresh product draw. The algorithm uses $O(n^2)$ independence queries on $n$ elements. Both constants are tight in their respective models. We also give a self-contained black-box reduction that converts a single-sample prophet ratio $\alpha$ into a secretary ratio $\alpha^2/16$, preserving polynomial running time. Our single-sample algorithm consequently yields a $1/64$-competitive ordinal secretary algorithm for arbitrary matroids.

We study the space complexity of diameter estimation for a set of points in Euclidean space in the dynamic (turnstile) streaming model. The seminal work of Indyk (SODA 2003) gives a $c$-approximation to the Euclidean diameter of $n$ vectors using $n^{O(1/c^2)}$ space. Our main contribution is giving an essentially matching lower bound. Any dynamic streaming algorithm which can $c$-approximate the diameter of $n$ Euclidean vectors must use $n^{\tilde{\Omega}(1/c^2)}$ space.

The Matrix Spencer conjecture asks whether any $n$ real symmetric matrices A_1,...,A_n \in \mathbb{R}^{m \times m} of operator norm at most one admit a signing $x\in\{-1,1\}^n$ such that the operator norm of the signed sum is at most O(\sqrt{n \log(2m/n)}) We give a randomized algorithm establishing this bound with polynomial runtime in the real-arithmetic model. We first prove the $O(\sqrt n)$ bound for $m\le n$, resolving the square case, and then obtain the rectangular bound by changing the regularizer. As in earlier algorithmic discrepancy methods \cite{lovettmeka2012,bansalLaddhaVempala2022,pesentivladu2026}, we run a covariance-controlled random walk from the origin of the hypercube, rounding coordinates near its faces and keeping them fixed. Our potential measures a soft spectral edge of the evolving discrepancy matrix perturbed by an operator-valued free semicircular element. Inspired by the free interpolation approach of \cite{bbvh2023}, we combine Lehner's variational formula for the free edge \cite{lehner1999} with spectral Tsallis regularization \cite{allenZhuLiaoOrecchia2015,pesentivladu2026}. This puts the discrepancy and remaining covariance in a single smooth optimization problem. The potential has a finite-dimensional semidefinite formulation. Stability of its optimizer, governed by equations related to the matrix Dyson equation \cite{erdos2019}, lets us find a large subspace in which to move while controlling discrepancy. The square case uses the Tsallis–$1/2$ regularizer; the rectangular case uses a suitable generalized Tsallis power regularizer. Our companion paper \cite{kathuria2026ks} applies these ideas to give an algorithmic proof of Weaver's discrepancy theorem, whose existence proof by [MSS15] resolved the Kadison–Singer conjecture \cite{mss2015}.Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison–Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most $35\sqrt\varepsilon$. The algorithm walks from the origin of the hypercube to a vertex, fixing coordinates as they hit a face. Its potential measures a soft spectral edge of the discrepancy matrix perturbed by an operator-valued free semicircular element. The perturbation's covariance vanishes as the coefficients reach their endpoints. Inspired by the free interpolation approach of Bandeira, Boedihardjo, and van Handel \cite{bbvh2023}, we combine Lehner's variational formula \cite{lehner1999} with spectral Tsallis–$1/2$ regularization used in \cite{allenZhuLiaoOrecchia2015} and \cite{pesentivladu2026}. The resulting potential has a finite-dimensional SDP formulation, allowing the discrepancy and remaining covariance to be analyzed together. We analyze the optimizer's stability through the linearized Karush–Kuhn–Tucker (KKT) system of a regularized min–max problem, whose stationarity equations are related to the matrix Dyson equation \cite{erdos2019}. This gives the movement rule: either a coordinate can move toward its nearer endpoint at small spectral cost, or a low-curvature direction orthogonal to the current coefficient vector allows further progress. Choosing the better sign of this direction controls discrepancy while increasing the squared distance from the origin. Upcoming work \cite{kathuria2026higherRank} will address higher-rank Kadison-Singer and spectrally thin trees. Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

We establish a degree-independent bound on spectral independence for log-concave Holant problems on simple graphs. As a corollary, we obtain relaxation-time bounds for Glauber dynamics of $O_\lambda(m)$ for the monomer-dimer model at activity $\lambda$ and $O_{b,\lambda}(m)$ for $b$-matchings at fugacity $\lambda>0$, where $m$ is the number of edges. For uniform $b$-matchings, the relaxation-time bound improves to $O(bm)$. The main proof ideas were found using GPT-5.6 Sol.

Random walks are a standard tool for search problems in which a state can be updated locally and tested for being marked. When updating the state and checking whether it is marked have different costs, two classical strategies optimize different parts of the cost: checking after every step is optimal in the number of updates, while repeatedly checking only after mixing is optimal in the number of checks. For a single marked state $m$ and a walk started from its stationary distribution $\pi$, Dohotaru and Høyer stated that both guarantees can be matched simultaneously, for a walk that checks after blocks of a fixed length; their argument is sketched through quantum walks, and they observe that they know of no classical proof. We give a short and self-contained classical proof of such a tradeoff, for arbitrary irreducible Markov chains. The algorithm replaces the original transition matrix $P$ by the averaged walk $ \overline P_\tau = \frac{1}{\tau}\sum_{k=1}^{\tau} P^k, $ where $\tau$ is of order $\pi(m)HT(m)$. Using a coupling with the original walk and Kac's lemma, we prove directly that the averaged walk hits the marked state in $O(1/\pi(m))$ checks in expectation. The resulting search cost is \[ S + O(HT(m))U + O(1/\pi(m))C \] in expectation, where $S$, $U$, and $C$ denote setup, update, and checking costs.

We study Transient Multiagent Pathfinding, a variant of the classical Multi-Agent Pathfinding problem in which a set of agents must be routed without collisions from designated start vertices to designated destination vertices in a graph. We analyze the problem within the above-and-below-guarantee paradigm of parameterized complexity. In particular, we consider the natural upper bound \(L\), given by the sum of the shortest-path distances between pairs of agents' terminals (corresponding to sequential routing of the agents). The parameterization is given by the gap \(\zeta = L - \lambda\) between this bound and the target makespan \(\lambda\), together with the number \(k\) of agents. Our main result establishes fixed-parameter tractability for the combined parameter \(k + \zeta\). Matching lower bounds show that parameterization by \(k\) alone is W[1]-hard, and that parameterization by \(\zeta\) alone is W[1]-hard when terminals are not required to be distinct. On the positive side, if all terminals are distinct, the problem becomes fixed-parameter tractable when parameterized solely by \(\zeta\). Finally, we show that Transient Multiagent Pathfinding is unlikely to admit a polynomial kernel when parameterized by \(k + \zeta\). Together, our results provide an almost complete characterization of the parameterized complexity landscape of the problem for the considered parameters.

We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian $H$ and a projected unitary encoding of the stacked jump operator $B=\sum_{k=1}^m \lvert k\rangle\otimes L_k$, with normalization factors $\alpha_H$ and $\alpha_B$, respectively. For evolution time $t$, set $\tau=(\alpha_H+\alpha_B^2)t$. The algorithm approximates the evolution channel to diamond-norm error $\varepsilon$ using $O\!\left(\tau+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/\tau\right)}\right)$ oracle queries, matching the query lower bound for Hamiltonian simulation. The number of additional one- and two-qubit gates is linear in the query complexity up to polylogarithmic factors. The query- and gate-complexity bounds extend to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access. Our construction uses a one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst. We bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels. The gate implementation combines a compressed Kraus-label representation, which stores only the positions and values of the nonzero labels, with the rotation factorization of Chen et al.

We prove that the tensor rank of $3\times3$ matrix multiplication over $\mathbb F_2$ is at least $21$. The structural proof, independently developed by Qiushi Engine, converts occupation constraints on a single tensor factor into algebraic relations coupling all three factors. Certified quotient-rank bounds and finite geometry force any hypothetical $20$-term decomposition to have first-factor matrix-rank profile $(16,1,3)$. The ranks of the corresponding split-flattened summands therefore sum to $27$, exactly the rank of the full split flattening. Equality in rank subadditivity forces their images to form a direct sum; normalization by the inverse flattening then makes the summands pairwise annihilating idempotents. An explicit product identity for matrix multiplication implies that at most one first factor can be invertible, contradicting the three forced by the profile. The same obstruction constrains $22$-term decompositions attaining the split-rank bound. The complete proof, including the finite quotient bounds, is formalized in Lean. The accompanying research trajectory records Qiushi Engine's long-horizon autonomous research, from numerical experiments and quotient constructions to the structural proof.

We give an approximately uniform sampler for satisfying assignments of constraint satisfaction problems that satisfy $4\mathrm e p(\Delta+1)^2\le1$, where $p$ is the largest constraint-violation probability under the uniform product distribution, and $\Delta$ is the maximum degree of the dependency graph. The algorithm invokes the recent efficient approximate counting algorithm of Liu, Wang, Yin, Zhang, and Zhou~\cite{CountingLLL} as a subroutine and returns a satisfying assignment sampled within total-variation distance $\varepsilon$ of the uniform distribution in $(n+m/\varepsilon)^{O(k\Delta\log D)}$ time, where $n$ and $m$ are the numbers of variables and constraints, $D$ is the common domain size, and $k$ bounds the constraint arity. We also give an asymmetric product-form condition under which both counting and sampling are efficient. To supply the counts needed in the additional regime, we extend the marginal-expansion proof of Liu et al.

Computing the total variation (TV) distance between succinctly represented high-dimensional distributions is generally intractable. We give an FPRAS for TV distance between mixtures of product distributions and, more generally, for a natural class of structured probabilistic circuits. Our main technique is a novel application of domain reduction: Given a family of feature vectors indexed by assignments, we use Lewis-weight sampling to replace the assignment domain by a polynomial-size weighted subset that simultaneously approximates the sum of absolute values of every linear projection. For mixtures of product distributions, we construct such reduced domains incrementally over the coordinates, obtaining the first FPRAS with running time polynomial in both the dimension and the number of mixture components. We then extend the approach to smooth, structured-decomposable probabilistic circuits with a common structured architecture.

We study the canonical Maximum Clique and Maximum Independent Set problems in the one-pass edge-arrival graph streaming setting. Here, the edges of some input graph $G = (V,E)$ are presented one at a time (possibly including deletions), before an algorithm needs to produce either a large clique or independent set at the end of the stream, with the focus being on space complexity. We are interested in finding $\beta$-approximate solutions, for any $\beta \geq 1$. Previous work gave an algorithm using $\tilde{O}\left(n^2/\beta^2\right)$ bits of space, together with a corresponding $\tilde{\Omega}\left(n^2/\beta^2\right)$ two-party communication lower bound [Halldórsson et al., ICALP'12], seeming to resolve the problem. However, their algorithm crucially relies on randomness, and the best known deterministic algorithm remains a folklore derandomisation using $O\left(n^2/\beta\right)$ bits of space, leaving a (deterministic) gap of size $\tilde{O}(\beta)$. We resolve this deterministic gap with an (almost) tight lower bound: any deterministic algorithm for either problem must use $\Omega\left(\frac{n^2}{\beta\cdot\log n}\right)$ bits of space. Our proof is via a two-party one-way communication lower bound, and highlights the power of randomness when approaching either of these problems.

We consider the problem of estimating the trace of an implicit matrix $\mathbf{A} \in \mathbb{R}^{d^p\times d^p}$ that can only be accessed through matrix-vector products queries. The Hutchinson trace estimator% ~\cite{Girard1987algorithme, article-hutchinson} is a classical sketching method for this problem. Their estimator, $H_{m}(\mathbf{A}) = \frac{1}{m} \sum_{i=1}^{m} {\mathbf{z}^{(i)}}^T \mathbf{A} \mathbf{z}^{(i)}, \quad \text{where } \ {\mathbf{z}^{(i)}}\in \mathbb{R}^{d^p}$, and $z^{(i)}_j \in {N}(0, 1), j\in [d^p]$, satisfies the following guarantees: (i) $\mathbb{E}[H_{m}(\mathbf{A})]=\operatorname{tr}(\mathbf{A})$, and (ii) $\mathrm{Var}[H_{m}(\mathbf{A})]=\frac{2}{m}||\mathbf{A}||_F^2$. Generating one query vector $\mathbf{z}^{(i)}$ requires $O(d^p)$ random bits; thus, $m$ queries require $O(md^p)$ random bits, which can be prohibitive in large-scale applications. Recent work by Meyer et al.~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} proposes a variant of the Hutchinson trace estimator in which each query vector in $\mathbb{R}^{d^p}$ is constructed as the Kronecker product of $p$ random vectors in $\mathbb{R}^d$, requiring $O(mpd)$ random bits for $m$ query vectors. The estimator of~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} is unbiased; however, its variance grows exponentially with $p$. In this work, we address this limitation by proposing a sketching-based estimator that requires $O\!\big(p (d + m)\log m\big)$ random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with $p$.