algorithm engineers

Abstract: The Hylland-Zeckhauser (HZ) mechanism provides a market-based approach to one-sided matching, making efficient equilibrium computation central to its implementation. Bi-valued utilities admit a strongly polynomial-time algorithm [VY], whereas with four values per buyer, the problem is PPAD-hard under inverse polynomial approximation [CCPY]. To understand the tractability boundary, we study two extensions of the bi-valued case: a third linear utility value and separable concave utilities with two common marginal slopes. For every fixed rational $a\in(0,1)$, we prove that computing a normalized additive $\varepsilon_{*}(a)/N$-equilibrium in an $N$-buyer HZ market is PPAD-hard for some constant $\varepsilon_{*}(a)>0$, even when all utilities belong to the same prescribed set $\{0,a,1\}$. This resolves the main question left open by [VY, CCPY]: whether three utility values already suffice for PPAD-hardness. Using the same market gadgets, we show that hardness at a specified constant accuracy on the recognizable family generated by our construction is equivalent to the PCP-for-PPAD conjecture. Consequently, assuming that conjecture, general markets over $\{0,a,1\}$ admit no PTAS unless $\mathrm{PPAD}\subseteq\mathrm{P}$. For the concave extension, we compute an exact equilibrium in polynomial time with two marginal slopes common across goods for each buyer and arbitrary rational buyer--good breakpoints. The algorithm selects a cheapest utility-maximizing bundle for each buyer. With three common marginal slopes, suitable breakpoints encode the three valued linear case, yielding PPAD-hardness. Thus, our paper identifies two thresholds separating tractable and intractable cases of HZ models with utility functions specified by utility values or marginal slopes. In both cases, the tractability threshold lies between two and three.

Abstract: Given a set system (X, S), we consider the problems of constructing perfect matchings and spanning paths (also known as Welzl orders) of X with low crossing numbers with respect to S. Matchings with low crossing numbers were originally introduced in the late 1980s in the seminal works of Welzl [29, 30] and Chazelle-Welzl [7], who showed that any set system (X, S) with bounded dual VC-dimension d has a matching with crossing number O |X| 1-1/d , which is optimal. Low-crossing matchings and spanning paths have found several applications outside of their initial realm of computational geometry, including algorithmic graph theory, model checking, and game theory. In many of these applications, |S| is near-linear in |X|, which motivated the search for an improved construction for this regime. However, the proposed new algorithms provided only average-case bounds or sub-optimal crossing number guarantees for d $\ge$ 2 [5, 12]. We propose a new quasi-uniform sampling based framework. This allows us to obtain a simple algorithm with expected running time of __ |X| 2 + |S| $\bullet$ |X| , which improves upon the previous-best Our result has several immediate consequences, including new faster algorithms for constructing low-crossing spanning paths for set systems induced by balls, as well as for neighborhood set systems of graphs. Moreover, we get the first quadratic-time algorithm for combinatorial discrepancy, with nearly optimal discrepancy (up to a log factor), for bounded dual VC-dimension set systems. Beyond these applications, we believe that our idea could be applied to other algorithms that use the multiplicative weight update method.

Abstract: The selection problem asks to find the $k$-th smallest element in a given set $X$. Its complexity is well-known to be $Θ(|X|)$ for every fixed $k$. We consider the poset selection problem where a partial order $P$ on $X$ is given, and the underlying order of $X$ is guaranteed to be a linear extension of $P$. This generalizes several variants of the selection problem studied before. Our main result is an algorithm that performs $O( k + \operatorname{OPT}(P,k) )$ comparisons, where $\operatorname{OPT}(P,k)$ is the minimum number of comparisons required for the input $(P,k)$. If $P$ is a rooted tree, we obtain an $O( \operatorname{OPT} \log (k / \operatorname{OPT}) )$ algorithm, which can be further improved to $O( \operatorname{OPT} \log \log (k/\operatorname{OPT}) )$ or $O( \operatorname{OPT} \log \operatorname{OPT})$ under mild assumptions about $P$. Our algorithms are based on the work of Kaplan, Kozma, Zamir, and Zwick [SOSA 2019], who used Chazelle's soft heaps [J. ACM 2000] to simplify several older results. We introduce a new soft heap variant, the weighted soft heap, which allows greater control over which elements get corrupted.

Abstract: We show that adding "catalytic space" (which starts full and must have its original contents restored at the end of computation) provably speeds up time-and-space-bounded computation. In a natural output model, with $O(\log(n))$ free space and poly($n$) catalytic space, we give algorithms for sorting and the discrete Fourier transform running in time $n^{1+o(1)}$, and an algorithm for matrix multiplication running in time $n^{ω+ o(1)}$. In the same output model, without additional catalytic space, sorting and DFT are known to require time-space product $Ω(n^2)$, and matrix multiplication is known to require time-space product $Ω(n^3)$ [Borodin and Cook, 1982] [Beame, 1991] [Yesha, 1984] [Abrahamson, 1991]. This is the first unconditional demonstration that (uniform, non-relativized) catalytic logspace algorithms can outperform their (non-catalytic) logspace counterparts. We give several further results relevant to fast catalytic algorithm design. We observe that many applications of sorting, FFT, and fast matrix multiplication (e.g., kSUM, integer multiplication, and clique counting) can be performed catalytically, giving catalytic logspace algorithms matching (up to subpolynomial factors) the best known unbounded-space runtimes. Furthermore, we give a fast and simple catalytic algorithm for evaluating low-depth threshold circuits, improving the previously known runtime bound from $\widetilde O(|C|4^df)$ to $\widetilde O(|C|2^d)$, where $|C|$ is the total size (i.e. number of wires) of the circuit, $d$ is the depth, and $f$ is the maximum fan-in.

Abstract: Our understanding of turn-based stochastic games is reminiscent of our understanding of linear programming in the 1970s. Instead of the simplex method, we have two families of algorithms - policy iteration and value iteration - which work well in practice but are known to run in exponential time on some input instances, and we still lack an algorithm that runs in polynomial time on all instances. A recent result by Loff and Skomra showed that, for deterministic discounted and mean-payoff games played on an ergodic graph, a variant of policy iteration runs in smoothed polynomial time. This offered an explanation of why policy iteration performs well in practice, analogous to Spielman and Teng's explanation for the simplex method. In this paper, we drop the ergodicity assumption: we show that their policy iteration algorithms run in smoothed polynomial time for any game graph. We do this by defining a condition number that naturally generalizes theirs, showing that sufficiently-perturbed games are well-conditioned with high probability, and showing that their algorithms are efficient on well-conditioned instances. Although the outline is similar, our proof requires a substantially new approach, based on log-Lipschitz distributions which recently appeared in work on the smoothed analysis of the simplex method. For our second contribution, we propose three new value iteration algorithms for solving deterministic mean-payoff games (also on any graph). All three are based on iterative methods for finding fixed points of non-expansive operators, which we show can be applied to the Shapley operator. The first two are simple applications of Krasnoselskii-Mann iteration and Halpern iteration. The third is quadratically faster but more complicated: it runs Zwick-Paterson and Halpern iterations in parallel. We prove that all three algorithms are correct and run in smoothed polynomial time.

Abstract: The Preprocessed 3SUM problem asks to preprocess a set $A$ of $n$ numbers so that we can quickly decide whether a query subset $A' \subseteq A$ contains a solution $a+b=c$. The best known query bounds differ substantially between integer and real inputs. For integers, a series of advances with near-quadratic preprocessing reduced the query time from $\tilde O(n^{13/7})$ [Chan, Lewenstein; STOC '15] to $\tilde O(n^{11/6})$ [Chan, Vassilevska W., Xu; STOC '23], and finally to $\tilde O(n^{3/2})$ [Kasliwal, Polak, Sharma; SOSA '25]. For reals, only the first of these bounds has been achieved, by adapting the corresponding integer algorithm [Fischer; SODA '25]. Is this gap inherent to the more limited tools available for real inputs? We give a randomized real-to-integer reduction with $\tilde O(n^2)$ preprocessing overhead and no asymptotic increase in query time. This yields $\tilde O(n^2)$ preprocessing and $\tilde O(n^{3/2})$ query time for real inputs, closing the gap. We show how to extend our result to the setting where one set is unknown at preprocessing time. Our reduction is conceptually simple, and relies on an interesting technical toolkit around old and new tools from sparse linear algebra. More broadly, it suggests a route to real-to-integer reductions for other additive problems.

Abstract: To facilitate the solving of complex problems, evolutionary multitask optimization is regarded as a promising technique due to its capacity for cross-task knowledge transfer. In contrast to empirical evidences, no mathematical runtime support exists for this technique within the domain of multi-objective optimization. In this work, we aim to fill this important gap. We analyze how the representative multiobjective multifactorial evolutionary algorithm (MO-MFEA) covers the Pareto fronts of two bi-objective problems simultaneously. For the two-task problem of maximizing the classic bi-objective OMM and the multimodal OJZJ benchmarks, the MO-MFEA requires only an expected runtime of $O(n^2 \log n)$---the same as optimizing the simple OMM alone---yet achieves a speedup by a factor of $Θ(n^{k-1}/\log n)$ compared to optimizing OJZJ alone (with gap size $k$). Similarly, for the task pair comprising the classic LOTZ and the multimodal DLTB benchmarks, a speedup of $Θ(n)$ is attained over optimizing DLTB alone, while the runtime matches that of optimizing LOTZ alone.

Abstract: We give a randomized polynomial-time $0.48$-approximation for maximizing a nonnegative non-monotone $k$-submodular function under a matroid constraint, for every $k\ge2$. The algorithm combines a top-two label rule with a nested-chain potential and maximum-weight matroid bases. Its analysis reduces the approximation guarantee to a one-dimensional time allocation: a uniform local lower bound leads to a linear differential equation, concavity closes the remaining interval, and two elementary budgets complete the proof. A strict saving in the time budget absorbs sampling and discretization errors, yielding the exact $0.48$ guarantee in the value-oracle model.

Abstract: Let $V_i(n)$ denote the minimum worst-case number of comparisons needed to find the $i$-th smallest of $n$ distinct elements. We construct algorithms showing $V_7(16)\le28$ and $V_8(16)\le29$, improving the previously reported upper bounds of 30 and 31. Together with known lower bounds, these results establish $V_7(16)=28$ and leave $V_8(16)\in\{28,29\}$. For 17 elements, we establish $V_5(17)=27$ and improve the upper bounds for ranks 6 through 9 to 29, 30, 31, and 31, respectively. Every new upper bound has an explicit decision-graph certificate verified by a static checker developed independently of the search. We also derive a lower bound for selection from a partially ordered state by combining the Fussenegger-Gabow weight with its order-reversed counterpart. All new upper bounds and this lower bound are formally verified in Lean 4. For $V_8(16)$, we show that a lower bound based solely on the total number of decision-tree leaves cannot establish $V_8(16)\ge29$. The algorithms were found using fixed-budget search, information-guided comparison ordering, and proof-number search. Proof-number search was decisive in finding the 28-comparison algorithm; in our experiments, refuting a comparison budget remained substantially more expensive than finding an algorithm within it.

Abstract: Alman and Vassilevska Williams (arXiv:2610.06783) gave the first polynomial improvements over the textbook algorithms for 3SUM and APSP: deterministic algorithms with exponents 1.9992 for 3SUM, 2.9983 for Exact Triangle and 2.99942 for APSP. Their algorithm has two steps: a matrix theorem, computing N^2/sqrt(D) prescribed entries of the product of an N x D and a D x N integer matrix in time N^2/D^gamma, gamma > 0, when D <= N^eps, for every eps < 0.1204; and reductions from the three problems to the lopsided sparse triangle problem. We improve both. With Schönhage's five-term partial-product tensor, the matrix theorem holds for every eps < 0.172. The preprint's reductions keep a quarter of the matrix theorem's saving for 3SUM and a half for Exact Triangle and APSP; ours keep all of it, by calling the counting version of the triangle problem adaptively and building composite moduli one prime at a time. Together this gives deterministic 3SUM in n^{1.9945+o(1)}, and Exact Triangle, (min,+)-product and APSP in n^{2.9945+o(1)}. We also improve on the preprint's proof sketch for 3XOR and solve it deterministically in O(n^{1.99451}). Which other problems on three lists does the method make truly subquadratic? It solves 3SUM over F_p^d for every fixed prime p with 3XOR's exponents, and over every finite abelian group of exponent p^2, such as Z_4^d, in O(n^{1.99726}). For coordinatewise problems with a fixed relation P on every coordinate triple, a certified exhaustive computation shows that every Boolean P, and every functional P over three letters, either is the solution set of an equation over Z, F_2 or F_3, and the problem is then truly subquadratic, or has a gadget for Orthogonal Vectors, and the problem is then hard under the Orthogonal Vectors hypothesis. Over four letters, just four functional relations, up to symmetry, satisfy neither condition.

Abstract: We give a simplified proof of the polynomial improvements for integer 3SUM and all-pairs shortest paths (APSP) established by Alman and Vassilevska Williams, with weaker exponents. The central ingredient is selected-entry matrix multiplication: computing a prescribed set of entries of a product of dense rectangular matrices. Starting from Schönhage's inner/outer-product identity, we construct a multiplication rule that shares intermediate products among many outputs. We apply this rule recursively and bound the work by counting the requested entries at each level. Applied to incidence matrices, the algorithm solves Offline Set Disjointness over a small universe. Known deterministic reductions then yield truly subquadratic integer 3SUM and truly subcubic APSP for polynomially bounded integer inputs.

Abstract: Under the Strong Exponential Time Hypothesis (SETH), for any constant $\varepsilon > 0$, the #SAT problem (counting the number of satisfying assignments of a CNF formula) cannot be solved in $\mathcal{O}^*((2-\varepsilon)^n)$ or $\mathcal{O}^*((2-\varepsilon)^m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. On the other hand, simple exhaustive search and the standard inclusion-exclusion give $\mathcal{O}^*(2^n)$-time and $\mathcal{O}^*(2^m)$-time algorithms, respectively. A natural line of research is to beat these SETH-based barriers for restricted versions, such as #$k$-SAT (where each clause contains at most $k$ literals) or #$d$-occ-SAT (where each variable appears in at most $d$ clauses). It is known that the $2^n$-barrier can be broken when $k$ or $d$ is any constant; yet, whether the $2^m$-barrier can also be broken in these cases remains unknown. We present two simple algorithms that overcome the $2^m$-barrier. First, for #$k$-SAT, we give an $\mathcal{O}^*(2^{m(1-1/O(k))})$-time algorithm, thereby breaking the $2^m$-barrier for any constant $k$. Second, for #$2$-occ-SAT (which also includes the problem of counting the number of edge covers in a graph as a special case), we provide an algorithm with runtime $\mathcal{O}^*(2^{mω/3})$, where $ω< 2.3714$ is the matrix multiplication exponent. Furthermore, we demonstrate that both algorithms generalize to the weighted counting setting while preserving the same runtime bounds. On the hardness side, we present a reduction from #Max-$d$-SAT to #$d$-occ-SAT, showing that for any $d\ge 3$, #$d$-occ-SAT admits no $\mathcal{O}^*((2-\varepsilon)^m)$-time algorithm for any constant $\varepsilon>0$, even on positive formulas, under the hypothesis that #Max-3-SAT on $n$ variables admits no $\mathcal{O}^*((2-\varepsilon)^n)$-time algorithm for any such $\varepsilon$.

Abstract: We study a natural greedy algorithm for the Airplane Refueling Problem (ARP), based on a well-known priority rule. We show that this algorithm achieves an approximation guarantee of $9/20$, noticeably improving the previously known $1/12$ guarantee for a fast algorithm. We also show that the same priority rule can be implemented in $O(n\log n)$ time and $O(n)$ space using a dynamic convex-hull data structure. These results provide a worst-case approximation guarantee for an existing greedy priority rule and establish an efficient implementation. In the real-RAM model, the running-time bound is independent of the magnitude of the processing times. The resulting method is also suitable as a fast primal routine inside more complex exact and approximation algorithms for large instances. These results narrow the gap between theoretically strong but complex approximation schemes and lightweight algorithms that can be used directly in computational pipelines. The algorithm combines a simple selection rule with a provable performance bound, making it a useful baseline for further algorithmic studies of ARP.

Abstract: Given $n$ nonnegative integer weights $w_1, \ldots, w_n$ and an integer knapsack capacity $T$, the $\#$Knapsack problem asks to count the number of subsets $I \subseteq \{1, 2, \dots, n\}$ such that $\sum_{i \in I} w_i \le T$. A long line of research has been devoted to designing faster $(1 \pm \varepsilon)$-approximation algorithms for this \#P-hard problem. Until very recently, the best-known time complexity was $\tilde{O}\bigl(n^{2.5}/\mathrm{poly}(\varepsilon)\bigr)$, achieved by the randomized algorithm of [Dyer, STOC 2003] and the deterministic algorithm of [Gawrychowski, Markin, and Weimann, ICALP 2018]. The recent work by [Feng and Jin, SODA 2025] improved the randomized complexity to $\tilde{O}\bigl(n^{1.5}/\mathrm{poly}(\varepsilon)\bigr)$, leaving open the question whether this $n^{2.5}$ barrier could also be broken by a \emph{deterministic} algorithm. In this work, we answer this question in the affirmative by presenting a deterministic $(1 + \varepsilon)$-approximation algorithm for \#Knapsack in $\tilde{O}\bigl(n^{2.4}/\mathrm{poly}(\varepsilon)\bigr)$ time. Our key technical innovation is to deterministically simulate the balancing technique, which was previously used in the literature of knapsack-type problems via random partitions and seemed to require randomization.

Abstract: Brambles of constant congestion in directed graphs have interesting structural and algorithmic applications, and it is desirable to find the smallest function $f_c(k)$ such that if a digraph has directed treewidth at least $f_c(k)$, then it contains a bramble of size at least $k$ and congestion at most $c$. By the Directed Grid Theorem of Kawarabayashi and Kreutzer [STOC 2015], such a function $f_c(k)$ exists for every value $c \geq 2$ of the congestion. However, even using the recent improvements due to Hatzel et al. [FOCS 2024], the resulting function is a power tower of height $22$. Recently, Masařík et al. [SIAM J. Discrete Math. 2022] proved that, for congestion $8$, the function $f_8(k)$ can be made polynomial; more precisely, they showed that $f_8(k) = \mathcal{O}(k^{48} \cdot \log^{13} k)$. They asked whether it is possible to decrease the congestion, ideally to $2$, even at the cost of a higher polynomial function. In this work we answer their question affirmatively with the best possible value of the congestion, by proving that $f_2(k) = \mathcal{O}(k^{96}\cdot \log^{23} k)$. We also obtain smaller polynomials for higher congestion, namely $f_4(k) = \mathcal{O}(k^{72} \cdot \log^{21} k)$ and $f_6(k) = \mathcal{O}(k^{66} \cdot \log^{18} k)$. Our results are inspired by the proof for congestion $8$, which we improve by introducing walkages. Walkages allow us to avoid technicalities of the original proof by translating ideas due to Reed and Wood [Eur. J. Comb. 2012] that work for undirected graphs to the directed setting. Our proofs are constructive and naturally yield polynomial-time algorithms to find the brambles assuming a certificate for large directed treewidth is given. Moreover, we discuss algorithmic applications of our results for the Directed Disjoint Paths with Congestion problem, and to half-integral packings of subgraphs with large directed treewidth.

Abstract: Given an integer $t$ and a set of integers in $[N]$, Subset Sum asks whether there exists a subset that sums to $t$. A long open problem is whether Subset Sum can be solved in $O(N)$ time. We show that Subset Sum can be solved in $O(N^{1 + \varepsilon})$ time where $\varepsilon > 0$ is an arbitrarily small constant. Our result also generalizes to multi-sets in multi-dimension. That is, for any fixed $d$ and $\varepsilon >0$, the $d$-dimensional subset sum can be solved in $O(n + N^{d + \varepsilon})$ time. As an application, for any fixed $d$ and $\varepsilon$, feasibility test of integer programming with $d$ constraints can be done in $O(N^{d+\varepsilon} \mathrm{poly}(\ell_{\mathrm{in}}))$ time, where $N$ is the maximum absolute value in the constraint matrix and $\ell_{\mathrm{in}}$ is the input size. Although the algorithm is quite involved, its high-level idea is clear. It is already known that when the input set is dense and $t$ lies in the interior of the zonotope, then Subset Sum is easy to solve [Galil-Margalit '91, Bringmann-Wellnitz '21, Chen-Hu-Mao-Zhang '26]. Our key observation is that a sparse input can exhibit a dense structure when lifted to higher dimension. We show that such a lifting can be done efficiently. After lifting, the interior of the zonotope is easy to tackle, and one only needs to deal with the thin area near the boundary of the zonotope. Then we show that the boundary area can be decomposed into subproblems and solved recursively, and that there cannot be too many recursion levels since each level of recursive reduces the volume of the area significantly.

Abstract: 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.

Abstract: We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas. For every sufficiently large $k$ and density $0 < α\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(α+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,α)}$. 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.

Abstract: For $κ>1$, a directed graph is $κ$-conditioned if it is $κ$-mixing and its stationary distribution is approximated by the uniform distribution within a factor of $κ$. We present a deterministic algorithm that approximates the stationary distribution of a $κ$-conditioned graph to inverse polynomial relative error in $O((\log n + \log^2 κ) \log \log n)$ space. In the regime $κ= \exp(Θ(\log^αn))$ for any $α\in (0, 2/3)$, our result improves the best-known $O(\log n \sqrt{\log κ} / \sqrt{\log \log n})$ space bound for approximating $κ$-step random walks in general directed graphs by [Hoza, RANDOM 2021]. We release this preliminary version due to recent rumors of LLM-based progress on related problems and uncertainty about when those results may appear. Further implementation details will be provided in a subsequent version.

Abstract: The matroid parity problem serves as a fundamental framework that generalizes both graph matching and matroid intersection. Although the general version is intractable, Lovász (1981) developed a polynomial-time algorithm for the linear matroid parity problem, assuming the availability of matrix representations. Subsequently, Gabow and Stallmann (1986) presented an augmenting path algorithm, which has long been recognized as one of the fastest deterministic algorithms. Since shortest augmenting paths improved algorithms for graph matching (Micali & Vazirani, 1980) and linear matroid intersection (Cunningham, 1986), extending these techniques to linear matroid parity appears to be a natural progression. However, such an algorithm has remained elusive for four decades. In this paper, we present the first shortest augmenting path algorithm for linear matroid parity. Our approach synthesizes the augmenting path algorithm of Gabow and Stallmann with the synchronized blossom formation of the Micali$\unicode{8211}$Vazirani framework. Our key technical contributions are threefold: (i) a linear-algebraic argument that bounds the lengths of shortest augmenting paths for linear matroid parity, which generalizes Cunningham's bound for linear matroid intersection; (ii) an a priori characterization of shortest search paths through lower bounds on their lengths; and (iii) an extension of the structural properties for graph matching established by Izumi, Kitamura, and Yamaguchi (2025) to the linear matroid parity setting. Our algorithm deterministically solves the linear matroid parity problem in ${\rm O}(nr^2\log r)$ time, where $n$ is the ground set size and $r$ is the matroid rank. By incorporating fast matrix multiplication, this complexity can be further reduced to ${\rm O}(nr^2)$. These results improve upon the long-standing deterministic bounds of ${\rm O}(nr^3)$ and ${\rm O}(nr^ω)$.

Abstract: We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with $d$ actions per player, we develop an algorithm achieving a duality gap of $\widetilde{\mathcal{O}}(\sqrt{d/t})$ with high probability, simultaneously at every round $t$. This improves the dimension dependence of the best previously known guarantee by a factor of $d^{3/2}$. The rate matches a standard bandit lower bound, establishing minimax optimality in both the number of actions and the number of rounds, up to logarithmic factors. The algorithm is computationally efficient, requiring only $\mathcal{O}(d)$ time and memory per round. Our technical contribution is a joint design of adaptive averaging and corrected exponential weights that absorbs estimation variance, together with a potential argument that bounds phase durations.

Abstract: In the unrestricted polynomial decision-tree model, only the number of polynomial sign tests is charged. A parity test asks for the sign of a product of pairwise differences. Such tests underlie low-depth randomized algorithms for maximum finding and top-$k$ selection, but their usual analysis assumes distinct inputs because a tie makes the product vanish. We give a black-box lifting theorem that removes this assumption. After $O(\log n)$ polynomial tests determine the number of nonzero pairwise differences, every subsequent parity test is simulated by one polynomial test, consistently with a fixed lexicographic tie-breaking order. The simulator is an elementary symmetric polynomial in masked first and second powers of all pairwise differences. Thus a depth-$D$ parity-test tree on distinct inputs becomes a polynomial decision tree of depth $D+O(\log n)$ on arbitrary inputs, with no increase in randomized pointwise error for order-selection problems. We obtain maximum finding in depth $O(\log n[\log n+\log(1/δ)])$ with error $δ$, and top-$k$ selection in depth $O(\log^2 n+k\log n)$ with inverse-polynomial error, both without any promise on ties.

Abstract: We study the stability of Boolean constraint satisfaction problems (CSPs) through the notion of average sensitivity (Varma and Yoshida, SODA 2021; SICOMP 2023). It measures the expected $1$-Wasserstein distance between an algorithm's output distributions before and after the deletion of a uniformly chosen constraint, using the unnormalized Hamming metric. We establish two dichotomies for every finite Boolean constraint language $Γ$, where $n\geq 2$ denotes the number of variables in an instance. For stable solvability, exactly one of the following holds: $\bullet$ either there is an algorithm that solves $\mathrm{CSP}(Γ)$ and has average sensitivity $O_Γ(1)$ for all satisfiable instances; $\bullet$ or every algorithm that solves $\mathrm{CSP}(Γ)$ has average sensitivity $Ω_Γ(n)$ on satisfiable instances of arbitrarily large $n$. The first alternative holds if and only if $Γ$ has finite duality: unsatisfiability can be witnessed on a bounded number of variables. For stable approximability, where a $(1-\varepsilon)$-approximation violates at most an $\varepsilon$-fraction of the constraints in expectation, exactly one of the following holds: $\bullet$ either for every $\varepsilon\in(0,1]$, there is an algorithm that $(1-\varepsilon)$-approximates $\mathrm{CSP}(Γ)$ with average sensitivity $O_Γ(\varepsilon^{-1}\log n)$ for all satisfiable instances; $\bullet$ or there exists $\varepsilon_Γ\in(0,1]$ such that every algorithm that $(1-\varepsilon_Γ)$-approximates $\mathrm{CSP}(Γ)$ has average sensitivity $Ω_Γ(n)$ on satisfiable instances of arbitrarily large $n$. The first alternative holds if and only if $Γ$ has bounded width: local consistency checks on bounded sets of variables detect unsatisfiability.

Abstract: Long-horizon reasoning remains a central challenge for large language models (LLMs) under sparse-reward regimes. We argue that this brittleness arises from two biases induced by complex reasoning spaces: an exploration bias, where models are drawn toward locally plausible but structurally unstable branches, and a compounding bias, where small local deviations accumulate across depth and suppress rare rewards. We introduce Symbolic Closure Analysis (SCA) as a theoretical lens characterizing how branching structures and sparse rewards induce these biases in long-horizon reasoning with local admissibility, and as a design principle for structural priors in less formal reasoning tasks. Motivated by this analysis, we propose SAGE (Structural Admissibility-Guided Exploration), a unified framework that injects structural guidance to alleviate exploration bias and compounding bias in long-horizon reasoning. SAGE combines two complementary structural guidance: algebraic sparsification, which projects locally admissible candidates onto operator-indexed algebraic subspaces to suppress spurious branching and mitigate exploration bias, and hyperbolic structural guidance, which embeds reasoning states into a negatively curved space to provide dense depth-wise signals and mitigate compounding bias. Across 12 benchmarks and 7 model families, SAGE outperforms competitive baselines. In particular, SAGE achieves up to an 8-fold improvement on the Andrews-Curtis problem, an open real-world long-horizon task. Code is available at: https://github.com/Susan571/SAGE-NeurIPS2026.

Abstract: The Matching-Match puzzle asks whether the vertices of a fixed graph can be colored so that the multiset of color pairs induced by its edges is exactly a prescribed multiset. We study how the complexity of this realization problem depends on the host graph. On the dense side, we give a polynomial-time algorithm for complete $k$-partite graphs for every fixed number $k$ of parts, with arbitrary precoloring and an arbitrary number of colors. We prove a sharp complement-degree threshold: the problem is polynomial-time solvable when $Δ(\overline G)\le1$, but NP-complete on completely uncolored graphs already when $Δ(\overline G)=2$. This yields a dichotomy for uniform complete multipartite graphs, and connected diameter two already suffices for NP-completeness. We also prove W[1]-hardness on cographs parameterized by the number of colors. On the sparse side, completely uncolored paths and cycles admit a linear-time characterization by Euler trails and circuits, while counting feasible colorings is $\#P$-complete on both classes. Counting is nevertheless polynomial-time solvable on stars and complete graphs, even with arbitrary precoloring. A decomposition-transfer theorem yields NP-completeness already at tree-depth two. A separate path-decomposition reduction gives a maximum-degree threshold between one and two for completely uncolored disconnected host graphs with unrestrictedly many colors. Components with at most two edges are tractable, while a disjoint union of $P_4$'s is NP-complete. Finally, precoloring restores tractability in several cases: star forests are polynomial when every center is precolored, and two broad precoloring regimes on length-two spiders are polynomial even when the number of colors is unbounded.

Abstract: In a seminal work, Buhrman et al.\ (STOC 2014) introduced catalytic computation and proved that uniform $TC^1$ circuits are computable in catalytic logspace, the class of problems solvable in space $s$ with an additional catalytic tape of size $c$, a tape whose initial content must be restored at the end of the computation. A central ingredient of their proof is the register program model. Namely, they constructed a uniform family of register programs that computes $x^n$ using $n$ registers and four accesses to $x$. Since then, determining the number of registers and input accesses required to compute a polynomial of a given degree has become a central question in the study of catalytic computation. On one hand, we prove that the four-access bound of Buhrman et al.\ is optimal: every passive-output register program computing a polynomial of degree greater than three requires at least four input accesses, independently of the number of registers. On the other hand, we show that their register bound is not optimal. For every $t\geq2$ and every field $K$ of characteristic $0$ or greater than $2t-1$, we construct a register program for $x^{2t-1}$ with four input accesses and $t$ registers. Our proofs rely on derivations and their exponential operators. This approach represents a register program as a series of exponential derivation operators, reducing register restoration to an operator identity. Finally, we use the uniform family of register programs to improve known trade-offs for catalytic streaming algorithms and register programs for matrix powering. The generalization of the lower-bound methods and the construction of the uniform family of register programs were developed with assistance from ChatGPT 5.6.

Abstract: We prove that the integer-threshold decision problem for weak partition connectivity in hedgegraphs is NP-complete, answering an open question about its computational complexity. Hardness holds even for connected unweighted hedgegraphs in which every hedge consists of exactly two nonempty, vertex-disjoint hyperedges whose union is the entire vertex set. On the same class of instances, hedge connectivity has a simple exact formula. Using a binary matrix representation, we express fractional weak partition connectivity as $m-ρ(A)$, where $ρ(A)$ maximizes the ratio of the number of selected rows to one less than the number of distinct projected columns. This formula yields both the hardness reduction and deterministic algorithms: exact computation when some reference column gives row supports satisfying a linear intersection condition, including the case of minimum row-support number $s(A)\le2$, and a partition-output polynomial-time approximation scheme (PTAS) for both the integer and fractional objectives on all full-support split systems. Unless $\mathrm{P}=\mathrm{NP}$, neither objective admits a fully polynomial-time approximation scheme (FPTAS) on this class.

Abstract: The software status quo is to use one system to process many different kinds of inputs. In contrast, we propose hyperspecialization: creating new software that is optimized for a single class of inputs. Hyperspecializing manually is anywhere from expensive to impossible. We conjecture that coding agents make automated hyperspecialization cheap, effective, and safe for problems with measurable performance and checkable output. This paper explores one such problem, SAT solving, by synthesizing hundreds of workload-specific SAT solvers at an average cost of \$37 each. Our specialists outperform their competition-winning, general-purpose cousins by 5$\times$ on average, and by over $10\times$ on a quarter of benchmark families. A general-purpose solver constructed from over a hundred of our prototype hyperspecialists won the SAT track at the 2026 SAT Competition.

Abstract: We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of order $n$, the approximation factor is \[ \exp\!\left(O\!\left(\frac{n(\log\log n)^2}{\log n}\right)\right)=\exp(o(n)). \] All previously known deterministic polynomial time guarantees for unrestricted inputs had approximation factors $\exp(Ω(n))$. Our proof uses convex optimization to tighten an upper bound on the permanent. The bound is based on weighted sums over all matchings in a bipartite graph representing the matrix, and correlations between unmatched vertices control its error. We approximate these sums deterministically using correlation decay and a bound on the effect of vertex deletion.

Abstract: Consider a permutation of $[n]$ whose values arrive one at a time. We resolve two questions about the space needed to decide natural properties of such input: First, computing the parity of the permutation requires $Θ(n)$ bits, even with randomization and constant error, and a constant number of passes. Second, every permutation pattern of length three can be detected deterministically in one pass using $O(\log n)$ bits. Together with the 2026 lower bounds of Berendsohn, this completes the classification of fixed permutation patterns; The optimal space complexity is $Θ(\log n)$ for monotone patterns and patterns of length at most three, and $Θ(n)$ for every other pattern. As a consequence, we observe that we can verify BST traversals in streaming with logarithmic memory.

Abstract: We study envy-freeness with subsidies for indivisible items beyond additive valuations. Assuming that every single-item marginal value lies in $[-1,1]$, we prove that a total subsidy of $O(n^{3/2}\sqrt{\log n})$ suffices to achieve envy-freeness among $n$ agents whenever all agents assign nonnegative values to every bundle or all assign nonpositive values to every bundle. These valuation classes include monotone goods and monotone chores, respectively, but do not require monotonicity. Our result establishes the first subquadratic total-subsidy bound for general monotone valuations that holds for every number of agents.