Theory of Computing Report

December 27-29, 2026 Steinhardt Museum of Natural History, next to Tel Aviv University, Tel Aviv, Israel https://www.ranraz60.org Registration deadline: December 6, 2026 Please join us in Tel Aviv for a three-day conference celebrating Ran Raz’s 60th birthday. The scientific program will focus on lower bounds, randomness, space complexity, and quantum computation, four areas in which … Continue reading Celebrating Ran Raz’s 60th Birthday

By shacharlovett

December 27-29, 2026 Steinhardt Museum of Natural History, next to Tel Aviv University, Tel Aviv, Israel https://www.ranraz60.org Registration deadline: December 6, 2026 Please join us in Tel Aviv for a three-day conference celebrating Ran Raz’s 60th birthday. The scientific program will focus on lower bounds, randomness, space complexity, and quantum computation, four areas in which … Continue reading Celebrating Ran Raz’s 60th Birthday

By shacharlovett

Gil Cohen and Amir Shpilka asked me to spread the word through my blog about the celebration for Ran Raz 60th birthday.

RR60 @ Tel Aviv University – December 27-29, 2026

This conference (click for the site) brings together researchers working on central questions in computational complexity. The program will focus on several interconnected themes, including lower bounds, the role of randomness in computation, space-bounded computation, and quantum computation — areas in which Ran Raz has made seminal and lasting contributions. The conference will highlight recent developments, encourage new interactions between these areas, and celebrate Ran’s profound influence on theoretical computer science.

By Gil Kalai

The best known lower bound on the determinantal complexity of the $4\times4$ permanent is 10. In this short note, I prove that this value is exactly 15: the $4\times4$ permanent is the determinant of a $15\times15$ matrix of affine linear forms, and cannot be that of any smaller matrix. To do so, I must establish both a lower and upper bound. To establish the upper bound, I use Grenet's construction of size $2^n-1$. Hence that construction is optimal at $n=4$ (and $n=3$). This now constitutes the first known exact value of the determinantal complexity of the permanent at $n=4$, improving over prior knowledge in which the exact value was known only for $n=3$. Recall that the general quadratic bound only gives 8 for $n=4$. To establish the lower bound, I work from a normal form at a zero of the permanent. In the first row (and column) of the normal form, the linear forms vanish on a linear space inside the singular locus of the permanent. A hessian inequality bounds the size of the matrix in terms of that space. Then, a matrix of size 14 forces the space into any of nine coordinate types. The forcing is either up to symmetry, or else into a family that degenerates to one of them. I then rule out every case. All involved computations are exact. In respect of the claim, I have made all certificates public. \textbf{This note was hand-written by the human author.}

Authors: Xiao Liang, Takashi Yamakawa, Chak Fai Yung

Whether useful structured hardness can arise from unstructured assumptions is a fundamental question in complexity and cryptography. The longstanding Bennett-Gill question asks whether $\mathsf{NP}\cap\mathsf{coNP}$ remains hard relative to a random oracle; [GIKKLS, STOC 2023] recently gave a conditional affirmative answer in the classical setting. We establish the quantum analogue: if $\mathsf{UP}\not\subseteq\mathsf{BQP}$, then $\mathsf{NP}^{O}\cap\mathsf{coNP}^{O}\not\subseteq\mathsf{BQP}^{O}$ with probability $1$ over a random oracle $O$. Beyond extending the classical result, this separation has a distinctly quantum significance: Shor's algorithms defeat canonical number-theoretic hardness candidates, while lattice assumptions and other leading post-quantum cryptographic assumptions do not directly supply hard languages with two-sided classical certification on every input. Our conditional oracle separation provides evidence that such structured quantum hardness can nevertheless arise from unstructured sources. Complementing this result, we rule out fully black-box quantum reductions of worst-case quantum hardness in $\mathsf{NP}\cap\mathsf{coNP}$ to post-quantum injective one-way functions and indistinguishability obfuscation. This barrier excludes a broad class of black-box approaches to deriving structured quantum hardness from generic cryptographic primitives, providing partial evidence that the non-black-box techniques in our first result are essential.

Authors: Dmytro Gavinsky

We exhibit a total Boolean function on n input bits whose bounded-error quantum simultaneous-message (and hence one-way) communication complexity is in O(\sqrt n), whereas its randomised one-way (and hence simultaneous-message) communication complexity is in Ω(n). The same function admits a classical simultaneous-message protocol of cost O(\sqrt n) when the players share O(\sqrt n) EPR pairs.

Authors: Aditya Bandekar, Amatya Sharma, Santhoshini Velusamy

We characterize the single-pass streaming space complexity of Boolean CSP satisfiability in the strict-turnstile model for every fixed constraint language $Γ$ of $k$-ary Boolean relations that is not trivially satisfiable. Constraints can be inserted or deleted with nonnegative multiplicities; satisfiability is decided for those remaining at the end. While Sharma and Velusamy [ESA 2026] characterized insertion-only complexity via non-redundancy (up to logarithmic factors), we show that strict-turnstile complexity is governed by the integer capturing degree. For $R\subseteq\{0,1\}^k$, let $d_R$ be the minimum degree of an integer-coefficient polynomial vanishing exactly on $R$ over the Boolean hypercube, and set $d_Γ=\max_{R\inΓ}d_R$. On polynomial-length streams, we obtain an $O_k(n^{d_Γ}\operatorname{polylog} n)$-space randomized algorithm and an $Ω_k(n^{d_Γ}/\log n)$ lower bound for all algorithms. Moreover, our algorithm outputs a sparse instance preserving every satisfying assignment. This yields, to our knowledge, the first insertion-only versus turnstile separation for streaming CSPs. It also differs from the Fourier-degree characterization of exact optimization by Kol, Paramonov, Saxena, and Yu [ITCS 2023]. For $k\ge3$, $k$-XOR with literals has three distinct space complexities: $\widetildeΘ(n)$ for insertion-only satisfiability, $\widetildeΘ(n^{\lceil k/2\rceil})$ for strict-turnstile satisfiability, and $\widetildeΘ(n^k)$ for exact optimization in either model.

Authors: Søren Riis

This paper proves asymptotically optimal linear degree lower bounds for Nullstellensatz and Polynomial Calculus, yielding a four-way polynomial-versus-exponential proof-size classification for uniform polynomial consequences over fields of positive characteristic. The size bounds use full, explicit coefficient lists, including zeros. Apart from a fixed finite initial range, exactly one of four cases occurs: $\mathrm T_1$, bounded degree; $\mathrm T_2$, degree at least linear in the universe size $n$; $\mathrm T_3$, constant degree on some residue classes and at least linear degree on the others; or $\mathrm T_4$, infinitely many recurring finite degrees, with bounded-degree subsequences and finite $Ω(n)$ peaks at arbitrarily large sizes. Thus the size patterns are polynomial bounds, exponential lower bounds, a periodic mixture, or polynomial subsequences with finite exponential peaks, respectively. Underivable targets have degree $\infty$, and both proof systems assign the same type. The result strengthens my 2008--2009 refutation classification and extends it to uniform consequences. The proof uses degree-preserving lifting with onset and period bounds linear in the degree. A common $p$-adic hardness spectrum describes the four types topologically. Distinguishing any two types is undecidable already for refutations. The linear degree bounds, four-way classification and pairwise undecidability results have been formalised and verified in Lean. The Lean formalisation, verification records and an accompanying tutorial are available in the supporting materials (https://doi.org/10.5281/zenodo.23965838).

Authors: Gautam Chandrasekaran, Jesse Goodman, David Zuckerman

A quadratic source is a random variable $X\sim\mathbb{F}_2^n$ generated by applying $n$ quadratics to a hidden uniform string. Previously, the best-known explicit extractor for this model required min-entropy roughly $k=n-\sqrt{\log n}$. In this paper, we give an explicit construction for min-entropy $k=\mathrm{polylog}(n)$. Even for the special case of $2$-local sources, where each bit of $X$ depends on two hidden uniform bits, achieving an entropy requirement below $k=\sqrt{n}$ was an important open problem. This is because such sources provably cannot be reduced (in a black-box manner) to our most powerful general-purpose seedless extractor, known as a sumset extractor. Our new extractor bypasses this barrier, providing the first explicit construction to go beyond sumset extraction.

Authors: Nimrod Kaplan, Amir Shpilka, Yann Tal

We study deterministic black-box polynomial identity testing (PIT) and reconstruction for polynomials of the form \[ f(x)=\sum_{i=1}^r α_i f_i(x)^d, \] where each $f_i$ belongs to some underlying polynomial class $\mathcal{C}$. This representation generalizes Waring decomposition, several natural small-depth circuit models, and polynomial decompositions arising in moment-based learning problems. Our main results are three lifting theorems showing that, when the outer power is sufficiently large, PIT and reconstruction for the inner class can be lifted to sums of powers. When the power degree is small, we can perform these tasks directly in some of the cases using closure properties of the underlying models. In particular we obtain the following results: \begin{itemize} \item When the inner polynomials have bounded-individual-degrees and are sparse, we obtain deterministic reconstruction for every d: the original power-sum decomposition is recovered at high degree, while at low degree the polynomial is reconstructed nonproperly by sparse interpolation. \item For sums of powers of same-order and any-order read-once oblivious algebraic branching programs, the same proper/nonproper dichotomy gives deterministic reconstruction for every powering degree. \item Explicit quasipolynomial-size hitting sets for every powering degree for several depth-5 and depth-6 circuit families, as well for the models mentioned above. Our results for high powering degree rely on the polynomial ABC theorem, which to the best of our knowledge is the first application of this theorem in the context of PIT.

Authors: Armando Angrisani, Hela Mhiri

Sampling experiments are a leading approach to demonstrating quantum computational advantage, yet their robustness to experimental noise is not completely understood. We develop a common framework for classical simulation of boson and fermion sampling under thermal loss, including pure loss. For Fock-state boson sampling, Gaussian boson sampling with fixed uniform squeezing, and fermion sampling with magic inputs, we obtain polynomial-time sampling at inverse-polynomial total variation error, for any fixed nonzero overall loss rate, and with high probability over Haar-random interferometers. A milder flatness assumption on the ideal output distribution suffices for quasipolynomial-time simulation without Haar randomness. With constant thermal loss per layer, the same flatness assumption gives polynomial-time simulation at logarithmic depth. Our bounds for Fock-state boson sampling cover both dilute and saturated regimes and become stronger near full input filling: when only a bounded number of input modes are empty, the noisy output for Haar-random interferometers converges, as the number of modes grows, to a distribution independent of the interferometer.

Authors: Noel Arteche, Susanna F. de Rezende, Erfan Khaniki, Kilian Risse

We give a parallel algorithm for the Proof Analysis Problem of Arteche, Atserias, de Rezende, and Khaniki (FOCS 2025). The problem asks, given a CNF formula $\varphi$ on $n$ variables and a proof $π$ of a size-$s$ Resolution lower bound on $\varphi$, encoded as $\neg \mathrm{Ref}_s(\varphi)$, to extract a satisfying assignment for $\varphi$ when one exists. The original work gave a polynomial-time extraction algorithm for Resolution refutations that enabled a formalization of the Atserias-Müller lower bound (FOCS 2019) in Extended Frege, but it appeared inherently sequential. We devise a new algorithm that performs assignment extraction in low-depth circuit classes. Specifically, we give an assignment extraction algorithm computable by polynomial-size $\mathbf{TC}^0$ circuits and by quasipolynomial-size $\mathbf{AC}^0$ circuits, and we prove the correctness of the latter within quasipolynomial-size $\mathbf{AC}^0$-Frege. This is thanks to a new formalization of the Atserias-Müller lower bound in the relativized theory $\mathsf{T}^4_2(α)$ of bounded arithmetic, which corresponds to depth-$4$ Frege systems. This yields quasipolynomial-size $\mathbf{AC}^0$-Frege proofs for a broad class of Resolution lower bounds, making progress on a question of Pudlák. A key feature of our approach is an improved parameter regime where we get $\mathbf{AC}^0$-Frege formalizations of Resolution lower bounds $\neg \mathrm{Ref}_s(\varphi)$ for all $s$, including $s = n^{O(1)}$. W also show that the Proof Analysis Problem for $\mathbf{AC}^0$-Frege is $\mathbf{NP}$-hard under quasipolynomial-time reductions, which rules out certain Atserias-Müller-type approaches to the hardness of automating constant-depth Frege. Furthermore, automating $\mathbf{AC}^0$-Frege on Resolution lower bound formulas suffices to automate it on all formulas.

Authors: Nikolai Chukhin, Karthik Gajulapalli, Alexander Golovnev, Ivan Mihajlin

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$. Our proof gives a fine-grained variant of the connection between Polynomial Identity Testing (PIT) and circuit lower bounds established by Kabanets and Impagliazzo (2004). We show that the specific identity tests required by this argument can be performed over the integers without a derandomization assumption. Over a fixed finite field $\mathbb{F}$, we first give a deterministic $O(st^{d-1})$-time algorithm for PIT on size-$s$ circuits computing degree-$d$ polynomials in $t$ variables. We further show that, for any fixed $d\ge2$ and $\varepsilon>0$, improving this running time by a factor of $t^{\varepsilon}$, even nondeterministically, implies either the same Boolean lower bound or an arithmetic circuit lower bound of $t^{1+\varepsilon/2}$ for a polynomial family from $VNP_{\mathbb{F}}$. If nondeterministic PIT instead runs in time $s^{o(d)}t^{(1-\varepsilon)d}$ for infinitely many degrees $d$, then the arithmetic lower bound strengthens to $VP_{\mathbb{F}}\ne VNP_{\mathbb{F}}$. Over the integers, we give a deterministic PIT algorithm for syntactically set-multilinear circuits running in time $s^{O(1)}t^{5d/6}$, which yields the unconditional result above. Combining the Kabanets-Impagliazzo argument with range avoidance, we show that an NP algorithm for PIT over $\mathbb{Z}$ gives a purely arithmetic win-win: either $VP_{\mathbb{Z}}\ne VNP_{\mathbb{Z}}$, or constant-degree polynomials of maximum circuit complexity can be constructed in FNP.

Authors: Marshall Ball, Eshan Chattopadhyay, Mohit Gurumukhani, Ronen Shaltiel, Yunya Zhao

Trevisan and Vadhan [TV, FOCS'00] constructed (seedless) extractors for distributions samplable by poly-size circuits that have very high min-entropy, under the very strong complexity theoretic hardness assumption that $\mathsf{E}=\mathsf{DTIME}(2^{O(n)})$ requires size $2^{Ω(n)}$ circuits that have oracle access to $Σ_6^{\text{P}}$. In this paper we give three new explicit constructions of extractors for samplable distributions. First, we construct an extractor that extracts one bit, with constant error, for min-entropy $k=O(\log n)$, which matches the non-constructive probabilistic argument. This result uses hardness for nondeterministic circuits, and achieves the same parameters as the recent extractor of Oh and Shaltiel [OS, STOC'26] under an incomparable hardness assumption. In contrast to the extractor of [OS26], our extractor (and, similarly, the constructions below) also works for the more general class of distributions samplable with postselection (a model introduced by [BGDM, FOCS'23] that generalizes samplable and recognizable sources). Second, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=n^α$, where $α>0$ is an arbitrary constant. This result also uses hardness for nondeterministic circuits, and significantly improves upon the recent extractor of [Shaltiel, FOCS'25] which required a much stronger assumption. This extractor is also \textit{multiplicative}: a stronger notion suggested in [AASY, Comp. Complexity'16; Shaltiel, CCC'25] to make extractors for samplable distributions suitable for selecting keys for cryptographic protocols. Third, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=\mathrm{polylog}(n)$. This result uses hardness for circuits that have oracle access to $Σ_2^{\text{P}}$.

Authors: Gilles Villard

An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix $A$ over an arbitrary commutative ring R. The algorithm uses $O(n^ω)$ ring additions, subtractions and multiplications, where $ω>2$ is a feasible exponent for matrix multiplication, that is, such that two $n\times n$ matrices over R can be multiplied using $O(n^ω)$ ring operations. The algorithm involves no division and no zero test, and its control depends only on $n$: for each $n$ it is a straight-line program. The approach combines a polynomial matrix point of view and a block Krylov point of view on the characteristic polynomial, which makes Strassen's elimination of divisions efficient. A bivariate matrix $λI-L(t)$, obtained from $A$ by a homotopy, is compressed in $\log n$ steps, each of which halves the dimension while only doubling the degree in $λ$. The cost of the homotopy is controlled by truncating the power series in $t$ at an order that only grows with the compression steps, from a constant to $n$.

Authors: Kang Liu

We study the minimum number of query rounds needed to find approximate stationary points of nonsmooth weakly convex functions, measured by the gradient of the Moreau envelope. Each round permits multiple simultaneous queries. In the stated parameter regime, the standard subgradient rate is optimal in sufficiently high dimensions, even for randomized algorithms making polynomially many parallel queries per round. We then show how the order structure of the real line enables faster search: a deterministic algorithm using only function values achieves logarithmic round complexity, with a further reduction through parallel queries. Matching lower bounds hold even when each query returns the entire subdifferential. Together, these results clarify the role of dimension in determining the benefits of parallel queries for weakly convex optimization.

Authors: Vinayak M. Kumar, Ray Li, Jonathan Mosheiff, Gilad Shavit

Thresholds for local properties tell us which guarantees to expect from random linear codes (RLCs) and help us carry those guarantees over to structured codes. A monotone property is $b$-local if a collection of at most $b$ codewords can witness its satisfaction or failure, as in list decoding and list recovery. The threshold of $\mathcal P$ is the code dimension at which the probability that an RLC in $\mathbb{F}_q^n$ satisfies $\mathcal P$ crosses $1/2$ in a sharp transition. We show that the threshold of a $b$-local property $\mathcal P$ is within $O(b)$ dimensions of the expectation threshold. This is the dimension predicted by the best union bound over covers of $\mathcal P$: families of subspaces such that the span of every witness contains at least one member. This gives a general derandomization statement: Any decreasing local property satisfied by RLCs at a given rate holds at a similar rate for pseudorandom ensembles that fool the cover union bound. In addition to previously studied ensembles, these include codes whose parity-check matrix is sampled from a small-bias distribution. Because our threshold characterization applies to all local properties, this derandomization also reaches properties beyond the scope of earlier reductions, including maximum loads in linear hashing for arbitrary input sets, rank-metric list decoding, and list decoding from insertion-deletion errors and burst errors. Our theorem unifies and strengthens prior works on row-symmetric and coordinate-wise linear characterizations, which located the threshold to within $O(q^{2b}\log_q n)$ and $O(b^2+nb/\log_2 q)$ dimensions, respectively. We obtain $O(b)$ error for every $b$-local property, independently of alphabet size. Under suitable pseudorandomness bounds, the rate loss vanishes for every $b=o(n)$, compared to $b=O(\log n)$ for earlier frameworks.

Authors: Omar Alrabiah, Rohan Goyal, Venkatesan Guruswami

For infinitely many rates $R \in (0,1)$, we show that full-length Reed-Solomon codes over fields of low characteristic can contain super-polynomially many codewords in a Hamming ball of radius just exceeding the Johnson radius. Over prime fields, we exhibit full-length Reed-Solomon codes of constant rate $R$ with polynomially many codewords in a Hamming ball of relative radius bounded strictly below $1-R$. This refutes a recent conjecture that, over prime fields, list sizes below capacity are always bounded by a constant. Together, these results demonstrate that certain restrictions in recent works on explicit Reed-Solomon codes achieving list-decoding capacity, related to the choice of field or evaluation points or to the list-size guarantee, are inherent.

Authors: Mogens Plessen

A method for the problem of partitioning an area into K subareas subject to coinciding boundary segments of neighboring subareas is presented. The given area may be non-convex and may additionally include obstacle areas. The proposed hierarchical method involves three steps: repeated bisection splitting, merging and the solution of traveling salesman problems. Geographic real-world outdoors areas data is used for the evaluation of the method. The benefit of computational simplicity at the cost of imbalanced subarea sizes is highlighted.

Authors: Mikkel Abrahamsen, Jacobus Conradi, Arindam Khan, Jack Stade, Sampson Wong, Shuyi Yan, Hanwen Zhang

We study the problem of packing a given set of polygons into a minimum-area convex container, that is, placing them without overlap so as to minimize the area of their convex hull. Every previously known polynomial-time algorithm with a nontrivial approximation guarantee for packing polygons with arbitrary edge orientations required the polygons to be convex. In fact, an algorithm was not even known when every input polygon was a quadrilateral. We obtain such algorithms for the entire class of star-shaped polygons with unrestricted combinatorial complexity. The stars may be just translated or also rotated. In either case, we give an $O(\log n)$-approximation algorithm, where $n$ is the number of stars. Likewise, we get $O(\log n)$-approximation algorithms for bin and strip packing, assuming that the diameter of the stars is at most some (small) constant. Previous approximation algorithms for polygon packing focused on convex objects, and the analysis always relied on a density argument, i.e., if the area of the packed objects is at least a fraction $ρ$ of the area of the container, then we have a $(1/ρ)$-approximation. However, star-shaped polygons may need an arbitrarily large area to be packed, even when the total area of the stars approaches $0$ and each star has bounded diameter. This phenomenon prevents the use of density arguments. We instead establish a strong structural property about any packing: Even though the stars can fit together in complicated ways, we can reorganize them into simple stacks, replace these stacks by rectangles, and consider a packing of these rectangles. The rearrangement costs only a factor of $O(\log n)$, which stems from the number of size groups. We complement our algorithms by showing that both the translational and the rotational versions are APX-hard, even for constant complexity stars.

Authors: Naoyuki Kamiyama

The quickest transshipment problem is a problem defined in a dynamic network with multiple sources and multiple sinks. The goal of this problem is to send all the supplies from sources to sinks as quickly as possible. It is known that this problem can be solved in polynomial time. In particular, Schlöter, Skutella, and Tran proposed a strongly polynomial-time discrete Newton method for this problem. In this paper, we propose a simple polynomial-time discrete Newton method for the quickest transshipment problem.

Authors: Jingyang Zhao, Jason William Setiawan, Uman Khalid, Chaoning Zhang, Een-Kee Hong, Hyundong Shin

Sweep coverage requires each point of interest (PoI) to be revisited by some mobile sensor at least once during every sweep period, and it underlies persistent patrolling, environmental monitoring, and infrastructure inspection. Given a set of $N$ PoIs, each associated with a nonnegative weight representing its importance, the weighted budgeted sweep coverage problem (WB-SCP) seeks routing trajectories for a budget of $M\leq N$ identical mobile sensors with a common maximum speed to maximize the total weight of the sweep-covered PoIs. For the unweighted special case in which every PoI has unit weight, the first constant-factor approximation algorithm achieves a ratio of $0.0116-O(\varepsilon)$ for any constant $\varepsilon>0$, and whether the WB-SCP itself admits such an algorithm has remained open. In this paper, we resolve this open question by proposing two constant-factor approximation algorithms for the WB-SCP. The first converts any bifactor $(α,β)$-approximation algorithm into a $β/(2α)$-approximation algorithm, yielding a ratio of $1/16=0.0625$. The second builds on a greedy maximum-coverage framework and improves the ratio to $1-e^{-1/2}-\varepsilon$ for any fixed $\varepsilon>0$. Both algorithms also improve the best-known ratio for the unweighted case, and the second extends to heterogeneous sensors with different speeds while preserving the same guarantee.

Authors: Jingyang Zhao, Jason William Setiawan, Uman Khalid, Chaoning Zhang, Een-Kee Hong, Hyundong Shin

The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost Hamiltonian cycle in a complete undirected graph with $N$ vertices, where edge costs satisfy the triangle inequality. The biased TSP (BTSP) is a natural generalization of the metric TSP, in which the vertex set is partitioned into $k$ subsets: edge costs satisfy the triangle inequality within each subset, while edges crossing the subsets may violate the triangle inequality by a certain bias factor. This model captures scenarios in which distances are metric only locally but may be distorted across different regions or types of vertices. In this paper, we study approximation algorithms for the BTSP and its path variant, the biased traveling salesman path problem (BTSPP), which asks for a minimum-cost Hamiltonian path. Previously, constant-factor approximation algorithms were known only for the case $k=2$. Whether the BTSP and the BTSPP admit constant-factor approximation algorithms for any fixed integer $k>2$ has remained an open question. We resolve this question affirmatively. We show that both the BTSP and the BTSPP admit $O(k)$-approximation algorithms with running time $N^{O(2^k k!)}$. Moreover, for the BTSPP with $k=2$, we propose an improved $(α+2+\varepsilon)$-approximation algorithm, where $α<3/2-10^{-34}$ is the best-known approximation ratio for the metric TSP, improving upon the previous ratio of $4$

Authors: Kundan Baliga, Aiden Xie, Aditya Byju

GreedTok (Lim, Tan, Choo and Lauw, NeurIPS 2025) builds a tokenizer vocabulary greedily for the partition-cover objective: choose $k$ tokens so as to maximize the number of adjacent character pairs merged when the corpus is segmented optimally. The objective is neither submodular nor supermodular, so the classical $1-1/e$ analysis does not apply, and a worst-case guarantee was left open. We prove that GreedTok is a constant-factor approximation: on every corpus and for every budget $k$ it achieves at least $0.2752$ of the optimum, and it is optimal for $k=1$. The bound holds for both the exact greedy loop and the lazy priority-queue loop of the published algorithm and its code. The key ingredient is a shift lemma: if two occurrences of a not-yet-chosen token overlap and both are still usable, they offer exactly the same gain, so GreedTok's left-to-right scoring loses nothing when occurrences collide. A per-occurrence charging argument, with window distributions certified in exact arithmetic or given in closed form, completes the proof. In the other direction, we construct corpora on which GreedTok, with adversarial tie-breaking, achieves at most a fraction of the optimum tending to $(7-\ln 2)/12\approx0.5256$ (below $0.5380$ when every greedy choice is unique). Finally, we show that the objective is NP-hard to approximate within $1-1/31580$, to our knowledge the first inapproximability result for it.

Authors: Jiseung Kim, Minkyu Kim, Hyung Tae Lee

We give a randomized, rank-preserving reduction from exact $\ell_p$-CVP to exact Euclidean SVP for every integer $p\ge2$. For rational inputs of bit length $\ell$ on full-rank lattices $L\subset\mathbb R^N$, the reduction uses $(Cp)^N\poly(p,\ell)$ oracle calls and additional bit operations, where $C$ is an absolute constant. It uses $\poly(p,\ell)$ working space outside the oracle, and all oracle queries have rank $N$ and $\poly(p,\ell)$ bit complexity. For $p=2$, the reduction transfers polynomial-space exact SVP algorithms to exact CVP with $2^{O(N)}\poly(\ell)$ time overhead. Instantiating it with the SVP algorithms of Kannan and of Feng, Gao and Liu yields randomized polynomial-space CVP algorithms running in time $N^{N/(2e)+o(N)}$ and $N^{N/(4e)+o(N)}$, respectively. For every fixed integer $p\ge3$, the same reduction yields exact $\ell_p$-CVP algorithms for arbitrary rational targets either in randomized time and space $2^{O(N)}$, or in randomized time $N^{N/(4e)+o(N)}$ and polynomial space. These algorithmic bounds are up to polynomial factors in $\ell$. The reduction performs local search sequentially over the cosets of \(2L\), where \(L\) is the input lattice, while tracking the excess of the current objective value over the optimum. Within a coset containing a closest vector, midpoint inequalities bound the unknown correction in terms of this excess, which in turn allows us to construct many short corrections that reduce the excess bound by a factor of four. A counting argument shows that these improving corrections form a sufficiently large fraction of the lattice points in a known search region, and a sparsification-based sampler assigns sufficiently large probability to every nonzero vector in that region, using at most one SVP call per sample. For \(p\ge3\), the same framework is extended using a diagonal weighted norm computed from the current point.

Authors: Guangyan Zhou

Under the self-referential $K$-SAT exhaustive-search hypothesis (SRK-ESH), no uniform deterministic algorithm computes exact longest common subsequence or standard edit distance on binary strings in $O(n^{2-η})$ time for any fixed $η>0$, where $n$ is the longer sequence length. The same exclusion holds for one-dimensional dynamic time warping on $\{0,1,2,4,8\}$ with absolute-difference cost and for five-symbol dynamic time warping with the discrete metric. We derive Orthogonal Vectors hardness in polylogarithmic dimension by splitting the variables of the logarithmic-width source formula into two halves. Existing sequence reductions have polynomial overhead in the dimension. Their output lengths and construction times allow a fixed saving in the target exponent to yield a fixed proportional saving in the source exponent.

Authors: Nick Gravin, Jianhao Jia

We study how well approximation guarantees for clustering under one norm translate into guarantees under another. Specifically, we compare $k$-clustering in $\mathbb{R}^d$ under the $L_1$ and $L_2$ objectives, defined as the sums of Manhattan and Euclidean distances, respectively. In the worst case, the elementary relationship between these norms yields a $\sqrt{d}$ approximation bound, which is already tight for $k=2$. We therefore investigate whether stronger guarantees are possible in a natural average-case model, where the dataset is arbitrary but the coordinate system is chosen uniformly at random among all orthonormal bases. Our main result shows that, when $d=Ω(\log k)$, with high probability over the random rotation, any $β$-approximate $L_1$ clustering, with optimally chosen centers for its clusters, is also an $O(β)$-approximation under the $L_2$ objective. We also establish an expected approximation ratio of $O(β\min\{\sqrt{d},k^{2/d}\})$, yielding a dimension-independent bound of $O(β\sqrt{\log k/\log\log k})$. We obtain analogous guarantees in the reverse direction, from $L_2$ to $L_1$. We complement these results with lower bounds of $Ω(\min\{\sqrt{d},k^{1/d}\})$ in both directions, showing that our dimension-independent guarantees have asymptotically optimal dependence on $k$ for constant $β$. Our proofs overcome the dependence of the algorithm's output on the random rotation using geometric projection arguments and small Euclidean coresets. In particular, our results provide guarantees for existing clustering algorithms without requiring their redesign.

Authors: Aaron Bernstein, Henry Fleischmann, Bernhard Haeupler, Gary Hoppenworth, Thatchaphol Saranurak

The Steiner shortcut problem asks whether every directed graph $G=(V,E)$ with $n$ vertices and $m$ edges admits an augmentation $G_{+}=(V\cup V_{+},E\cup E_{+})$ with $m^{1+o(1)}$ edges such that $G_+$ has the same reachability structure as $G$ (i.e. for all $s,t\in V$, $s$ reaches $t$ in $G$ iff $s$ reaches $t$ in $G_+$), and the diameter of $G_{+}$ is $m^{o(1)}$. This is a core combinatorial question underlying many reachability algorithms in the dynamic, streaming, and CONGEST models, and all parallel algorithms with almost-linear work and sublinear depth. A sequence of works ruled out such a shortcut $G_{+}$ in the non-Steiner setting where $V_{+}=\emptyset$. However, as recently shown by Bernstein et al. [STOC '26], all known non-Steiner lower-bound constructions fail once Steiner vertices $V_{+}$ are allowed. This paper rules out almost-optimal Steiner shortcuts: we show an infinite family of graphs $G=(V,E)$ with the property that, for any $\varepsilon>0$, a Steiner shortcut $G_{+}=(V\cup V_{+},E\cup E_{+})$ with $m^{1+\varepsilon}$ edges must have diameter at least $n^{1/56-O(\varepsilon)}$. Our construction strengthens the standard non-Steiner lower-bound framework via an additional structure that allows Steiner vertices to be replaced by original vertices; we can then reduce back to the standard arguments without Steiner vertices. This new structure is achieved via a new general strategy based on test functions, which is quite flexible and can potentially be extended to applications beyond our work. We also generalize our lower bound to exact Steiner hopsets in undirected graphs and to depth reduction for monotone circuits. The latter significantly strengthens the classical lower bound based on Sylvester matrices.

Authors: Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara

Several landmark oracle results (FOCS 2000, FOCS 2025, STOC 2026) establish strict separations along the chain $\mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}$, showing that quantum verification and quantum witnesses can each provide additional power over classical proof systems. These separations, however, use substantial coherent quantum computation, often through the quantum Fourier transform. We prove that a minimal quantum resource already suffices to outperform every classical verifier. Namely, we show the separation $$\mathsf{MA} \subsetneq \mathsf{StoqMA}$$ relative to a classical oracle. The class $\mathsf{StoqMA}$, introduced by Bravyi, Bessen, and Terhal (arXiv 2006), restricts the verifier to classical reversible computation, followed by a single Hadamard-basis measurement. Its power is closely tied to the complexity of stoquastic Hamiltonians, a sign-problem-free and seemingly more tractable class of quantum Hamiltonians. Our separating problem is to determine whether a sparse high-girth graph, given via an adjacency-list oracle, has a large or small Perron--Frobenius eigenvalue. This amounts to a ground-energy estimation task for a related stoquastic Hamiltonian. Our construction builds on a line of work on graph exploration problems with exponential quantum speedups, from welded trees (STOC 2003) to recent constructions (STOC 2021, arXiv 2026).

Authors: Karthekeyan Chandrasekaran, Harshul Sagar

The canonical cut hierarchy recursively partitions a graph along Tutte-Nash-Williams partitions, choosing the partition with the most number of parts at each step. We give a randomized almost linear-time algorithm for computing this hierarchy in undirected graphs with polynomially bounded capacities via reduction to max-flow. This yields randomized almost linear-time algorithms for computing partition connectivity, strength, both arboricity and fractional arboricity, both integral and fractional spanning tree packing numbers, and implicit representations of the principal partition sequence and a maximum fractional spanning tree packing.

Authors: Yuhao Lei

We determine the sharp order of discrepancy in Tusnády's problem in every fixed dimension $d\ge 2$. The largest combinatorial discrepancy of $N$ points in $\mathbb{R}^d$ with respect to axis-parallel boxes is $Θ_d((\log N)^{d-1/2})$, extending Wei's planar result and matching Nikolov's upper bound. More strongly, with high probability, this lower bound holds simultaneously for every subset obtained by deleting at most a sufficiently small fixed fraction of a uniform $N$-point sample. We apply this geometric estimate to online thinning of two independent samples of size $n$ from an unknown common distribution, where observations must be kept or discarded upon arrival. For every fixed dimension $k\ge 1$ and expected deletion budget $ρn$, with $0<ρ<2$, we prove that the minimax expected prefix discrepancy over lower orthants is $Θ_{k,ρ}((\log n)^{k+1/2})$. In dimension one, the optimal terminal discrepancy is instead $Θ_ρ((\log\log n)^{3/2})$, giving a sharp separation between the prefix and terminal objectives. For $k\ge 2$, we obtain terminal bounds differing by a factor of $\log n$. The lower bounds are based on Gaussian small-ball estimates for box-incidence matrices, while the upper bounds use stationary Metropolis thinning and, in one dimension, a terminal cancellation procedure.

Authors: Andreas Galanis, Daniel Stefankovic

We develop a new framework for sampling at low temperatures using Glauber dynamics. In this regime, the coexistence of competing modes (commonly referred to as phases) creates bottlenecks that can make worst-case mixing exponentially slow. The main new ingredient in our framework is to relate convergence within a phase to the geometry of disagreements between two independent configurations drawn from that phase. As applications of our approach, we consider three canonical models on random regular graphs that have been central to low-temperature sampling, and establish fast convergence from natural initialisations of Glauber dynamics for every fixed degree. We show: --- For the hard-core model on random bipartite $d$-regular graphs, Glauber dynamics initialised from either one-sided independent set mixes within the corresponding phase in $n^{3/2+o(1)}$ steps throughout the non-uniqueness regime $λ>λ_c(d)$. --- For the random-cluster model on random $d$-regular graphs, for every real $q>2$, Glauber dynamics initialised from the all-in edge set mixes within the ordered phase in $n^{3/2+o(1)}$ steps for all $β\geq β_c$. Similarly, Glauber dynamics initialised from the all-out edge set mixes within the disordered phase in $n^{3/2+o(1)}$ steps for $β\leq β_c$. --- For the ferromagnetic Ising model on random $d$-regular graphs, Glauber dynamics initialised from all-plus or all-minus mixes within the corresponding phase in $n^{3/2+o(1)}$ steps throughout the low-temperature regime $β>β_c(d)$. We also give an $n^{2+o(1)}$-time algorithm that combines phase samples into samples from the full distribution, avoiding in particular time-costly approximations of the corresponding partition functions to the target sampling accuracy.

Authors: Sanjeev Khanna, Aaron Putterman, Junkai Song

We continue the study of the classic \emph{generalized sorting problem}, a basic variant of ordinary sorting. There are $n$ elements and an (initially hidden) total ordering $π$ over them. Unlike in ordinary sorting, however, only \emph{some} comparisons are allowed: those given by the edges of an undirected graph $G = (V, E)$ on the elements. How many comparisons are needed to find the total ordering? In ordinary sorting, $Θ(n \log n)$ comparisons are necessary and sufficient. For generalized sorting, however, the best known upper bound has been $\tilde{O}(n^{3/2})$ since the work of Huang, Kannan, and Khanna (FOCS 2011), who even asked whether the problem might in fact require $n^{1+Ω(1)}$ comparisons. We show that it does not: we give a randomized algorithm that uses $O(n \log^4 n)$ comparisons in expectation. Thus, up to logarithmic factors, generalized sorting is no harder than ordinary sorting.

Authors: Bardiya Aryanfard, Monika Henzinger, John Kuszmaul, Jakob Nogler, Virginia Vassilevska Williams

We introduce a new model for dynamic algorithms in which the algorithm has read-only oracle access to a dynamically changing input and random access to its own bounded workspace. It is a dynamic analogue of the time-space tradeoffs for static inputs studied in complexity theory, where only writable memory counts as space. We study dynamic undirected $s$-$t$ connectivity: after every edge update to an $n$-vertex graph, an algorithm with $S$ words of workspace must report whether $s$ and $t$ are connected. The graph is accessed via adjacency list queries (degree, $j$-th neighbor) or adjacency matrix queries. Our algorithms are randomized; our lower bounds hold for randomized algorithms with $cn$ bits of workspace, $c>0$ a small constant ($cn/\log n$ for the worst-case matrix bound). We prove: (1) With adjacency lists, worst-case time $\tildeΘ(n^2/S^2)$ per insertion is necessary and sufficient for incremental algorithms. (2) With an adjacency matrix, worst-case time $\tildeΩ(n^2/S)$ per insertion is necessary for incremental algorithms, and sufficient for $S\ge\sqrt{n}$. (3) With amortization, incremental algorithms achieve $\tilde O(n/S)$ time per insertion with adjacency lists and $\tilde O(n^2/S)$ with an adjacency matrix, while $\tildeΩ(\sqrt{n/S})$ and $\tildeΩ(n\sqrt{n/S})$, respectively, are necessary. (4) Fully dynamic algorithms need amortized time $\tildeΩ(n/S)$ per update with adjacency lists and $\tildeΩ(n^2/S)$ with an adjacency matrix, even on forests, where both bounds are tight (lists: under bounded degree). Conventional dynamic connectivity admits polylogarithmic update time with $Ω(n)$ words of space. In contrast, our lower bounds show that polynomial update time is necessary whenever $S\le n^{1-\varepsilon}$, even for a single pair of vertices and even for incremental algorithms with amortized guarantees.

Authors: Zhaienhe Zhou

We give a deterministic, strongly polynomial algorithm running in $\tilde{O}(km+k^4n)$ time that finds $k$ arc-disjoint arborescences of minimum total cost in a directed multigraph with $n$ vertices and $m$ arcs. This significantly improves upon the state of the art for $k \ge 2$ with $k=n^{o(1)}$: the prior fastest weakly polynomial and strongly polynomial algorithms take $\tilde{O}(km\sqrt{n}\log C)$ and $\tilde{O}(kmn)$ time (Gabow and Xu, 1989; Gabow, 1995), respectively. Roughly, our technique can be viewed as a way to apply a linear number of \emph{shortest} augmenting paths in near-linear total time for the special case of the weighted matroid intersection problem between the $k$-fold graphic matroid and the indegree partition matroid. This was previously done in the unweighted case by Gabow (1995), but our approach is different. As an extension, we also obtain a deterministic $\tilde{O}(km^{1+o(1)}+k^5n)$-time algorithm for minimum-cost maximum-cardinality packing of $k$ forests in undirected graphs. In particular, this finds $k$ edge-disjoint spanning trees of minimum total cost, if they exist. The previous fastest algorithm takes $\tilde{O}(kn^2+m)$ time (Gabow and Westermann, 1992).

Authors: Chao Xu

We compute Cunningham's canonical decomposition of a symmetric submodular function on $n$ elements in $O(n^3)$ time. The decomposition represents all minimum cuts in linear space. For the pair $s,t$ produced by Queyranne's algorithm, we construct in $O(n^2)$ time a digraph representing exactly the minimum $st$-cuts of the function. Using this construction in Chekuri and Xu's decomposition algorithm gives the cubic bound.

Authors: Aditya Anand, Evangelos Kipouridis, Karol Węgrzycki

The Minimum Bisection problem asks whether an $n$-vertex graph can be split into two halves with at most $k$ edges between them. We give a single exponential time algorithm for minimum bisection, running in time $2^{O(k)}n^{O(1)}$. This improves the previous bound of $2^{O(k\log k)}n^{O(1)}$ due to Cygan, Komosa, Lokshtanov, Pilipczuk, Pilipczuk, Saurabh, and Wahlström (TALG 2021). Our algorithm counts solutions instead of only finding if one exists. We show that our dynamic program can be implemented on top of an unbreakable decomposition using algebraic techniques. Along the way, we compute in time $2^{O(k)}n^{O(1)}$ a tree decomposition with adhesions of size at most $2k$ whose bags are $(3k,k)$-edge-unbreakable inside their own subtrees.

Authors: Johannes Brüstle, Simone Di Gregorio, Federico Fusco, Stefano Leonardi

Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. We study this problem from the perspective of a profit-maximizing broker in a regret minimization framework. At each time step, a new seller and buyer arrive and the broker proposes a trading price to each agent. The trade happens if both agents accept, and the profit of the broker is the difference between the price received from the buyer and the one paid to the seller. At the end of each interaction, the learner only observes whether the trade occurred, and its goal is to achieve sublinear regret relative to the best fixed pair of prices in hindsight. We start by investigating the adversarial version of the problem, where buyer and seller valuations are generated by an adversary. In this setting, we construct a polynomial-time learning algorithm with a $\tilde O(T^{\frac 23})$ regret rate, which is nearly tight even if the valuations are drawn i.i.d. from independent distributions, thus matching the rate for one-sided pricing. Our adversarial algorithm combines a localized estimation procedure with an information-based minimax construction. We then consider valuations drawn i.i.d. from independent distributions satisfying the monotone-hazard-rate (MHR) property and provide a learning algorithm with nearly tight $\tilde{O}(\sqrt{T})$ regret. The algorithm combines localized estimation with a stochastic convex bandit routine applied to the negative logarithm of expected profit. Finally, we complement this result by showing a separation between MHR and regular distributions, proving that the minimax regret rate in the latter setting is $\tilde Θ(T^{\frac 35})$. This last result contrasts with the $\tilde{O}(\sqrt{T})$ regret bound that can be obtained for one-sided pricing with regular distributions.

Authors: Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk

Monadically dependent graph classes are those in which first-order logic cannot encode all graphs. They include all nowhere dense classes and all classes of bounded twin-width. We show that first-order model checking is fixed-parameter tractable on every monadically dependent graph class. Together with the known hardness result for hereditary classes that are not monadically dependent, this gives a complete characterization of the hereditary graph classes with fixed-parameter tractable first-order model checking. This resolves a central open problem in algorithmic model theory. Our proof combines ideas from structural graph theory (graph decompositions), finite model theory (locality of first-order logic), and model theory (counting types). In particular, we show that in monadically dependent classes, tuples of fixed length have only $|U|^{O(1)}$ types of fixed quantifier rank over any set of parameters $U$.

Authors: Arpon Basu, Andrew D. Lin, Peter Manohar

We give a $n^{O(\ell)}$-time algorithm for solving semirandom planted instances of a $k$-ary Boolean constraint satisfaction problem (CSP) with $m \gtrsim \left(\frac{n}{\ell}\right)^{k/2} \ell \, \mathrm{polylog}(n)$ constraints, for any choice of the runtime parameter $\ell$. Up to $\mathrm{polylog}(n)$ factors, this matches the known runtime vs.\ number of constraints trade-off for refuting semirandom CSPs, as well as the trade-off for solving fully random planted CSPs. Prior work on designing algorithms for semirandom CSPs follows a high-level blueprint of decomposing the constraint hypergraph $\mathcal{H}$ of the instance into pieces, each with an explicit pseudorandom property that allows the standard algorithm for random CSPs to succeed on every piece. We depart considerably from this framework and instead implicitly \emph{learn} such a decomposition, without appealing directly to explicit properties such as expansion. More generally, we construct such a learning algorithm from the assumption that semirandom $k$-XOR has Sum-of-Squares certificates of refutation. This yields the broader implication that any Sum-of-Squares refutation algorithm for semirandom $k$-XOR gives a corresponding algorithm for solving semirandom planted CSPs, and instantiating this reduction with known Sum-of-Squares algorithms for refuting semirandom $k$-XOR gives our main algorithm. To the best of our knowledge, this is the first reduction from search to refutation for (semi)random CSPs.

Authors: Zhao Song

We give a randomized algorithm for feasible bounded-box linear programs with $n$ variables and $d\le n=O(d)$ linearly independent equality constraints. For additive accuracy $ε$, its expected running time is $O((n^ω+n^2\log n)\log(1/ε))$, where $ω$ is the matrix multiplication exponent. This answers the matrix-multiplication-time open question posted in Song's Ph.D. thesis [Son19] in this setting.

Authors: Mugen Blue, Sungjin Im, Alexander Lindermayr

Dominant Resource Fairness (DRF) is an influential policy for sharing multiple resources among jobs with heterogeneous demands. It combines sharing incentive, strategy-proofness, envy-freeness, and Pareto efficiency, making it particularly attractive for shared computing systems. DRF has been implemented in major resource-management frameworks, including Apache Mesos and Hadoop YARN. DRF is also nonclairvoyant: it requires no advance knowledge of job sizes, making it practical when processing requirements are difficult to predict. This motivates understanding its completion-time performance relative to an optimal schedule that knows all job sizes. However, elementary arguments can only give an $Ω(\sqrt D)$ lower bound and an $O(D)$ upper bound for total completion time, where $D$ is the number of resource types. In this paper, we close this gap by proving that DRF is $Θ(\sqrt D)$-competitive. More generally, for every fixed real $q\geq1$, we show that DRF is $Θ(D^{1/(q+1)})$-competitive for the $\ell_q$ norm of completion times, with larger $q$ placing greater emphasis on late-finishing jobs. These bounds hold with arbitrary release times. We also give a refined analysis of total completion time for small $D$.

Authors: Eduard Eiben, Roohani Sharma, Magnus Wahlström

We give deterministic polynomial-time constructions of vertex multicut-mimicking networks of quasi-polynomial size. Given a graph G, a terminal set T, and a positive integer c, our algorithm constructs a graph with |T|^7 c^{O( log c ) } vertices that preserves every minimum vertex multiway cut value of at most c, for every partition of the terminals. Setting c=|T| gives an exact vertex multicut-mimicking network with |T|^{O( log |T| ) } vertices, resolving an open question of Wahlström [ACM Transactions on Algorithms 2022], who showed a bound of κ^{O( log^3 κ)} for the edge multicut-mimicking variant, where κ:= \sum_{t \in T} |N_G(t)| is the capacity of the terminal set, which was later improved to κ^{O( log^2 κ)} by Anand, Lee, Li and Saranurak [STOC 2024]. As applications of our vertex multicut-mimicking network, we obtain deterministic kernels of size k^{O( log k )} for Vertex Multiway Cut, p^{O(1)} k^{O(log k)} for Vertex Multicut with p requests and |Γ|^{O(1)} k^{O( log k)} for Group Feedback Vertex Set, where k is the deletion budget and Γis a finite group. Our first kernelization result, in particular, resolves an open question by Wahlström [ACM Transactions on Algorithms 2022], which was reiterated in a recent survey on kernelization by Jansen [Computer Science Reviews 2026]. Also, to the best of our knowledge, our kernel for Vertex Multicut is the first one whose size is completely polynomial in p and (quasi-polynomial) super-polynomial only in k. Finally, again using our vertex multicut-mimicking network for graphs, we obtain a hyperedge multicut-mimicking network for hypergraphs, which preserves hypergraph edge-multicuts of size up to c, of size |T|^{O(1)} c^{O(log c)}. Our result removes the dependence on the rank of the hypergraph from the exponent of the size bound, that existed in prior work.

Authors: Haoyuan Ma, László A. Végh, Adrian Vladu

Linear Complementarity Problems (LCPs) with sufficient matrices form a well-studied class of problems, dating back from the foundational works of Cottle and Dantzig (1968). LCPs capture convex quadratic programs, and admit reductions from problems such as discounted stochastic games or mean-payoff games. While the original approach for solving these problems was based on pivoting methods, in their 1991 book, Kojima, Megiddo, Noma, and Yoshise introduced an interior point method (IPM) with running time that is polynomial in the input size, but which depends linearly on a certain parameter called the handicap number of the matrix. Despite the ensuing rich literature on sufficient LCP IPMs, the linear dependence on the handicap number has not been improved since then. We present an IPM whose running time depends on the square root of the handicap number. The algorithm can decrease the duality gap by a constant factor in $O\left(\min\left\{\sqrt{n} (1+κ),n^{9/8}\sqrt{1+κ}\right\}\right)$ iterations. Curiously, this can already be achieved using standard Newton updates. We analyze the IPM in a norm defined by a local weighting, where centralizing Newton steps quadratically converge to the central path, without any dependence on the handicap number. The weights arise from a characterization by Rump (Linear Algebra and Its Applications, 1997, 1998, 2003) of the sign-real spectral radius and its relation to sufficiency; another ingredient of our proof is a new operator norm characterization of the handicap number. Moreover, the connection to Rump's work also enables us to show coNP-completeness of testing sufficiency, and approximation hardness of the handicap number.

Authors: Chengzhi Guo, Shaofeng H. C. Jiang, Robert Krauthgamer, David P. Woodruff, Shenghao Xie, Samson Zhou

We design adversarially robust algorithms for dynamic geometric streams that $(1 + ε)$-approximate $k$-Median and $k$-Means in Euclidean space $\mathbb{R}^d$, using $\tilde{O}(kd \mathrm{poly}(ε^{-1}))$ space. This result significantly improves a recent $O(d\log n)$-approximation for $k$-Median [Gribelyuk, Lin, Woodruff, Yu, and Zhou, FOCS 2026], and is furthermore the first algorithm whose space is linear in $kd$, even in the oblivious (non-adaptive) setting. We develop several new techniques which may be of independent interest, including a new data-oblivious Euclidean primitive called hierarchical Lipschitz assignment, a robust dimensionality reduction for clustering, and a robust streaming algorithm for inner-product queries.

Authors: Przemyslaw Uznanski

We study $(1 \pm ε)$-approximate text-to-pattern Hamming distance: given a length-$N$ pattern and a length-$2N$ text, compute the Hamming distance at every alignment to relative error $ε$. For every fixed $a \ge 0$ and $ε= N^{-a}$, we give a randomized algorithm with simultaneous high-probability correctness on a logarithmic-word RAM and expected running time $\widetilde{O}(N^{ω(4a)/2})$, where $\widetilde{O}$ suppresses subpolynomial factors and $ω(k)$ is the exponent for multiplying an $n \times n^k$ matrix by an $n^k \times n$ matrix. With a recent rectangular bound, this improves the published bounds [CGK+20, FKN26] for $1/12 < a < (3 + \sqrt{3})/16$. In particular, the algorithm runs in expected time $\widetilde{O}(N)$ for $0 \le a \le 1/8$, extending the previous near-linear guarantee through $a = 1/12$.

Authors: Kejing Lu

We study the degree needed for greedy graph search to find the exact nearest neighbor from every starting point on graphs of $n$ independent data points on the unit sphere in $\mathbb R^d$. For uniform data, we determine an explicit sublinear degree threshold when $d$ is proportional to $\log n$, and the threshold $2^{d/2+o(d)}$ in the dense regime $\sqrt{\log n}\ll d\ll\log n$. Above these thresholds by fixed exponent gaps, the nearest-neighbor graph succeeds from every entry for most uniform queries with high probability, with evaluation cost on the same exponential scale as its degree. Matching lower bounds hold for every graph designed after observing the sample. For nonuniform data in the dense regime, local density variation shifts the critical degree. Under explicit local regularity conditions and within a specified range of density variation, we derive a sharp worst-case degree curve and show that the nearest-neighbor graph attains it. We construct sampling densities and query distributions for which, with high probability, every graph whose degree lies below this curve by a fixed exponent gap has failing entries for most queries. Allowing fresh uniform random entries reduces the cost of exact recovery. For uniform data in the dense regime, we determine the exact exponent for the number of distinct distance evaluations over a range of degrees below the critical threshold. Independent restarts on a single graph joining points within a prescribed radius attain this exponent with high probability. Matching lower bounds hold for adaptive local exploration on threshold and nearest-neighbor graphs using entries independent of the data. Optimizing within this degree range lowers the exponent from $\frac12\log2\approx0.347$ for success from every entry to approximately $0.243$.

As everyone knows, this week was a (an?) historic one for the State of Texas and for the United States as a whole—because this is the week when my wife Dana finally gave a 3-hour public lecture on OpenAI’s recent proof of the Unique Games Conjecture! Thanks so much to the nearly 200 people who joined us in person or via Zoom, and to the staff of UT Austin’s CS department for pulling the event together on short notice. Video will be up on YouTube as soon as we can manage it.

But also, yes, there was an election.

I remember that, when Dana and I moved to Texas in the summer of 2016, we were excited to be a small part of what seemed at the time like Texas’s impending transformation into a cosmopolitan blue state.

And now the prophecy is finally being fulfilled. But so many strange and harrowing things have happened in the interim, that I feel like Murph when her father finally returns to her at the end of the movie Interstellar.

So it turns out that, indeed, the Democrats could’ve easily recaptured both houses of Congress without any need to sell their souls to the likes of Hasan Piker or Abdul El-Sayed. And now the keffiyeh-clad revolutionaries will claim a mandate directly from the people, to put to the sword all the evil landlords and techbros and kulaks and bourgeoisie and (obviously) Zionists, and thereby finally usher in the utopia that failed the first 10,000 times it was tried. I see them as more likely to inspire a Republican comeback in 2028 (as unlikely as it seems this week) than to achieve their stated goals.

For please remember that the socialist firebrands massively underperformed more moderate Democrats on Tuesday—it looks like the socialists were merely lifted up by the same tide of justified anti-MAGA rage. Yes, in the US and across the Western world, some university humanities departments continue to churn out young people who’d see my family’s slaughter as an inspiring (or at least deeply understandable) act of revolutionary justice, and who vote on that basis. By and large, though, the American voters simply belatedly realized that Trump is a charlatan who was never going to deliver anything he promised, and also they wanted cheaper gas.

The Allied victory over Nazi Germany was glorious, it called for parades and dancing in the street, and it was 3,000% earned by Nazi behavior if anything in human history ever was. It left only one tiny problem for the future—namely that, within the winning coalition, the fans of liberal democracy, science, and Enlightenment still needed to confront the Stalinists, whose evil rivaled even the Nazis’, yet who believed their fanatical ideology to be the one vindicated by events. Why was I so often thinking about that these past couple days?

There was, of course, also a big election in Israel. Given the results, I pray that Gadi Eisenkot finds some way to form a coalition, or at least soft coalition, with Israel’s Arab parties, since that’s clearly what it will now take finally to topple Netanyahu, a man whose corruption (like Trump’s or Ken Paxton’s) knows no bounds. I’m under no illusions that this step would do anything to appease the hundreds of millions of protesters around the world whose true demand (as they’ll explain if you ask them) never had anything to do with Israeli policies or Gaza or the West Bank or Bibi Netanyahu, but was always simply that Israel cease to exist—that Israel’s Jews either “go back to Poland” or the other countries where their grandparents were murdered or expelled, or preferably just die, as on October 7.

Nevertheless, I pray for a coalition of moderate Israeli Jews and Arabs, firstly because it’s morally right, secondly because it’s politically expedient, and thirdly because it will impress on at least some fair-minded observers the enormity of the moral chasm here—that, whereas the Arab countries expelled or murdered virtually all of their Jews, the State of Israel not only tolerates its Arab minority but gives it the right to vote and to wield power.

Whatever else one can say, Israel’s Arabs have been sufficiently loyal to their nation that, on October 7, Hamas murdered them right along with the Jews, treating them as Zionist collaborators and traitors to Islam. I’d like to see that loyalty rewarded with a role in Israel’s governing coalition.

As is becoming standard practice with my political posts, I’m closing the comments—because life is short, and these days, the overwhelming majority of comments that I get on posts like this one, whichever ideological axe they’re grinding, are not ones that engender in me even minimal respect for their authors. I apologize to those who would’ve actually pursued a thoughtful dialogue with me or others had I left the comments open—to all five of you, or however many righteous men of Sodom there might be.

By Scott

Trevisan and Vadhan [TV, FOCS'00] constructed (seedless) extractors for distributions samplable by poly-size circuits that have very high min-entropy, under the very strong complexity theoretic hardness assumption that $\text{E}=\text{DTIME}(2^{O(n)})$ requires size $2^{\Omega(n)}$ circuits that have oracle access to $\Sigma_6^{\text{P}}$. In this paper we give three new explicit constructions of extractors for samplable distributions. First, we construct an extractor that extracts one bit, with constant error, for min-entropy $k=O(\log n)$, which matches the non-constructive probabilistic argument. This result uses hardness for nondeterministic circuits, and achieves the same parameters as the recent extractor of Oh and Shaltiel [OS, STOC'26] under an incomparable hardness assumption. In contrast to the extractor of [OS26], our extractor (and, similarly, the constructions below) also works for the more general class of distributions samplable with postselection (a model introduced by [BGDM23] that generalizes samplable and recognizable sources). Second, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=n^{\alpha}$, where $\alpha>0$ is an arbitrary constant. This result also uses hardness for nondeterministic circuits, and significantly improves upon the recent extractor of [Shaltiel, FOCS'25] which required a much stronger assumption. This extractor is also multiplicative: a stronger notion suggested in [AASY, Comp. Complexity'16; Shaltiel, CCC'25] to make extractors for samplable distributions suitable for selecting keys for cryptographic protocols. Third, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=\mathrm{polylog}(n)$. This result uses hardness for circuits that have oracle access to $\Sigma_2^{\text{P}}$. Prior to this work, the lowest min-entropy threshold $k$ that was achieved using hardness for nondeterministic circuits (or even circuits with oracle access to $\Sigma_2^{\text{P}}$) was larger than $0.99n$ [BGDM, FOCS'23]. Our results significantly improve both the min-entropy threshold and the hardness assumptions compared to all past work that extracts more than one bit. Our constructions build upon earlier work [TV, FOCS'00; BGDM, FOCS'23; BSS, STOC'25; Shaltiel, FOCS'25] while introducing several new ideas: (1) We simplify and build upon the ideas of [BGDM, FOCS'23] to construct our extractors under nondeterministic hardness. (2) We introduce a notion of robust errorless condensers and construct and use them to obtain our multiplicative extractors. (3) We adapt the two-source extractor recipe from [CZ, Ann. of Mathematics'19] to construct our additive extractors. We do this by constructing and using a correlation breaker against small circuits. Our correlation breaker extends recent constructions of non-malleable extractors against small circuits [BDL, CRYPTO'22; BD, CRYPTO'25].

Given a joint distribution $P_{XY}$ of random variables $X,Y$ on finite alphabets, the information bottleneck method seeks a representation $T$ of $X$ that is as informative as possible about $Y$ while compressing $X$; the privacy funnel asks for a representation that discloses much about $X$ while leaking little about $Y$. In both scenarios $T$ and $Y$ are conditionally independent given $X$. We show that computing the optimal value $IB(P_{XY},R) = \sup_T \{ I(Y;T) : I(X;T) \le R \}$ of the information bottleneck problem, as well as its Lagrangian relaxation $L_\beta(P_{XY}) = \sup_T [ I(Y;T) - \beta I(X;T) ]$, is NP-hard. Moreover, unless $\mathrm{P} = \mathrm{NP}$, neither $IB(P_{XY},R)$ nor $L_\beta(P_{XY})$ can be approximated in polynomial time within an additive error of order $|\mathcal{X}|^{-(1+\alpha)}$, for every fixed $\alpha > 0$. We also prove that computing the privacy funnel $PF(P_{XY},r) = \inf_T \{ I(Y;T) : I(X;T) \ge r \}$ and its Lagrangian relaxation $\Lambda_\beta(P_{XY}) = \inf_T [ I(Y;T) - \beta I(X;T) ]$ is NP-hard, and that, unless $\mathrm{P} = \mathrm{NP}$, neither can be approximated in polynomial time within an additive error of order $|\mathcal{X}|^{-2}$.

We construct an explicit family of total sign matrices whose sign-rank is exponentially larger than their margin complexity. Previously, no superpolynomial separation was known for total matrices. In particular, we give a quantitative answer to a question of Linial, Mendelson, Schechtman, and Shraibman (Combinatorica, 2007), who asked whether the logarithmic dependence on matrix size in the Johnson--Lindenstrauss upper bound for sign-rank is necessary. Our result shows that this dependence on matrix size is nearly tight if the dependence on margin complexity is required to remain polynomial. The construction is the OR of Equality tests on a large enough alphabet. This also exponentially improves sign-rank lower bounds for sparse disjointness and Hamming-distance thresholds. The proof uses a new one-sided version of Forster's spectral bound for sparse matrices that gives exponentially stronger lower bounds than previous lower bounds. Using the same method, we also obtain direct-sum theorems for unbounded-error communication complexity for OR compositions of expanders and set-membership tests.

In Hrubeš' Algebraic Monotone Calculus AMC a DNF tautology $A$ is proved by a monotone arithmetic circuit computing $\chi(A)-\epsilon\cdot\chi(1)$ for some $\epsilon>0$, where $\chi(A)$ is the set-multilinear polynomial whose coefficient at $\mathbf x^{\sigma}$ counts the terms of $A$ satisfied by $\sigma$, and $\chi(1)=\prod_{i\le n}(x_i^0+x_i^1)$. Proof size is circuit size, and $\epsilon$ is existentially quantified, so a lower bound must hold at arbitrarily small $\epsilon$. We prove such bounds for bounded-depth fragments by two nonnegative rank measures of $\chi(A)-\epsilon\cdot\chi(1)$: its monotone tensor rank, and the nonnegative rank of a flattening of its coefficient tensor. At depth three, a proof decomposes the coefficient tensor into nonnegative rank-one tensors. Restricting the summands to nonnegative multiples of subcube indicator tensors yields conical juntas and a system polynomially equivalent to Sherali–Adams when size counts conjunctions over the twin variables $x_i,\bar x_i$. For arbitrary nonnegative rank-one summands, we adapt Rothvoß' hyperplane separation method to monotone tensor rank and prove that Tseitin formulas on constant-degree expanders of sufficiently large girth require proofs of size $2^{\Omega(\epsilon n)}$ for $\epsilon\in(0,1]$ with $\epsilon=\omega(\log n/n)$. This cannot reach every $\epsilon>0$: at shift $2^{-\Theta(n\log n)}$ Tseitin acquires polynomial-size depth-three proofs, which separates the general depth-three fragment from the subcube one exponentially. We compose Tseitin formulas with a constant-size index gadget to obtain lower bounds for every $\epsilon\ge2^{-\Omega(n)}$, converting a Sherali–Adams *degree* bound into a depth-three *size* bound. Depth three is essential to all of this: we also show that Tseitin has monotone proofs of size $O(n^3)$ and depth $O(\log n)$ at *every* $\epsilon\in(0,1]$. Beyond depth three, we bound the nonnegative rank of a flattening by $L^{2^t}$ for a monotone formula with $L$ leaves and *mixed-product depth* $t$. Here $t$ is the maximum number, along a root-to-leaf path, of product gates whose two inputs each involve both sides of the bipartition; the Tseitin proofs just mentioned have $t=0$ for every bipartition, so this bound is empty for Tseitin. We give two constructions turning hard matrices into hard DNFs. Approximate extension complexity yields bounds for perfect matching and odd factor instances. Linear programming integrality gaps for planted constraint satisfaction yield an explicit family of planted Tseitin DNFs hard at inverse-polynomial shift.

For infinitely many rates $R \in (0,1)$, we show that full-length Reed-Solomon codes over fields of low characteristic can contain super-polynomially many codewords in a Hamming ball of radius just exceeding the Johnson radius. Over prime fields, we exhibit full-length Reed-Solomon codes of constant rate $R$ with polynomially many codewords in a Hamming ball of relative radius bounded strictly below $1-R$. This refutes a recent conjecture that, over prime fields, list sizes below capacity are always bounded by a constant. Together, these results demonstrate that certain restrictions in recent works on explicit Reed-Solomon codes achieving list-decoding capacity, related to the choice of field or evaluation points or to the list-size guarantee, are inherent.

A quadratic source is a random variable $X\sim\mathbb{F}_2^n$ generated by applying $n$ quadratics to a hidden uniform string. Previously, the best-known explicit extractor for this model required min-entropy roughly $k=n-\sqrt{\log n}$. In this paper, we give an explicit construction for min-entropy $k=\mathrm{polylog}(n)$. Even for the special case of $2$-local sources, where each bit of $X$ depends on two hidden uniform bits, achieving an entropy requirement below $k=\sqrt{n}$ was an important open problem. This is because such sources provably cannot be reduced (in a black-box manner) to our most powerful general-purpose seedless extractor, known as a sumset extractor. Our new extractor bypasses this barrier, providing the first explicit construction to go beyond sumset extraction.

Authors: Karthik Sheshadri

The best known lower bound on the determinantal complexity of the 4x4 permanent is 10. In this short note, I prove that this value is exactly 15: the 4x4 permanent is the determinant of a 15x15 matrix of affine linear forms, and cannot be that of any smaller matrix. To do so, I must establish both a lower and upper bound. To establish the upper bound, I use Grenet's construction of size 2^n-1. Hence that construction is optimal at n=4 (and n=3). This now constitutes the first knwon exact value of the determinantal complexity of the permanent at n=4. Only the value at n=3 was exactly known, prior to this note. The general quadratic bound only gives 8 for n=4. To establish the lower bound, I work from a normal form at a zero of the permanent. In the first row (and column) of the normal form, the linear forms vanish on a linear space inside the singular locus of the permanent. A hessian inequality bounds the size of the matrix in terms of that space. Then, a matrix of sie 14 foces the space into any of nine corordinate types. The forcing is either up to symmetry, or else into a family that degenerates to one of them. I then rule out every case. All involved computations are exact. In respect of the claim, I have made all certificates public.

Authors: Julian Dörfler, Alexander Rogovskyy

It is well known that $\mathsf{VF} = \mathsf{VBP}_{3}$ (Ben-Or-Cleve'92), i.e. the width of any constant-width algebraic branching program can be reduced to width $3$ with only a polynomial overhead to size. We prove that this is not the case for the monotone equivalents. In particular, we prove that there is an infinite hierarchy $\mathsf{mVBP}_{2} \subsetneq \mathsf{mVBP}_{3} \subsetneq \ldots$ by showing that $\mathrm{imm}_{k,n}$ requires width $w$ mABPs to have depth at least $\left(\frac{k}{w-1}\right)^{\frac{1}{2}\left\lfloor n^{\frac{1}{(w-2)}} \right\rfloor - 1}$ whenever $3 \leq w < k$. We prove this lower bound using support-based techniques. Since this lower bound is exact instead of asymptotic, it allows some width separations even for superconstant width. Moreover, it allows us to show that the expressive power of poly-sized monotone formulas of depth $2d$ is not reached by poly-sized mABPs of width $d-1$ but a width of $2d+1$ is sufficient. We contrast this to unbounded-depth monotone formulas, which are proven to be stronger than constant-width mABPs, but weaker than $\log$-width mABPs and incomparable for most widths in between. Finally, we generalize Snir's framework (Snir'80) for showing lower bounds on the number of leaves of monotone formulas to monotone formulas of multiplication depth $d^{\times}$, giving a lower bound of $n \cdot k^{d^{\times}(n^{\frac{1}{d^{\times}}} - 1)}$ for the iterated matrix multiplication polynomial and $\left(\left(e+o(1)\right) \ln^{\circ(d^{\times}-1)}(n)\right)^n$ for the permanent.

Authors: Qian Liu, Shinuo Ma, Yixin Tao, Minji Yang, Weiqiang Zheng

The competitive equilibrium (CE) is a fundamental concept for markets, with applications to efficient and fair allocation of resources. We consider the fundamental question of computing a CE in the most basic Fisher market model where agents have linear preferences. While it is known that we can compute a CE in strongly polynomial time with linear goods, there is no known polynomial-time algorithm for CE with linear chores. Computing a CE for linear chores is known to be in CLS with no hardness results. In this paper, we prove that computing an exact CE in Fisher markets with divisible chores and linear disutilities is CLS-hard and thus CLS-complete. To the best of our knowledge, this is the first CLS-completeness result for a market equilibrium problem. On the technical side, we use the nonconvex dual Eisenberg-Gale (EG) program whose Karush-Kuhn-Tucker (KKT) points are CE [Chaudhury, Kroer, Mehta, and Nan, 2024], and the CLS-complete problem of computing a KKT point of a quadratic program [Fearnley, Goldberg, Hollender, and Savani, 2024]. We show that from any exact equilibrium of the constructed market, we can recover in polynomial time an $\varepsilon$-KKT point of the input quadratic program over the unit box.

Authors: Thanin Quartz, Ivan O. Shevchenko, Hans De Sterck, Jun Liu

The matrix mortality problem asks whether a given finite family of matrices can be multiplied, in any order and with possible repetition, to get the zero matrix. It is one of the most basic decision problems about matrix products, and it arises naturally in the study of switched linear systems and of finite automata. Mortality is trivially decidable in dimension one and has been known to be undecidable for integer matrices in dimensions three and higher since 1970; only the problem in dimension $2$ is left open. We resolve this problem by proving that mortality is undecidable for families of 5,799 distinct $2\times2$ integer matrices. All but one of the matrices are fixed and nonsingular, with determinants $\pm p$ for a single fixed prime $p$. The input affects only the remaining rank-one matrix, which encodes this input into its kernel. Our proof encodes the computation of a fixed universal machine into products of $2\times2$ matrices. We represent each configuration of the computation by a single rational number, which we identify with a line through the origin in $\mathbb{Q}^2$, and each nonsingular matrix carries out a small piece of one computation step. The main difficulty is that the matrices may be multiplied in any order, so we design them to check their own work: a "wrong'' step puts a factor of a prime number $p$ into the denominator of the rational number corresponding to the current computation step, where no later matrix can remove it. As a result, products of these matrices can go from one encoded configuration to another only by following a valid computation. The rank-one matrix then turns the question of whether the machine halts into the question of whether some product equals zero. A companion formalization in the Lean proof assistant verifies the complete reduction.

Authors: Manaswi Paraashar, Nitin Saurabh

We establish upper bounds on the Shannon entropy $\mathbb H(\widehat f^{\,2})$ of the Fourier distribution of Boolean functions. We prove that $$ \mathbb H(\widehat f^{\,2}) =O\!\left(\log\bigl(1+\|\widehat f\|_{1,1/3}\bigr)\right), $$ where $\|\widehat f\|_{1,1/3}$ denotes the minimum spectral norm of a pointwise $1/3$-approximant to $f$. This implies $\mathbb H(\widehat f^{\,2})=O(\mathsf R^\oplus(f))$, where $\mathsf R^\oplus(f)$ is bounded-error randomized parity-query complexity. We also bound Fourier entropy by the smaller of the two one-sided average unambiguous parity-certificate complexities. More generally, for any exact representation of indicator of $f$ as $\sum_C w_C\mathbf1_C$, with nonnegative weights and affine subspaces $C$, we prove $$ \mathbb H(\widehat f^{\,2}) =O\!\left(\sum_C w_C\,2^{-k_C}k_C\right), \qquad k_C=\operatorname{codim}(C). $$ The quantity on the right is the average conical junta degree of the representation. These results strengthen earlier bounds of (Arunachalam et al. 2021) by extending approximation-based entropy estimates to Shannon entropy and allowing one-sided and overlapping exact representations. The proofs use an entropy bound from a sequence of increasingly accurate approximants of $f$ with \emph{small} spectral norm. Our techniques also find an application in quantum communication complexity, where it improves a lower bound for the bounded-error quantum communication complexity of XOR functions.

Authors: Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh

In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantum algorithms can be divided into two classes, QFT based algorithms and search based algorithms. The usual circuit for QFT (covered in almost every basic quantum algorithms course) needs $O(q^2)$ gates (and $O(q)$ qubits) to perform the exact Fourier transform over $\mathbb{F}_{2^q}$. Cleve and Watrous (FOCS 2000) improved this gate count to $O(q (\log q)^2 (\log \log q))$ using the integer multiplication algorithm in $O(n (\log n) (\log \log n))$ time for two $n$-bit integers (best known at that time). Our first main result shows that this gate count can be improved to $O(q (\log q))$. In fact, if there is a multiplication circuit, to multiply two $n$-bit integers, with $O(n (\log n)^α)$ gates; we get a QFT circuit with $O(q (\log q)^α)$ gates (improving upon $O(q (\log q)^{α+ 1})$) gates from the construction of Cleve and Watrous). Given the recent claim by OpenAI about integer multiplication, this opens up the possibility of having a QFT circuit with $o \left( q (\log q)\right)$ gates. On approximating the QFT over $\ZZ/(2^q \ZZ)$, the result of Ahokas, Cleve and Hales (ERATO 2003) showed that an approximating circuit can be built with $O \left( q (\log \log(q/\varepsilon))^{α+1} \right)$ gates, where $ε$ is the approximating parameter. Our second main result again improves this to $O \left( q (\log \log(q/\varepsilon))^α \right)$ gates.

Authors: Sergey Salishev

The halting problem asks whether a program eventually halts, with unrestricted resources. Engineering systems instead certify bounded halting: given a program, an input, and a step budget T, decide whether the program halts within T steps. This paper studies two of its uses. First, it defines an exact finite-budget problem, placing the simulated program and the checker on the same unit-cost timescale, so the checker can be embedded in an adversarial program. A diagonal argument with explicit additive overhead shows that no fixed deterministic checker decides every instance within any fixed fraction of T below one, for large T. In the nondeterministic case, T bounds the branch depth allowed for a stable observable decision. Second, bounded-halting instances give adversarial tests for finitary universality, since a universal model must support arbitrary finite computations as T grows. The tests check resource growth with T, the absence of a fixed deliberation bound, and later access to intermediate data. They separate a fixed model with extendable external resources, a model family that grows with T, and a larger system built around a fixed component. For machine-learning systems, this identifies the resource growth a universality claim assumes and whether it fails for deployed models.

Authors: Nikolai Chukhin

A hyperclique in an $r$-uniform hypergraph is a set of vertices in which every $r$-subset is an edge. A simple exhaustive search algorithm detects a hyperclique on $\ell$ vertices in an $r$-uniform hypergraph on $m$ vertices by checking all $\binom{m}{\ell}$ sets of $\ell$ vertices. This algorithm can be expressed as a depth-two circuit with at most $m^\ell$ gates and wires. For hypercliques of *constant* size, Amano (2010) showed that this circuit is almost optimal: for large $r$, constant-depth circuits need $m^{\ell(1-O(\log r/r))}$ wires. We prove that this circuit remains hard to beat even for hypercliques of *polynomial* size. More precisely, circuits of depth $h$ need $m^{Ω(\ell)}$ gates for $\ell\leq m^{1/h-\varepsilon}$, and $m^{\ell(1-O(\log r/r))}$ gates for $\ell=m^{o(1)}$ that tends to infinity. Our hyperclique bound and the method behind it also lead to lower bounds for two central problems of fine-grained complexity. First, we extend the bound $n^{k/4}$ of Rossman (2008) for $k$-Clique from cliques of *constant* size to cliques of *polynomial* size: circuits of depth $h$ detecting a clique on $k$ vertices in an $n$-vertex graph need $n^{Ω(k)}$ gates for $k\leq n^{1/(h-1)-\varepsilon}$. Second, a reduction of Choudhury, Limaye, Sreenivasaiah, and Srinivasan (2026) turns our hyperclique bound into a lower bound of $n^{k-\varepsilon}$ gates for $k$-Orthogonal Vectors ($k$-OV) at every fixed depth for vectors of dimension $\log^{O(1)} n$; this proves the $k$-OV Conjecture for constant-depth circuits in polylogarithmic dimension. Finally, for $2$-OV in logarithmic dimension, we give a simple proof that depth-three circuits need $Ω(n^2)$ wires, which answers a question of Kane and Williams (2019).

Authors: Aryan Agarwala, Dani Dorfman

We initiate the study of middle-bit predictors: functions that take as input a string with one missing bit and try to predict that bit. These are closely related to next-bit predictors, a classical object in pseudorandomness. We study the deterministic complexity of computing an unpredictable distribution (UNPRED). Given a list of middle-bit predictors in circuit form and a parameter $ε>0$, output a multiset of strings such that each predictor succeeds with probability less than $1/2+ε$ on a uniformly sampled string from the multiset. We write $\mathsf{UNPRED}^{\mathsf{TC}^1}$ for the restriction to $\mathsf{TC}^1$ predictors. We show that UNPRED offers a unified route towards resolving several major open problems in catalytic computation, the biggest of which is whether deterministic polynomial time (P and FP) can simulate catalytic logspace (CL and SearchCL). It is believed that $\mathsf{SearchCL}\subseteq\mathsf{FP}$. We prove $$\mathsf{UNPRED}\in\mathsf{FP}\implies\mathsf{SearchCL}\subseteq\mathsf{FP}\implies\mathsf{UNPRED}^{\mathsf{TC}^1}\in\mathsf{FP}.$$ Thus, the questions of whether UNPRED is in FP and whether SearchCL is contained in FP are almost equivalent, up to the restriction to $\mathsf{TC}^1$ circuits. We also show that any deterministic polynomial-time algorithm for $\mathsf{UNPRED}^{\mathsf{TC}^1}$ must exploit properties of $\mathsf{TC}^1$ circuits, either in the algorithm itself or in its analysis. To our knowledge, this would also be the first algorithm to use the structure of $\mathsf{TC}^1$ circuits in this way to solve a natural problem, thus advancing our understanding of Boolean circuits. Together, our results provide strong evidence that middle-bit predictors could be the key to unlocking several major open problems in catalytic computation, pseudorandomness, and Boolean circuit complexity.

Authors: Yanghao Liu, Fangda Guo, Yuxuan Zhang, Xueqi Cheng

We study community search when each vertex has its own tolerance for differences in position. For positions such as opinions or homes, a latitude-consistent community (LCC) contains the query vertex, is connected, has minimum degree at least k, and bounds its diameter by the smallest member tolerance. Motivated by social judgment theory, the bound exactly characterizes persistent acceptance of every interaction in a closed group under bounded-confidence dynamics with arbitrary positive weights. It also prevents rejection under social-judgment dynamics, whereas natural relaxations preserve neither guarantee. Finding a maximum LCC is NP-hard even in the plane, and with unbounded dimension, deciding whether an LCC exists is NP-complete for every fixed k >= 2. LatSweep turns the coupled bound into a sweep over the smallest tolerance, yielding two feasible heuristics, a (1,2)-bicriteria approximation and an exact branch-and-bound algorithm. Across eight graphs with up to 1.8 billion edges, the exact algorithm proves optimality on all but 9 of 3,700 efficiency queries and usually certifies absence within microseconds when no LCC exists. Its branch-and-bound solver proves more queries than a reimplemented maximum-(k,r)-core algorithm, a mixed-integer program and CP-SAT. In simulations, uneven influence disrupts initially accepted interactions in pairwise groups. Outside ties invalidate the guarantee for many real groups. On two location-based networks, tolerance-agnostic groups often place another member's home beyond a member's estimated travel radius; comparisons with spatial communities of the same size detect no co-visit loss from enforcing every member's tolerance.

Authors: Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux

We study the minimum number of clauses required to encode a boolean function into a CNF formula with auxiliary variables. Our main result is that if a boolean function can be evaluated in nondeterministic time $t$ (in the RAM model) with $m$ bits of advice such that at most $b$ bits of advice are accessed for each input, then it admits a CNF encoding with $\widetilde{O}(t + \sqrt{mb})$ clauses. This constitutes a nonuniform generalization of Robson's (TCS'91) variant of the Cook--Levin theorem, for which a naïve generalization would yield $\widetilde{O}(t+m)$ clauses; our applications leverage $b = o(m)$ to obtain significantly better bounds. Since preprocessed data structures can be modeled as computation with advice, our result allows us to translate space- and time-efficient data structures to compact CNF encodings. As an application, we derandomize a data structure of Larsen and Williams (SODA'17) to show that every $k$-CNF function on $n$ inputs can be encoded with $n^k/2^{Ω_k(\sqrt{\lg n})}$ clauses. Notably, despite encoding a $k$-CNF function, the encoding itself necessarily contains clauses of unbounded width, since an information-theoretic argument shows that the minimum number of bounded-width clauses to encode such functions is $Ω_k(n^{k}/\lg n)$ in the worst case. In general terms, our results imply that for a wide variety of NP-complete problems, one can reduce to CNF-SAT in a way that results in asymptotically fewer clauses than previously known methods.

Authors: Guangjian Zhang

We prove Conjecture 4 of Chan, Chang, Gao, Kisfaludi-Bak, Le, and Zheng (SoCG 2026): for every fixed integer $r\ge0$, the radius-$r$ neighbourhoods of a unit-cube graph in $\mathbb{R}^3$ have bounded VC-dimension. Our bound is $2^{2^{O(r)}}$, independent of the number of vertices. The main ingredient is a VC-dimension bound for reachability through arbitrary fixed-length sequences of three-dimensional generalized dominance relations. Its proof uses groups ordered in two coordinates, with neighbouring groups acting as barriers that preserve this invariant when one layer is removed. Combining these bounds with the existing interval-representation framework, we obtain a Las Vegas algorithm that, for every fixed integer $Δ\ge1$, decides whether a graph given by $n$ cube centres has diameter at most $Δ$ in expected $O_Δ(n^{2-\varepsilon_Δ})$ time, for an explicit constant $\varepsilon_Δ>0$. Finally, for every integer $r\ge7$, we construct unit-cube graphs with rational centres whose radius-$r$ neighbourhoods have VC-dimension $Ω(r^3)$.

Authors: Julián Uribe Castañeda, Mircea Petrache

Persistence diagrams do not naturally live in a Hilbert space. Carrière, Cuturi, and Oudot embedded them in kernel methods through the Sliced Wasserstein kernel, built from the Sliced Wasserstein distance $\mathrm{SW}_1$, which is conditionally negative definite (CND). We study the projected ($\mathrm{SW}_p$) and reflected ($\mathrm{RW}_p$) Sliced Wasserstein distances for every order $p\ge1$, and compare them with the $p$-Wasserstein distance $d_p$ and with a reflected variant $d_p^r$, in which projection onto the diagonal is replaced by reflection across it. We show that $2^{1/p}d_p\le d_p^r\le 2d_p$ with sharp constants, so that $d_1^r=2d_1$ and $d_p^r$ inherits the stability of $d_p$, although it is a metric only for $p=1$. The distances $\mathrm{SW}_1$ and $\mathrm{RW}_1$ are CND metrics, and $\mathrm{RW}_1$ gives rise to a new positive definite kernel, stable with respect to $d_1$. For $p>1$, neither $\mathrm{SW}_p$ nor $\mathrm{RW}_p$ satisfies the triangle inequality, and rigorous interval-arithmetic certificates prove that $\mathrm{SW}_2$ and $\mathrm{RW}_2$ are not CND; numerical experiments suggest that the CND property fails for every $p$ above some $p^*\in(1,1.2]$. On diagrams with at most $N$ points, $\mathrm{SW}_p$ and $\mathrm{RW}_p$ are metrically equivalent to $d_p$ and $d_p^r$, with sharp upper constants. On an orbit recognition benchmark, the kernels built from $\mathrm{SW}_1$ and $\mathrm{RW}_1$ reach about 85% accuracy, outperform the persistence scale space kernel, perform on par with the persistence weighted Gaussian kernel, and are about one percentage point below the kernel built from $\mathrm{SW}_2$, which is not positive definite.

Authors: Otobong Jerome, Tiago Nascimento

The optimal rapidly exploring random tree (RRT*) is proven asymptotically optimal on open subsets of Euclidean space with straight-line local planning. We ask whether it works on a triangle-mesh terrain, a two-dimensional surface in R^3. First, the original RRT* cannot run on a mesh: the surface has zero volume, so uniform sampling never hits it, no clearance ball fits in it, and chords across a fold leave it. Second, the surface reformulation we call Mesh RRT*, with its naive edge, the chord costed by its length, solved every run on heightfields with slopes up to 75 degrees but minimises the wrong objective: its cost, the straight-line length of a polyline whose vertices lie on the surface while its segments may leave it by a tolerance tau, is the length of no route on the surface and lies strictly below the geodesic length on any curved mesh. In numeric simulation and after 30,000 iterations the reported cost is on average up to 2.7% below the exact geodesic, a cost no path attains, and the returned route on average 0.1-0.5% longer than it. Rewiring keeps the biased edges, the bias decays only linearly with the step on polyhedral surfaces, and shrinking tau trades bias for connectivity. Third, replacing each chord by a path on the surface above it, built from projected points joined across the mesh edges they straddle and costed by its own length, makes every edge cost the exact length of a feasible path; with no other change the exact length of the returned routes is on average within 0.07-0.16% of the geodesic at every roughness tested, two to 3.4 times closer than with chords on the rougher terrains. The planner is in MeshNav3D 0.2.0 (release pending).

Authors: Zixuan Huang, Guozhang Chen

Attention is central to modern AI models for language, vision, and scientific modeling. However, direct evaluation compares every query with every key, requiring quadratic time in the context length, which limits its scalability to long contexts. Consequently, characterizing the complexity bounds of attention is of fundamental importance. For every fixed dimension $d$, we give an algorithm for $m$ queries, $n$ key-value pairs, and additive error $\varepsilon$, with expected time $ \widetilde{\mathrm{O}}\bigl((mn)^{k/(k+1)}+m+n\bigr),\qquad k=\lfloor d/2\rfloor. $ For fixed dimension and a fixed number of value channels, soft-O hides factors of the form $\operatorname{poly}_d\bigl(b,\log(m+n),\log B,\log(1/\varepsilon)\bigr),$ where $b$ bounds input encoding lengths and $B$ bounds coordinate and value magnitudes. In particular, the dependence on $B$ and $1/\varepsilon$ is polylogarithmic, which allows arbitrary positive temperature. When $m=n$ and $d\ge2$, the bound is $\widetilde{\mathrm{O}}(n^{2-2/(\lfloor d/2\rfloor+1)})$: near-linear in dimensions two and three, with exponent $4/3$ in dimensions four and five and $3/2$ in dimensions six and seven. It improves the previous $\widetilde{\mathrm{O}}(n^{2-1/d})$ upper bound and matches the best known batch maximum-inner-product bound in each fixed dimension. Additionally, we reduce integer batch maximum inner product computation to one attention call with the same dimension and input sizes $m,n$.

Authors: Huanjian Zhou, Taiji Suzuki

We study the query complexity of sampling from smooth distributions on $\mathbb R^d$ using first-order oracles. For $d$-dimensional strongly log-concave targets with condition number $κ=2$, we prove that any randomized sampler requires $\exp({Ω(\log^{1/3} d)})$ queries even from a constant warm start. This rules out polylogarithmic dimension dependence and strictly separates strongly log-concave sampling from Gaussian sampling. For targets with $L$-smooth potentials satisfying an $α$-log-Sobolev inequality with $κ= L/α$, we prove an $Ω(κ)$ query lower bound for $d\gtrsim\log^2κ$. This shows that log-Sobolev sampling is strictly harder than strongly log-concave sampling. Our proofs construct instance-dependent tests that target samples typically pass but outputs of algorithms making few queries typically fail. For strongly log-concave targets, we embed a sequence of hidden Gaussian into high-degree tensor polynomial with smooth gates, forcing any algorithm to uncover the layers sequentially. The log-Sobolev construction hides a constant fraction of the target mass in angular caps while controlling the log-Sobolev constant via delicate estimates.

Authors: Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick

The Multiway Cut problem is among the most well-studied problems in the area of combinatorial approximation algorithms. The currently best approximation ratio for the problem is 1.2787, obtained recently by the authors (2026). The best lower bound on the approximation ratio that can be achieved for the problem in polynomial time, under the Unique Games Conjecture (UGC), is 1.20016, obtained by Bérczi, Chandrasekaran, Király, and Madan (2020), building on and slightly improving a bound of $\frac65=1.2$, obtained by Angelidakis, Makarychev, and Manurangsi (2017) by introducing the important framework of non-opposite multiway cuts. We obtain a substantially improved lower bound of 1.22232 on the approximation ratio of the Multiway Cut problem. Manokaran, Naor, Raghavendra, and Schwartz (2008) showed that under UGC, the approximation ratio of Multiway Cut is equal to the integrality ratio of a simple LP relaxation, known as the CKR relaxation, introduced by Călinescu, Karloff, and Rabani (2000). Thus, stronger LP relaxations are not required for obtaining an optimal approximation algorithm for the problem. We show, however, that relying on the framework of Angelidakis, Makarychev, and Manurangsi (2017), stronger LP relaxations from the Sherali-Adams hierarchy for non-opposite multiway cuts can be used to obtain improved integrality ratios for the CKR relaxation, and hence improved lower bounds on the approximation ratio of the Multiway Cut problem. One of the novel features of our analysis is considering a continuous limit of discrete LPs defined on a simplex. Our proof of the new 1.22232 bound is completely analytic. We also present strong numerical evidence that suggests that our techniques can be used to improve the lower bound to at least 1.23003.

Authors: Eunjin Oh, Hyeonjun Shin

We develop a unified algorithmic framework for computing approximate minimum spanning trees (MSTs) in metric spaces in the fully scalable Massively Parallel Computation (MPC) model. Using this framework, we obtain the following results for any fixed constant $σ\in(0,1)$: - General metrics: Given all pairwise distances, we compute a $(1+\varepsilon)$-approximate MST in $O(\log(1/\varepsilon))$ rounds using $n^σ$ local space per machine and $\widetilde{O}(n^2)$ total space. - Euclidean spaces: Given $n$ points in $\mathbb{R}^d$, we compute an $O(1/σ^4)$-approximate MST in $O(1)$ rounds using $(nd)^σ$ local space per machine and $O(nd+n^{1+σ})$ total space. - Doubling metrics: Given $n$ points in a metric of doubling dimension $\mathrm{ddim}=O(σ\log n)$, we compute an $O(1/σ)$-approximate MST in $O(\mathrm{ddim}/σ^4)$ rounds using $n^σ$ local space per machine and $\widetilde{O}(n^{1+σ})\cdot 2^{O(\mathrm{ddim})}$ total space. For any fixed constant $\varepsilon\in(0,1)$, these results give the first constant-round MPC algorithms achieving $(1+\varepsilon)$-approximation in general metrics and $O(1)$-approximation in a high-dimensional Euclidean space, respectively. They improve upon the $O(\log\log n+\log(1/\varepsilon))$-round algorithm for general metrics [SODA'25] and the $O(\log\log n\cdot\log\log\log n)$-round algorithm for Euclidean spaces [SODA'24], respectively. Moreover, our round complexity for general metrics is asymptotically optimal in its dependence on $\varepsilon$, matching the $Ω(\log(1/\varepsilon))$ lower bound of [SODA'25] under the 1-vs-2-cycles conjecture. Our result also answers an open question raised by [STOC'23].

Authors: Henry Fleischmann, Sagnik Mukhopadhyay, Swagato Sanyal

We study $s$--$t$ reachability in an unweighted directed graph on $n$ vertices, accessed through a directed cut oracle: given $S\subseteq V$, the oracle returns the number of edges directed from $S$ to $V\setminus S$. Directed cut functions are submodular, and reachability asks whether the minimum $s$--$t$ cut has positive value. This connects the problem to the query complexity of submodular function minimisation. Whether or not reachability can be solved in truly subquadratic query complexity has been an outstanding open question for a decade. We give a simple algorithmic blueprint with two randomised implementations. The first uses $\widetilde O(n^{9/5})$ outgoing-cut queries; the second improves this bound to $\widetilde O(n^{5/3})$. The common idea is to construct an alternative orientation with the same underlying undirected graph and vertex-wise degree imbalances, thereby preserving reachability. We first approximate the target imbalances using an averaging and rounding procedure, then correct the remaining error with a flow. An earlier manuscript, made available in August 2026 in an online AI repository, reports an $\widetilde O(n^{3/2})$ query bound. Our contribution is a simple and comprehensible alternative approach that already achieves a polynomial saving over quadratic query complexity.

Authors: Alireza Farhadi, Mohammad Hajiaghayi

We give a $0.556195$-competitive randomized algorithm for edge-weighted online bipartite matching with free disposal, improving the $0.5368$ guarantee of Blanc and Charikar. The result holds for arbitrary nonnegative edge weights and any input sequence fixed independently of the algorithm's randomness. Our algorithm builds on online correlated selection, introduced by Fahrbach, Huang, Tao, and Zadimoghaddam, and its multiway extension due to Blanc and Charikar. Our main contribution is a state-dependent primal--dual analysis of correlated selection. At each weight threshold, we track the state of the selection process jointly with an auxiliary failure event. The analysis accounts for arrivals below the threshold, which change the state without improving the matching value at that threshold. A potential function bounds the dual increase in both cases. We instantiate the analysis with an explicit win map that assigns a common score to an initial range of states. Its selection inequalities are verified by a finite computer-assisted proof covering every required candidate multiplicity and every real threshold; the verifiers are available in an accompanying repository. Triangular unit-weight inputs asymptotically attain the guarantee of the underlying ideal algorithm, proving that its analysis is tight.

Authors: Iman Gholami, MohammadTaghi Hajiaghayi

In nonuniform buy-at-bulk network design, we are given an undirected graph and $h$ terminal pairs with positive demands, and we must route every demand at minimum total cost when each network resource has two independent parameters: a fixed buying price paid once if the resource is used, and a per-unit rental cost (or physical length) paid proportionally to the traffic it carries. Unlike the uniform-cost or single-sink variants, the general multicommodity problem allows unrelated buying and rental metrics across arbitrary source--sink pairs, arbitrary demands, and both edge and node resources. We give a deterministic polynomial-time $O(\log^2 h / (\log\log h)^2)$-approximation algorithm for undirected nonuniform buy-at-bulk network design. The guarantee holds for edge costs, node costs, and their combination, and applies to arbitrary positive rational demands with no dependence on the number of vertices or the numerical demand ratio. This improves upon the $O(\log^4 h)$ bound of Chekuri, Hajiaghayi, Kortsarz, and Salavatipour (2010) for unrestricted instances. Our result also establishes the same $O(\log^2 h / (\log\log h)^2)$ upper bound on the integrality gap of the natural affine multicommodity flow LP, bounding integral buying and rental costs separately against their fractional counterparts and preserving zero rental budgets exactly.

Authors: Hossein Esfandiari, MohammadTaghi Hajiaghayi

The matroid prophet-secretary problem asks an online algorithm to select an independent set of elements whose nonnegative values are drawn independently and revealed in uniformly random order. Its combinatorial-auction counterpart asks the algorithm to allocate disjoint bundles to arriving buyers with independently drawn XOS valuation functions. In both problems the distributions are known, and the benchmark is the expected offline optimum. Ehsani, Hajiaghayi, Kesselheim, and Singla (SODA 2018) give $(1-1/e)$-competitive algorithms for both settings. In this work we show that these two guarantees have different limits. For every matroid, we give a randomized $(1-1/e+\varepsilon_0)$-competitive algorithm, where $\varepsilon_0=10^{-6}$. The guarantee holds for independent nonnegative values with finite expected optimum. For explicitly given finite distributions with rational values and probabilities, the algorithm has polynomial worst-case running time in the matroid independence-oracle model. The oracle tests whether a queried set is independent. The algorithm makes $O(N^4)$ such queries in expectation and $O(N^4\log(N+2))$ in the worst case, where $N$ is the number of elements. For combinatorial auctions with XOS valuations, however, we show that $1-1/e$ is the optimal competitive ratio. We give an explicit family of finite instances showing that no online algorithm can guarantee a larger competitive ratio than $1-1/e$, even when the buyers' valuations are independent and identically distributed, every additive clause has coefficients in $\{0,1\}$, and computation is unrestricted. Thus the matroid improvement exploits structure absent from general allocation with XOS valuations.

Authors: Merav Parter, Elad Tzalik

A fault-tolerant (FT) connectivity oracle for an $n$-vertex graph $G=(V,E)$ determines whether $G- F$ is connected for any query set $F\subseteq E$. When the number of failures is unrestricted, prior constructions exhibited a sharp contrast between randomization and determinism: randomized oracles use only $\widetilde{O}(n)$ space [Duan and Pettie, SICOMP 2020], whereas no deterministic construction was known to improve upon storing $G$ explicitly, requiring $Θ(n^2)$ bits in the worst case. The promise that $F\subseteq E$ is essential for subquadratic space: allowing arbitrary queries $F\subseteq V\times V$ forces quadratic space. For queries containing at most $f$ failures, Khanna, Konrad, and Putterman [SODA 2027] recently constructed deterministic oracles using $\widetilde{O}(\sqrt{f}n)$ space that also report approximate distances with polylogarithmic stretch. Their result improves upon the classical $O(fn)$ space bound for deterministic connectivity oracles [Pătraşcu and Thorup, FOCS 2007], but offers no space savings over storing $G$ when $f=Θ(n^2)$. We present the first deterministic connectivity oracles with subquadratic space for failure sets of unrestricted size, using $\widetilde{O}(n^{7/4})$ space. We also establish the first polynomial separation between deterministic and randomized connectivity oracles, proving that every deterministic oracle requires $\widetildeΩ(n^{3/2})$ bits in the worst case. For queries containing at most $f$ failures, we obtain deterministic connectivity oracles using $\widetilde{O}(f^{2/5}n)$ space, improving the dependence on $f$ in the bound of Khanna et al., and prove a lower bound of $\widetildeΩ(f^{1/4}n)$ bits.

Authors: Timothy M. Chan, Reina Itakura, Zhiyuan Ma, Yuancheng Yu

We present truly subquartic algorithms for detecting or counting 4-hypercliques in a 3-uniform hypergraph with $n$ vertices, disproving a popular hypothesis in fine-grained complexity. The result immediately implies a faster algorithm for finding a $k$-hyperclique in a 3-uniform hypergraph for all constant $k\ge 4$, and a faster exponential-time algorithm for Max-3-SAT.

Authors: Jan Dreier, Nikolas Mählmann, Michał Pilipczuk, Szymon Toruńczyk

A graph class $\mathcal{C}$ is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from $\mathcal{C}$ using a fixed formula of first-order logic. We prove that every monadically dependent graph class has almost bounded merge-width, thereby confirming a conjecture of the first and the last author [STOC '25]. Our proof is algorithmic and the witnessing decompositions in the form of merge sequences can be computed in nearly-cubic time. This is a step towards the proof of fixed-parameter tractability of model checking first-order logic on monadically dependent graph classes, which is achieved in a companion paper.

Authors: Hadas Barabash, Jim Geelen, Rose McCarty, Caleb McFarland, Paul Wollan

We give an $O_H(n^5)$-time algorithm to test whether an $n$-vertex labeled tour graph has a full immersion isomorphic to a labeled tour graph $H$. A labeled tour graph is a connected $4$-regular graph whose edges are labeled by binary vectors of fixed length. To obtain a full immersion, a vertex may be removed only by pairing up its four incident edges and "splitting off" both pairs, summing the labels within each pair. Even for one-bit labels, no polynomial-time algorithm was previously known for arbitrary fixed $H$. Our main tool is of independent interest: we give an algorithmic min-max theorem that, in particular, characterizes the maximum number of odd-length circuits in a rooted circuit decomposition of an Eulerian graph. Our results have implications for vertex-minors, whose study is motivated by applications in quantum networking, connections with graph minor theory, and the goal of developing an irrelevant vertex technique for dense graphs. For vertex-minors, circle graphs play the same role as planar graphs do for graph minors. As a corollary of our main theorem, we obtain a fixed-parameter tractable algorithm for apex-vertex-minor testing in $k$-apex circle graphs. We also prove an irrelevant vertex theorem for such graphs of large rank-width. More broadly, our results are essential to forthcoming work of three of the authors proving a structure theorem for graphs with a forbidden vertex-minor. There, our min-max theorem plays the role of both the algorithmic $A$-paths and Two Paths Theorems.

Authors: Antoine Tinguely, G. Wessel van der Heijden

Finnah, Gönsch and Otto [Eur. J. Oper. Res. 2025] recently introduced the Data Validation Problem (DVP): Given a transitive directed acyclic graph $G$ on $n$ vertices (resp. tasks) and $m$ edges (resp. precedences) and a probing budget, a policy can successively pay a probing fee and probe an edge in $G$ as long as the total probing fees do not exceed the budget. If a probe succeeds, the targeted edge $e$ is removed from $G$ and we receive a reward; if the probe fails, the edge stays in $G$ and cannot be probed again. We seek a policy with maximum expected cumulative reward. Crucially, $G$ must stay transitive throughout the probing process, so a policy can only challenge the precedence between consecutive tasks, that is, only probe edges in the transitive reduction of the current precedence graph. We show that DVP is strongly NP-hard and W[1]-hard with the probing budget $T$ as a parameter, even in the deterministic case (when every probe has probability $0$ or $1$ to succeed) and with unit probing costs and rewards. For the same setting, we give an approximation-preserving reduction from the Densest $k$-Subgraph (D$k$S) Problem, with the consequence that there is no polynomial-time $2^{(\log n)^{1-δ}}$-approximation algorithm and no FPT $\sqrt{T}$-approximation algorithm for DVP, assuming the Almost-Exponential Time Hypothesis and the Strongish Planted Clique Hypothesis, respectively. We also present the first known policies with provable worst-case guarantees for DVP, namely an $m$-approximation algorithm for instances with uniform probabilities and probing costs, a $2T/p_{\min}^T$-approximation algorithm for general instances, where $p_{\min}$ is the minimum probing success probability, and an exact FPT algorithm on tournament graphs, in the deterministic setting.

Authors: Arjan Cornelissen, Amin Shiraz Gilani, Xingyu Zhou

Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques. For $N$-vertex graphs given by their adjacency matrices, a long line of work has improved the quantum query upper bound from $O(N^{3/2})$ to $O(N^{5/4})$. However, the best known lower bound has remained the elementary $Ω(N)$ bound obtained from unstructured search. We prove the first superlinear quantum query lower bound for triangle finding, showing that $Ω(N^{13/12})$ queries are necessary. Our result also implies the same lower bound for triangle detection and for detecting every fixed connected non-bipartite graph. The proof builds on the compressed oracle approach of Zhandry and the transfer approaches of Belovs. It compares the computation on graphs with a planted triangle to the computation on random graphs conditioned to be triangle-free, through a map on the input registers that almost commutes with every query. We average over local changes to the input while preserving its distribution, through a procedure known as conditional resampling. Our main technical contribution is a set of estimates that let us control the query error under this averaging, despite the dependence introduced by conditioning a dense graph to be triangle-free.

Authors: Soheil Behnezhad, Shane Ferrante

We study the generalized sorting problem where only a subset of the pairs can be compared. Equivalently, we are given an $n$-vertex $m$-edge graph $G=(V, E)$ where the vertex set $V$ is to be sorted, and the edge set $E$ indicates possible comparisons. The goal is to sort $V$ with as few (adaptive) queries to $E$ as possible. When $G$ is the complete graph, the problem is equivalent to standard sorting for which $Θ(n \log n)$ queries are sufficient and necessary. All classical sorting algorithms crucially rely on the ability to compare any pair and do not imply an $o(n^2)$-query algorithm in the general case. This was improved 15 years ago by Huang, Kannan, and Khanna [FOCS'11] who achieved a bound of $\widetilde{O}(n\sqrt{n})$. Kuszmaul and Narayanan [FOCS'21] later gave a bound of $\widetilde{O}(\sqrt{m n})$, which is more efficient for sparse graphs, but matches the $\widetilde{O}(n\sqrt{n})$ barrier for dense graphs. In this paper, we present an algorithm for generalized sorting that makes at most $\widetilde{O}(n^{4/3})$ queries, therefore breaking the longstanding $\widetilde{O}(n\sqrt{n})$ barrier for all graphs. The key to our result is to query edges that belong to many (specific types of) four-cycles. We show that querying such edges allows the algorithm to verify the direction of many other edges (specifically, their opposing edges in the four-cycles) and thus achieve a much better amortized query cost.

Authors: Piaoyang Cui, Yiming Liu, David P. Woodruff

For over fifty years, combinatorial algorithms for Boolean matrix multiplication (BMM) and triangle detection saved only polylogarithmic factors over cubic time. At STOC 2024, Abboud, Fischer, Kelley, Lovett, and Meka broke this barrier with a deterministic $O(n^3 / 2^{Ω((\log n)^{1/7})})$-time algorithm, and asked whether $n^3 / 2^{Ω(\sqrt{\log n})}$ time is achievable. We answer this question in the affirmative, giving deterministic combinatorial algorithms for both BMM and triangle detection running in $O(n^3 / 2^{Ω(\sqrt{\log n})})$ time. Following Abboud et al., we decompose $(A,B)$ into pairs of submatrices $(A_k,B_k)$, called \emph{pieces}, each of which is either sparse or pseudorandom in a sense that forces $A_k\star B_k$ to be nearly all-ones on its vertex sets. Whereas their decomposition produces $2^{O(d^7)}$ pieces at regularity parameter $d$, we obtain $2^{O(d^2)}$ pieces, directly improving the runtime exponent from $(\log n)^{1/7}$ to $\sqrt{\log n}$. Prior work found pseudorandom pieces by repeatedly restricting to denser submatrices, paying worst-case vertex losses at each step that compounded across nested recursion levels, together with an expensive derandomization step. We eliminate the extra powers of $d$ by matching the vertex loss at each step to the size of its density jump so losses telescope across scales, derandomizing witness search via $L_d$-norm estimation so the sampler length stays $2^{O(d)}$, and bounding overlap across the recursion with a fractional density-weighted volume budget rather than raw submatrix volume.

Authors: Christian Coester, Yichen Huang, Tze-Yang Poon

The online $k$-taxi problem is a natural generalization of the $k$-server problem: $k$ taxis must serve a sequence of requests in a metric space. Each request is a pair of points $(r,s)$, and the algorithm serves the request by first moving a taxi to $r$ (to pick up a passenger) and then to $s$ (to drop off the passenger). The cost is the total distance traveled by the taxis without a passenger. Previous bounds for general $k$ all depended on the number of points $n$ or the aspect ratio $Δ$ of the metric space, both of which can be infinite on general metrics, and competitive algorithms were previously known on general metrics only for $k \le 3$. In this work, we give a $9^{k-1}$-competitive randomized algorithm against adaptive online adversaries and, as a corollary, an $81^{k-1}$-competitive deterministic algorithm for the online $k$-taxi problem.

Authors: Marek Eliáš, Gautam Kamath, Janardhan Kulkarni, George Z. Li, Jingcheng Liu, Sepideh Mahabadi, Pan Peng, Jakub Tarnawski, Hangyu Xu, Zongrui Zou

We give a polynomial-time $(\varepsilon, δ)$-edge-differentially private algorithm that releases a synthetic graph approximately preserving all cut values of a nonnegative weighted input graph $G$. Our algorithm outputs a nonnegative weighted graph $H$ such that, with probability at least $1-β$, simultaneously for all $S\subseteq V$, \[ \left|w_G(S,V\setminus S)-w_H(S,V\setminus S)\right| \leq γw_G(S,V\setminus S) + O\left(\frac{n}{γ\varepsilon} \log^7 \frac{n}{δβγ\varepsilon}\right). \] For fixed $γ, \varepsilon$ and $δ= β= n^{-10}$, the additive error is $n \operatorname{polylog} n$, improving upon the previous efficient bound of $n^{13/12 + o(1)}$. Furthermore, we establish an $Ω(n/γ\varepsilon)$ lower bound for the relevant parameter regime, showing that our result is tight up to polylogarithmic factors. Our algorithm uses a log-det-regularized SDP to generate fractional queries for multiplicative-weights updates and certify accuracy for all cuts. The privacy analysis charges privacy loss only fractionally per mechanism call, based on the amount of mass on edge coordinates retired from subsequent iterations. Our synthetic graph release yields improved error bounds for several downstream tasks in private graph analysis including correlation clustering, Max-Cut, Max-$k$-Cut, constrained cut problems and hierarchical clustering. Most notably, for unweighted complete-graph correlation clustering, we achieve the optimal $\widetilde O(n)$ additive error while reducing the best previously known approximation ratio for this additive error from several thousand to $1.387$. We also provide a formalization of our results in Lean.

Authors: Jingcheng Liu, Yitong Yin

We give randomized algorithms for approximately counting and nearly uniformly sampling independent sets in arbitrary bipartite graphs (#BIS). At fixed accuracy, both algorithms run in $\exp(O(n^{1/3}\log^{4/3}n))$ time on $n$-vertex graphs. More generally, the same running-time dependence on the number of variables holds for approximate counting and sampling with efficiently evaluable positive log-supermodular weights on Boolean variables. A weighted Sinclair-Jerrum walk on the self-reduction tree reduces these tasks to coarse lower estimates of residual log-partition functions. We obtain these estimates by optimizing a concave relaxation of an exact variational principle on the tree; threshold smoothing certifies that the low-degree search suffices.

Authors: Sanjeev Khanna, Aaron Putterman, Madhu Sudan

How much information about a graph is needed to determine its connectivity after arbitrary valid edge deletions? This question is at the heart of designing deterministic dynamic streaming algorithms for graph connectivity. Towards answering this question, we study the deterministic one-way communication problem in which Alice holds a graph $G_A = (V, E_A)$ on $n$ vertices, Bob holds a graph $G_B = (V, E_B)$ with $E_B \subseteq E_A$, and Alice sends a message $M \in \{0,1\}^m$ that allows Bob to decide whether $G_A - G_B$ is connected. Randomized sketches solve this problem using $\tilde O(n)$ bits, whereas deterministic recovery of even one surviving edge requires $Ω(n^2)$ bits. We prove an upper bound of $m = \widetilde{O}(n^{7/4})$ bits and a lower bound of $m = \widetildeΩ(n^{3/2})$ bits for deciding connectivity. Thus, connectivity admits a subquadratic deterministic representation despite the quadratic cost of edge recovery, but remains polynomially harder than its randomized counterpart. The upper bound immediately yields an $\widetilde{O}(n^{7/4})$-bit deterministic $n^2$-fault tolerant connectivity oracle, which reports the connected components of a graph $G$ after any valid set of edge deletions. We also obtain an $\tilde Ω(n f^{1/4})$-bit lower bound for deterministic $f$-fault tolerant connectivity oracles for every $f \in [1,n^2]$. Finally, we show that the separation between connectivity and edge recovery persists in deterministic single-pass dynamic streams with bounded update multiplicity. For every fixed $ε\in (0,1/3)$, our algorithm reports the connected components of the final simple graph using $\widetilde{O}(n^{15/8 + 3ε/8})$ bits (subquadratic space), provided each edge undergoes at most $n^ε$ insertion or deletion updates in total.

Authors: Renaud Gaucher, Ephraim Linder, Adam Smith, Jonathan Ullman, Lydia Zakynthinou

We study the limits of differentially private Gaussian mean estimation when the covariance matrix is unknown. Prior work shows that when the covariance $Σ$ is known, the optimal sample complexity can depend only on its spectrum, rather than on the ambient dimension $d$. We establish new lower bounds for Gaussian mean estimation with Euclidean error which show that private estimators cannot achieve similar guarantees when the covariance is unknown. First, when the sample size $n$ is smaller than the effective dimension $\mathrm{trace}(Σ)/\|Σ\|_{\text{op}}$, the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of $\sqrt{d/n}$. Second, when the sample size is larger than the effective dimension, even for diagonal covariance matrices with effective dimension bounded by $\log d$, the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of $\sqrt{d}/n^{3/2}$. Together, these results show that in the unknown covariance setting, exploiting anisotropic structure under differential privacy can require a dimension-dependent error or sample complexity.

Authors: Mohsen Ghaffari, Sijin Peng

We give a dynamic algorithm that maintains a near-optimal edge coloring in constant expected time per update. For every fixed $ε>0$, the algorithm maintains a $(1+ε)Δ$ edge coloring under edge insertions and deletions in $\mathrm{poly}(1/ε)$ worst-case expected update time against an oblivious adversary, provided $Δ\geΔ_ε=\widetildeΘ(1/ε^2)$. The previous constant-time algorithm of Bhattacharya, Costa, Panski, and Solomon (BCPS) required $Δ\ge(\log n/ε^4)^{Θ(\log(1/ε)/ε)}$, where $n$ is the number of vertices. We remove this dependence on $n$, answering their open question. Our approach differs substantially from that of BCPS, which relied on coloring in locally tree-like subgraphs. Instead, we draw on distributed algorithms that organize partial coloring through successive applications of the Lovász Local Lemma (LLL). We develop a dynamic LLL solver with worst-case expected update bounds and a dynamic splitting algorithm that partitions edges into low-degree subgraphs. A key technical contribution is a bottom-up method for iterative splitting, which avoids the logarithmic overhead of maintaining successive levels. It achieves constant expected update time by adaptively choosing which levels to inspect and repair, rather than inspecting every level after each update. We believe these dynamic splitting and LLL tools can be of interest beyond edge coloring.

Authors: Ken-ichi Kawarabayashi, Hikaru Wada, Masataka Yoneda

We study the problem of determining the maximum number of stable matchings. This classical counting problem was posed by Knuth and has been studied for five decades. We obtain a new $2.999^n$ upper bound on the number of stable matchings with $n$ men and $n$ women. This improves the best-known previous result by Palmer and Pálvölgyi. This result gets much closer to the well-known lower bound $\frac{2.28^n}{\text{poly}(n)}$. We refine their entropy-based framework by capturing broader structural relationships among stable matchings. To capture these relationships, we introduce new frameworks, including cones and supports. This establishes the $3.332^n$ bound. We also exploit relationships among local structures and use a charging argument to improve the bound to $2.999^n$.

Authors: Ebrahim Ghorbani, Matthias Mnich

We study the maximum number ${\rm SM}(n)$ of stable matchings in an instance with $n$ men and $n$ women. Karlin, Oveis Gharan, and Weber (STOC 2018) proved the first single-exponential upper bound; their argument gives ${\rm SM}(n)\le 2^{17n}$ for sufficiently large $n$. Palmer and Pálvölgyi (FOCS 2021) improved this bound to $3.55^n+O(1)$. We prove that ${\rm SM}(n)<2.81^n$. This brings the exponential base closer to $2.28$, the base of the best known lower bound. More precisely, we bound the number of stable matchings in each instance in terms of each person's number of stable partners, where a stable partner is someone matched to that person in at least one stable matching. Our proof assigns each person a weight determined by this number and uses these weights to bound the number of stable matchings by induction.

Authors: Amotz Bar-Noy, Omri Kosary, David Peleg, Dror Rawitz

In the Degree Realization problem with respect to a family $\mathcal{P}$ of graphs the input is a non-increasing sequence $d = (d_1,\ldots,d_n)$ of positive integers, and the goal is to decide whether there exists a simple undirected graph $G \in \mathcal{P}$, whose degrees correspond to $d$, i.e., such that $deg(G) = d$. In this paper we consider the version of Degree Realization in which the realization is required to be a forest (i.e., $\mathcal{P}$ is the family of forests). We consider \emph{optimized} Degree Realization in which the goal is to obtain a realization that minimizes an objective function $f$. That is, the goal is to find a realization $G$ that minimizes $f(G)$ among the realizations of the given input sequence. More specifically, we focus on the following functions: the size of an optimal \emph{vertex cover} and the size of an optimal \emph{dominating set}. We also consider the \emph{total} and \emph{paired} versions of both Min Vertex Cover and Min Dominating Set. We provide characterizations and linear time realization algorithms for all the above-mentioned problems. Since Min Paired Vertex Cover is closely related to Min Edge Dominating Set, our results for Degree Realization with respect to the former extend to the latter.

Authors: Koustav Bhanja, Merav Parter, Asaf Petruschka

For over four decades, two classical structures have offered complementary views of mincuts. The Gomory-Hu tree encodes one $(x,y)$-mincut for every vertex pair $x,y$ in $O(n)$ space, but retains only one mincut per pair. In contrast, for a fixed pair $x,y$, the Picard-Queyranne representation admits an $O(n)$ space vertex ordering that determines whether some $(x,y)$-mincut separates any given pair $u,v$ and reports such a cut. Can these complementary guarantees hold simultaneously in $O(n)$ space? We answer affirmatively. For undirected graphs, we construct an $O(n)$ space structure encoding, for every four vertices $x,y,u,v$, an $(x,y)$-mincut separating $u,v$ whenever one exists. More precisely, given any terminal pair $x,y$, the structure recovers the Picard-Queyranne ordering in $O(n)$ time. Thereafter, separability queries take $O(1)$ time, and reporting a separating mincut $C$ takes $O(|C|)$ time. Thus, information for all $Θ(n^4)$ choices of $x,y,u,v$ is encoded in $O(n)$ space. This is essentially the strongest information of this form that fits in $O(n)$ space: if one additionally requires the mincut to place $u$ on side of $x$ and $v$ on side of $y$, then $Ω(n^2)$ space is necessary even for fixed $x,y$. As a consequence, we obtain an $O(n)$ space all-pairs mincut sensitivity oracle for a single edge failure in multigraphs, with optimal $O(n)$ time to report a new mincut. This resolves an open question of Baswana and Pandey [SODA'22] on achieving $o(n^2)$ space and $o(m)$ query time simultaneously. Our construction substantially generalizes the $O(n)$ space nearest-mincut-hierarchy [SODA'27], which reports only the nearest $(x,y)$-mincut. Recovering the entire Picard-Queyranne ordering for an arbitrary pair requires new structural properties of the Dinitz-Vainshtein [STOC'94] connectivity carcass, extending its use beyond the Steiner mincuts it represents.

Authors: Jingyang Zhao, Trung Q. Duong, Een-Kee Hong, Hyundong Shin

The traveling salesman problem (TSP) is one of the fundamental problems in combinatorial optimization that asks for a minimum-cost Hamiltonian cycle in a complete undirected graph with $N$ vertices. For the metric TSP, where edge costs satisfy the triangle inequality, a long line of work has produced constant-factor approximation algorithms, culminating in the best-known approximation ratio $α<3/2-10^{-36}$. The biased TSP (BTSP) generalizes the metric TSP to bipartitioned networks: the vertex set is partitioned into two subsets, edge costs satisfy the triangle inequality within each subset, while edges crossing the partition may violate it by a certain bias factor. This model captures heterogeneous routing scenarios in which distances are metric only locally but may be distorted across different regions or vertex types. Previously, the only known result for the BTSP was a $7/2$-approximation algorithm with running time $O(N^3)$. In this paper, we present two new approximation algorithms that significantly improve the state of the art. The first achieves an approximation ratio of $2α+\varepsilon$ (strictly less than $3$) in polynomial time $N^{O(1)}$ for any constant $\varepsilon>0$, where the exponent grows at least linearly with $1/\varepsilon$. The second achieves a $4$-approximation in only $O(N^2)$ running time, reducing the previous cubic-time bound by a full polynomial factor. These advances directly support emerging networked systems---including multi-tier 6G architectures and hybrid quantum-classical networks---where cross-region transitions incur biased and non-metric overheads.

Authors: Davide Bilò, Bartłomiej Bosek, Jadwiga Czyżewska, Evangelos Kipouridis, Karol Węgrzycki, Anna Zych-Pawlewicz

We present efficient partially dynamic algorithms for maintaining earliest arrival times from a fixed source in temporal digraphs with $n$ vertices. For the incremental scenario where updates are arc insertions, our algorithm has a constant query time and requires a total update time of $O(n + m \log m)$, where $m$ is the total number of arcs added to the arc-less graph. For the decremental scenario where updates are arc removals, our algorithm has a constant query time and requires a total update time of $O(n + m \log m)$, where $m$ is the number of arcs in the graph upon its initialization. We also consider earliest-arrival queries with an arbitrary departure-time threshold and develop an incremental algorithm with $O(n+Δ_s m\log m)$ total update time, $O(\log m)$ query time, and $O(n+m)$ space, where $Δ_s$ is the number of distinct departure times of arcs leaving the source. All of our algorithms are also capable of reporting an earliest arrival path from the source to the queried vertex $v$ in constant time per edge once the earliest arrival time at $v$ is known. We complement our positive results with conditional lower bounds based on the Online Boolean Matrix-Vector Multiplication conjecture (a.k.a. OMv conjecture). For both the incremental and the decremental scenarios, we show the non-existence of an algorithm with $O(n^{1-\varepsilon})$ amortized update time and $O(n^{2-\varepsilon})$ amortized query time, even if the algorithm is randomized and latencies on the arcs are uniform. For arbitrary departure-time queries, we also establish an OMv-based conditional lower bound showing that our incremental algorithm is optimal up to logarithmic factors on dense temporal graphs. Thus, efficient total running time is essentially the best outcome we can get. Our conditional lower bounds hold also for the case of undirected temporal graphs.

Authors: Eeshan Banerjee, Aranya Kumar Bal, Debabrota Basu, Sourav Chakraborty, Debarshi Chanda, Uddalok Sarkar

The \textit{Union Volume Estimation problem}, i.e. yielding an $(\varepsilon, δ)$-approximation of the volume of the union of convex bodies, is a classical problem in computational geometry and formal methods. In this paper, we first detect where and why the efficient union volume estimators with approximate sampling and PAC volume estimation oracles fail. Specifically, we show that having only TV-distance guarantees on the approximate sampler does not suffice, and demonstrate this bottleneck by constructing the sunflower families of convex bodies. In this context, we propose the concept of \textit{tail-controlled samplers} that can yield with high-probability almost-$\ell_{\infty}$ closeness. Secondly, we leverage this concept to propose a generic algorithmic framework \texttt{Alpona} that properly combines a PAC volume computation and approximate point sampling oracles with tail-controls to yield an $(\varepsilon, δ)$-estimate of the union volume for any collection of convex bodies. We show that \texttt{Alpona} needs only linear (in number of convex bodies) oracle calls to be $(\varepsilon, δ)$-correct. Finally, we provide a tail-controlled analysis of the Hit-and-Run sampler~\citep{lovasz2006fast}. We further provide a novel geometric analysis to improve the required walk length of Hit-and-Run. We further instantiate \texttt{Alpona}'s correctness for the sparse frequency streams of convex bodies: a special case of the union volume estimation problem where no convex body intersects more than $τ$ many other bodies.

Authors: Esther Galby, Roohani Sharma, Bart van der Steenhoven

In [Combinatorica 1996], Reed, Robertson, Seymour and Thomas proved Younger's conjecture dating back to 1973 that states that directed cycles have the Erdős-Pósa property. Specifically, they showed that every directed graph $D$ contains either $k$ arc-disjoint cycles or a set of at most $f(k)$ arcs that intersect every directed cycle. The function $f$, depending only on $k$, is however notoriously large--in fact, not even elementary. The first improvement on this function was only very recently provided by Hatzel, Kreutzer, Milani, and Muzi [FOCS 2024] who showed that $f$ can be taken to be an exponential tower of height $8$. In this work, we improve this function to $O(k^4)$ in the case where the digraph is Eulerian. This also answers an open question by Wahlström [Springer Monographs in Mathematics 2018] who asked explicitly when Eulerian digraphs have a polynomial Erdős-Pósa property. The only other known result about Erdős-Pósa on Eulerian digraphs is a result from Seymour [Combinatorica 1996] who showed that $f(k)=k$ when the Eulerian digraph admits a linkless embedding in 3-space, and such an equality is not possible for general Eulerian digraphs. We also complement our positive result, by showing that the result of Seymour cannot be extended to give a linear bound ($O(k)$) on general Eulerian digraphs, by showing that even on Eulerian digraphs the lower bound for the Erdős-Pósa property is $Ω(k \log k)$.

Authors: Matthias Bentert, Dario Cavallaro, Sebastian Wiederrecht

Given an undirected graph $G$ and a set $R \subseteq V(G)$ of terminals, Terminal Cyclability asks whether $G$ contains a simple cycle visiting every vertex of $R$. We establish a complexity dichotomy for this problem on red-minor-closed classes of annotated graphs. In particular, we show that Terminal Cyclability is polynomial-time solvable on every such class excluding any annotated planar graph. The problem is NP-complete whenever the class contains all annotated planar graphs. More precisely, we give an $|G|^{2^{\mathbf{poly}(b)}}$-time algorithm, where $b$ is the bidimensionality of $(G,R)$. Our main technical contribution is the introduction of a weak irrelevant vertex rule. Rather than removing irrelevant vertices until the treewidth becomes constant, we only remove irrelevant vertices until the treewidth is logarithmic in the graph size. Such a weakening is necessary as a parameter-only treewidth threshold for an irrelevant vertex rule in this setting is known to be impossible to realise. Combined with a single-exponential algorithm for Terminal Cyclability parameterized by treewidth, this yields the polynomial-time algorithm for our dichotomy.

Authors: Eric Balkanski, Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, Morteza Zadimoghaddam

Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental question that separates consistency from the other two: what does solution stability cost when the entire future is known and computation is unlimited? We answer this question for monotone submodular maximization, where an algorithm must maintain a solution of at most $k$ arrived elements, with a constant number of changes per step. We determine the optimal approximation thresholds: $3/4$ for deterministic algorithms and $ξ^\star \approx 0.7942$ for randomized algorithms. For every $\varepsilon>0$, we get within $\varepsilon$ of these thresholds with worst-case recourse polynomial in $1/\varepsilon$, independent of $k$ and the stream length. We prove matching impossibility results even for coverage functions. We attain the sharp bounds by optimally balancing two opposing forces: preparing for future arrivals and protecting the current solution. For randomized algorithms, we use addition robustness against prefixes of the known future, which we analyze tightly via an interval-selection problem. For deterministic algorithms, we introduce certificates, paths in a fractional relaxation that maintain high value, which we round into an update schedule.

Authors: Sunny Atalig, Marek Chrobak, Petr Kolman, Hans Raj Tiwary

The spanning tree congestion of a connected graph \(G\) is the minimum, over all spanning trees \(T\) of \(G\), of the maximum number of edges of \(G\) crossing a cut induced by deleting an edge of \(T\). In the spanning tree congestion problem we are asked to compute a spanning tree with minimum congestion. We describe two sublinear-ratio approximation algorithms for the spanning tree congestion problem (STC): a simple $\Ot(n^{8/9})$-approximation, and a more involved $\Ot(n^{2/3})$-approximation, where the notation $\Ot$ hides factors polynomial in $\log n$.. Until now, no algorithm with sublinear ratio was known. We also prove that for any fixed $0<\varepsilon<1$, approximation of the spanning tree congestion within $2-\varepsilon$ is NP-hard. This improves the previous best known lower bound $6/5$.

Authors: Leszek Gąsieniec, Tytus Grodzicki, Grzegorz Stachowiak

Population protocols model computation by indistinguishable agents interacting in uniformly random pairs, with unary inputs and outputs encoded by state counts. Efficiency requires polylogarithmically many states and polylogarithmic stabilisation time, measured as interactions divided by population size $n$. Stability requires eventual stabilisation to the correct output with probability $1$; silence requires that no agent changes state after stabilisation. Fast stable leader election and majority in leaderless populations require growing state spaces. Despite progress on individual problems, the general computational power of efficient stable protocols remains largely unexplored. We show that it extends beyond semilinear predicates, which characterise constant-state stable computation. We give an efficient, stable, and silent simulation of every $\mathcal{P}$-program: a word-RAM program with running time and number of registers polynomial in $w=Θ(\log n)$. Stabilisation takes polylogarithmic time both in expectation and with high probability. The framework supports general word-oriented computations, including multiple outputs. The construction extends MC$+$ protocols, fast Monte Carlo protocols whose failures are eventually detected as anomalies, and the system of weights. MC$+$ majority comparisons against the weights convert unary inputs into binary registers, with one agent per bit. MC$+$ operations on individual bits emulate RAM instructions, after which outputs are converted back to unary. A detected anomaly triggers a new universal rank-based backup that stabilises correctly and silently. These results open a systematic study of computational power and resource trade-offs, including extensions to external or spatial data.

Authors: Edith Cohen, Mohammad Roghani

A local computation algorithm (LCA) for matching answers ``who is the mate of $v$?'' by inspecting only a small part of the graph, with all answers consistent with one matching. For $n$-vertex graphs of maximum degree $Δ\ge2$, Levi et al. [Algorithmica'17] give a $(1-\varepsilon)$-approximate matching LCA using $(Δ/\varepsilon)^{O(1/\varepsilon^2)} \operatorname{polylog}(n)$ queries per invocation, while Yoshida et al. [SIAM J. Comput.'12] estimate the maximum matching size within additive error $\varepsilon n$ using $Δ^{O(1/\varepsilon^2)}$ queries. Behnezhad, Roghani, and Rubinstein [FOCS'23] proved a $Δ^{Ω(1/\varepsilon)}$ lower bound for both tasks, even on bipartite graphs and even when the LCA's matching guarantee is relaxed to additive $\varepsilon n$ error. This leaves a gap between linear and quadratic dependence on $1/\varepsilon$ in the exponent. We close this gap on bipartite graphs. We give an LCA that answers each mate query with $Δ^{O(1/\varepsilon)}$ queries for a $(1-\varepsilon)$-approximate matching, and an estimator for the maximum matching size within $\varepsilon n$ using $Δ^{O(1/\varepsilon)}$ queries. On general graphs, the same algorithm gives a half-integral fractional matching and estimates the maximum fractional matching size. Our approach runs $O(\varepsilon^{-1}\logΔ)$ rounds of a deterministic local optimization method in which vertices propose to neighbors and update prices according to incoming loads. We design its updates to admit exact recursive sampling with constant expected branching, obtaining the improved randomized bound without exploring full dependency neighborhoods. To our knowledge, this is the first LCA construction based on exact recursive sampling of the iterates of a deterministic continuous optimization method. We expect this approach to have applications beyond matching.

Authors: He Sun, Yong Zhang, Yacong Zhou

Partitioning the vertex set of a graph $G=(V,E)$ into clusters is a classical problem in computer science. As vertices within clusters should be well connected and cuts between clusters sparse, Oveis Gharan and Trevisan (SODA 2014, [OGT14]) proposed to measure the partition quality using inner and outer conductance, i.e., the bi-criteria guarantee. Specifically, when partitioning $V$ into vertex-disjoint subsets $P_1,\ldots, P_k$, every subgraph induced by $P_i$ should have high conductance, while the conductance of $P_i$ in $G$ should be low. They studied the existence of such a partition and designed a polynomial-time algorithm achieving this guarantee. For more than a decade, their algorithm remained the only one achieving this guarantee on its output clusters. In this paper, we study faster cluster decomposition algorithms under the same setup as [OGT14] and prove three results: 1. We make their existential result algorithmic: Our algorithms run in nearly-linear time, and achieve the same bi-criteria guarantee as the one in [OGT14] up to constant factors, including the asymptotically tight dependence on $k$. 2. We prove that their existential result holds algorithmically under a much weaker condition on the initial disjoint subsets. To achieve this, we develop a general algorithm framework that boosts the approximation guarantee of a solution: given an $α$-approximate solution to the $k$-way conductance problem, if $ρ_G(k+1)/ρ_G(k)=Ω\left(α/\varepsilon\right)$, then a $(1+\varepsilon)$-approximate solution can be obtained using only $O(k(1+\logα))$ minimum $s$-$t$ cut computations. 3. We present a nearly-linear time algorithm that finds clusters with the bi-criteria guarantee. Our algorithm has the same guarantee as the one in [OGT14], which, for any unweighted graph of $n$ vertices and $m$ edges, runs in $\widetilde{O}(knm^2)$ time.

Authors: Soh Kumabe

Minimum Bisection asks whether the vertices of a graph can be partitioned into two parts whose sizes differ by at most one and with at most k edges between the two parts. Cygan, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saurabh (SICOMP 2019) gave the first fixed-parameter algorithm, which runs in O*(2^(O(k^3))) time, by introducing an unbreakable decomposition. Cygan, Komosa, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saurabh, and Wahlström (TALG 2021) strengthened the decomposition and improved the running time to O*(2^(O(k log k))). However, whether the running time could be improved to single-exponential remained open. In this paper, we give a deterministic O*(2^(O(k)))-time algorithm for Minimum Bisection. Our algorithm also counts all feasible bisections. To obtain an O*(2^(O(k)))-time algorithm, we introduce two new techniques. First, we give a new algorithm that computes a (2k,k)-edge-unbreakable decomposition with adhesion at most 2k in O*(2^(O(k))) time by relaxing the unbreakability and adhesion guarantees of the decomposition in (TALG 2021). Second, we improve the running time of the dynamic program over the decomposition from O*(2^(O(k log k))) to O*(2^(O(k))) using important cuts, inclusion-exclusion, and formal logarithms and exponentials. Together with color coding, the same techniques give a deterministic O*(2^(O(k)))-time algorithm for Matching Cut, which asks for a cut whose crossing edges form a matching. This improves the O*(2^(O(k log k)))-time algorithm of Aravind and Saxena (IWOCA 2021).

Authors: Chunyang Wang, Yitong Yin, Yixiao Yu, Yiyao Zhang

We resolve longstanding questions about connectivity, reconstruction,and looseness in random $k$-SAT, for sufficiently large fixed $k$ as the number $n$ of variables tends to infinity. $\textbf{Single-variable connectivity up to reconstruction.}$ At clause densities up to \[\frac{2^k}{k}\bigl(\ln k+\ln\ln k+γ_*-o_k(1)\bigr),\] a polynomial-time algorithm joins a typical pair of satisfying assignments with high probability, using $O_k(n)$ single-variable flips that preserve satisfiability. Here $γ_*\approx0.871$ arises from a refined tree-reconstruction analysis. $\textbf{Settling the reconstruction threshold.}$ Building on the tools developed for connectivity, we determine the clustering threshold defined by the reconstruction criterion to be \[\frac{2^k}{k}\bigl(\ln k+\ln\ln k+γ_*+o_k(1)\bigr),\] below the classical cavity prediction with constant term $1+O(\ln\ln k/\ln k)$. $\textbf{Shattering before rigidity.}$ We locate the looseness--rigidity transition at a higher density, matching the classical cavity prediction for clustering: \[\frac{2^k}{k} \left(\ln k+\ln\ln k+1+Θ\left(\frac{\ln\ln k}{\ln k}\right)\right).\] Below the transition, we establish a stronger form of looseness: any variable of a typical solution can be reversed by logarithmically many single-variable flips that preserve satisfiability. Above it, reversing most variables of a typical solution requires changing linearly many variables (rigidity). Yet throughout an interval between reconstruction and rigidity, the solution space already splits into groups of exponentially small relative size separated by linear Hamming distance and linear energy barriers (shattering), while logarithmic looseness persists.

Authors: Hongyi Chen, Shuyan Fan, Tianyi Zhang

We study the fully dynamic maximal independent set (MIS) problem: maintaining an MIS in an undirected graph on $n$ vertices with at most $m$ edges under edge insertions and deletions. Against an oblivious adversary, which fixes the edge update sequence in advance, the randomized algorithms of Behnezhad et al. (2019) and Chechik and Zhang (2019) achieve polylogarithmic update time. Against an adaptive adversary, which may choose each update after observing the previously reported MISs, the best previously known update bound was $O(m^{2/3})$, given by the deterministic algorithm of Gupta and Khan (2018, 2021). Assuming the combinatorial Boolean matrix multiplication hypothesis, Bernstein et al. (2026) proved that any combinatorial algorithm against an adaptive adversary requires at least $m^{1/2-o(1)}$ update time even under edge insertions alone, leaving a polynomial gap between upper and lower bounds. We present a randomized fully dynamic MIS algorithm with $\widetilde O(m^{5/8})=\widetilde O(m^{2/3-1/24})$ update time against adaptive adversaries. This gives the first polynomial improvement over the $m^{2/3}$ bound for adaptive fully dynamic MIS.

Authors: Xiaorui Sun

The finite-group isomorphism problem asks whether two groups, given by their Cayley tables, are isomorphic. Despite decades of study, obtaining an $N^{o(\log N)}$-time algorithm for general groups of order $N$ remains a major open challenge. Groups of nilpotency class $2$ have long been a central obstacle to achieving this goal. Recent breakthroughs have established $N^{o(\log N)}$-time algorithms for $p$-groups of class $2$ with odd $p$ (Sun, STOC '23; Ivanyos-Mendoza-Qiao-Sun-Zhang, FOCS '24; Grochow-Qiao-Stange-Sun, STOC '25) and for groups of Frattini class $2$ (Grochow-Ivanyos-Qiao-Sun, FOCS '26). However, the problem remained open for general groups of class $2$. In this paper, we present an algorithm for testing isomorphism of groups of class $2$, with running time $N^{O((\log N)^{25/26} \log \log N)}$. Our algorithm combines a tensor-based restriction of the search space, an encoding of group relations by alternating matrix tuples, and an orbit computation to recover the remaining central power information.

Authors: Cong Ma, Guangting Chen, Yong Chen, Guohui Lin, Jiaxuan Ma, Lusheng Wang

We study the minimum-disagreement cluster editing problem that, from a complete edge-signed graph, where a positive edge represents two vertices agreeing to each other while a negative represents a disagreement, constructs disjoint cliques of upper bounded size such that the total number of negative edges inside cliques and positive edges outside cliques is minimized. When the sizes of the candidate cliques are unbounded, the problem is NP-hard and APX-hard, and many approximation algorithms with improving ratios have been proposed in the literature and the state-of-the-art approximation ratio of $α= 1.3865 + ε$. The capacitated variant, in which the candidate cliques have sizes no greater than a given $k$, is less studied and the best approximation ratio is $5.37$. In this paper, we study the latter problem. We first present a downsizing procedure that achieves an approximation ratio of $α_k = 2 α+ 1$, based on any $α$-approximation algorithm for the uncapacitated problem. Secondly, we propose a hybrid of cluster-LP sampling and pivoting and show that for every fractional capacitated cluster-LP solution of cost $L$, the hybrid using ordinary pivoting has an expected cost at most $\frac 95 L + \frac 1{10} \OPT_k$, and the hybrid using conditional pivoting has an expected cost at most $\frac {306}{203} L + \frac {50}{203} \OPT_k$. A cardinality-constrained adaptation of the approximate dual-separation framework of García-Soriano and Schohn supplies the required fractional solution and yields a randomized $(1.9 + ε)$-approximation algorithm and a randomized $(1.7537 + ε)$-approximation algorithm, respectively.

Authors: Yanyu Chen, Yu Chen, Zihan Tan, Mingyang Yang

Given an undirected unweighted graph $G$ on $n$ vertices and a set $P$ of $p$ pairs of its vertices, a distance preserver is a sparse subgraph of $G$ that exactly preserves the shortest-path distances between all pairs in $P$. In this paper, we prove a new upper bound of $O(n^{8/9} p^{4/9})$ for distance preservers when $p\in [n^{1/2}, n]$. Our result improves the previous bound of $O\big(n^{2/3}p^{2/3}+np^{1/3}\big)$ by Bodwin and Vassilevska Williams and $O(\min\{n+n^{1/2}p,\,np^{1/2}\})$ by Coppersmith and Elkin, particularly in the regime $p\in [n^{7/10}, n]$, and narrows the gap toward the conjectured $O(n^{2/3}p^{2/3}+n)$ bound. Using the techniques developed for distance preservers, we are also able to obtain pairwise additive $+2$ spanners with $O(n+n^{9/10}p^{2/5})$ edges, pairwise additive $+4$ spanners with $O(n+n^{24/25}p^{8/25})$ edges, and new bounds for sourcewise spanners, improving upon previous results in certain parameter regimes.

Authors: Lucy McManamon, Jingjin Yu

We study the largest minimum makespan of labeled pebble motion on graphs under a model that permits synchronous pebble movement. While classical pebble motion on graphs allows only one pebble to move at a time, our model permits any number of pebbles to move to an adjacent vertex, provided that no two pebbles collide. At full occupancy every vertex is assigned a pebble and a legal round consists of disjoint cycle rotations. We prove a series of makespan bounds for this problem on graphs with varying structure and pebble density. For cycles with a chord, we extend a known quadratic bound at span two to every fixed span. For random cubic graphs, we convert permutation routing via matchings into legal schedules in two ways, applying cycle-cover batching at full occupancy and disjoint vacancy-delivery paths below full occupancy. For simple 3-connected planar cubic graphs, we prove a tight linear class maximum at every pebble count. We extend the results to increasing degree, common-neighbor conditions, and vertex connectivity. The results describe how graph connectivity, cycle structure, expansion, planarity, and occupancy affect worst-case routing time.

Authors: Qihao Zhou

We study the component-oracle complexity of finding approximate local minima of nonconvex finite sums under mean-squared averaged smoothness with parameter $L$ and a $ρ$-Lipschitz average Hessian. Each query returns the value, gradient, and one Hessian-vector product of a component. We show that the complexity in the high-accuracy regime $\varepsilon\le c_0L^2/(nρ)$ is $\tildeΘ(n^{3/4}L^{1/2}ρ^{1/4}Δ\varepsilon^{-7/4})$ for a sufficiently large initial gap $Δ$. We attain the upper bound by adapting the inverse solver and eigenvector routine of FastCubic to averaged smoothness. Our lower bound assigns the bridge edges of a nested chain to random components; a replicated spectral construction gives the same bound for unrestricted randomized algorithms. Under individual smoothness, a factor of $n^{1/4}$ remains for $\varepsilon\le cL^2/(n^2ρ)$, up to logarithmic factors. In the complementary low-accuracy regime, we propose PathVR, which uses $\tilde O(n+\sqrt{n}LΔ\varepsilon^{-2})$ queries and matches a lower bound from dense weak hiding.

Authors: Zhangsong Li

We study the random-cluster model on locally treelike graphs at low temperatures. This is a model of dependent percolation parametrized by an edge probability $p \in (0,1)$ and a clustering weight $q \in [1,\infty)$, generalizing independent Bernoulli percolation ($q=1$) and closely related to the classical ferromagnetic Ising and Potts spin systems at integer $q$. For $q>2$, at parameter $p$ below the tree uniqueness threshold $p_{\mathsf u}(q,d)$, it is expected that sampling is easy and local Markov chains mix rapidly on all graphs with degree bounded by $d$. On typical graphs, the same is predicted at $p>p_{\mathsf s}(q,d)$, where $p_{\mathsf s}(q,d)$ is a second uniqueness transition point on the $d$-regular wired tree. Our result confirms this prediction for random regular graphs, showing that the random-cluster Glauber dynamics mix in time $O(n^{1+o(1)})$ on a random $d$-regular graph for all fixed $q>2$ and $p>p_{\mathsf s}$. For comparison, the best prior sampling results for these models that held for all $p>p_{\mathsf s}$ required $q\gtrsim \log d$ \cite{BGPZ26}. The key difficulty is that simply utilizing the contraction of cavity messages on $d$-regular trees does not suffice to cover the entire regime $q>2$. To address this issue, motivated by \cite{LS26}, we develop a careful bootstrap argument to show the shrinkage of disagreement under grand coupling. The core ideas of the proof were generated using GPT-6 and the Pharos system; the proof was then refined and simplified by the author.

Authors: Moses Charikar, Alireza Haqi, Jabari Hastings, Yichen Huang, Prasanna Ramakrishnan

We study metric distortion in one-sided matching. Given $n$ agents and $n$ items in an unknown metric space, our goal is to match agents to items so that the total distance between matched pairs is small. However, instead of direct access to the distances in the metric, we are only given each agent's ranking of the items by distance. What is the smallest worst-case approximation factor (called the distortion) that a mechanism can guarantee in expectation? Despite significant interest over the last decade, the best-known guarantee has been the $O(n)$ distortion of Random Serial Dictatorship since the beginning. We give a matching mechanism with distortion $O(n^{\log_4 3})$, the first sublinear upper bound. The key idea is to use a partial matching derived from a truncated version of either Random Serial Dictatorship or the Probabilistic Serial rule. We then complete this matching using a new, general-purpose cluster completion algorithm that ensures unmatched agents receive nearby items. Along the way, we pin down the optimal distortion of Random Serial Dictatorship and Probabilistic Serial up to logarithmic and constant factors, respectively, and give improved lower bounds for truthful mechanisms.

Authors: Yossi Azar, Junhao Gan, Shahar Lewkowicz, Xiao Sun, Seeun William Umboh

Online optimization with delays has emerged as a powerful paradigm with numerous applica- tions, including matching, caching, server management, network design, and set cover. In most of these problems, competitive algorithms are known for arbitrary monotone delay functions, even when different requests are associated with different delay functions. The notable exception is online matching with delays, where all previously known algorithms achieving constant or polylogarithmic competitive ratios require the delay functions to be identical, either linear or concave, and known in advance. We study the online minimum-cost perfect matching with delays problem on general metrics. We introduce the broad class of noncrossing delay functions, which strictly generalizes the classic setting of identical concave delay functions while naturally modeling scenarios in which different requests may experience different delay costs. We present the first deterministic $O(1)$-competitive algorithm for the single-location online matching problem with noncrossing delay functions in the non-clairvoyant setting as well as a randomized $O(lognlogΔ+log^2Δ)$-competitive algorithm of an arbitrary metric space where $n$ is the number of points of the metric space and $Δ$ is its aspect ratio. Our result allows each request to have an arbitrary noncrossing delay function, thereby simultaneously removing the assumptions of identical delay functions, concavity, and clairvoyance that were required by all previous constant or polylogarithmic-competitive algorithms.

Authors: Hung Le, Jack Spalding-Jamieson

We give a new algorithm for finding balanced separators in minor-free and induced-minor-free graphs. A key technical idea is a new connection to online learning: we formulate a continuous, non-convex optimization problem and solve it using the Follow the Regularized Leader (FTRL) framework. Our implementation of each FTRL step yields a purely combinatorial algorithm that assigns and adjusts vertex weights over multiple rounds. For graphs with $n$ vertices and $m$ edges, we obtain the following results. (1) For $H$-induced-minor-free graphs, we find a balanced separator of size $O(\log(|V(H)|)\sqrt{|V(H)|+|E(H)|}\sqrt{m})$ in expected linear time for fixed $H$. As a corollary, we find balanced separators of size $O(\sqrt{m})$ in string graphs in expected linear time, without requiring string representations. (2) For $K_h$-minor-free graphs, we find a balanced separator of size $O(h\log h\sqrt{n})$ in expected linear time for fixed $h$. Our algorithm unifies two long lines of work on separators in minor-free graphs, dating back to Alon, Seymour, and Thomas (1990): one optimizing separator size and the other optimizing running time. It also gives a natural interpretation of the vertex weighting scheme in a recent linear-time algorithm by Bonnet, Korhonen, Le, Li, and Masarik (2026). The separator bounds for both graph classes are flow-optimal: techniques based on flow-cut duality, including ours, cannot yield balanced separators of asymptotically smaller size.

Authors: Junbo Jacob Lian, Kaixuan Chen, Hanzhang Qin, Huiling Chen, Chaoyu Zhang, Chung-Piaw Teo

Dantzig-Wolfe reformulation strengthens the linear relaxation of a mixed-integer program by convexifying a chosen set of constraint families, and every candidate costs a column generation run. The choice is hard when families strengthen the bound only together, because a search that adds one family at a time then stops at the linear relaxation. The classical inequalities of lot sizing, network design and facility location rest on such zero-marginal groups. We prove that when each evaluation convexifies at most $s$ of $k$ families, any method that observes only bounds needs a covering number of evaluations, of order $k^w$, to find a hidden group of $w$ families, also on actual Dantzig-Wolfe relaxations. A prediction that misses $e$ members reduces the cost to $Θ(k^e)$, through one staged search that does not need to know $e$, so the evaluations a prediction saves measure what the predictor knows. We study two sources of predictions. A one-pass lookahead at an optimal LP dual is provably blind to groups whose families share no variable, and a language model reads the names and text of the model. JointDW verifies the prediction of the language model with the staged search and interleaves it with the lookahead at a bounded loss. Groups that strengthen the bound only jointly appear in a quarter of the MIPLIB-NL models whose bound can be improved. There the strongest language models identify them about as often as the lookahead, their predictions rest on the names for textbook models, and reasoning about doubles the accuracy of the same model. On larger models with distracting families, the lookahead finds the group in one evaluation of three families. Language models given only the text seldom name it, while one reasoning model given every coefficient names it in all but one answer and then needs fewer evaluations than the lookahead for pairs of families.

Authors: Nick Fischer, Yael Kirkpatrick, Vasileios Nakos

\emph{Text-to-Pattern Hamming Distances} is one of the most studied problems in string algorithms: given a text $T$ of length~$n$ and a pattern~$P$, the task is to compute the Hamming distance between~$P$ and every length-$|P|$ substring of~$T$. As exact algorithms have been stuck at time~$\tilde O(n^{3/2})$ for decades, a long line of work has turned to the $(1+ε)$-approximate version of the problem. Milestones include Karloff's $\tilde O(ε^{-2} n)$-time algorithm [IPL '93], followed by randomized improvements to $\tilde O(ε^{-1} n)$ by Kopelowitz and Porat [FOCS '15] and recently to $\tilde O(ε^{-0.915} n)$ by Chan, Jin, Vassilevska W., and Xu [FOCS '23]. In this work, we significantly improve this bound to $\tilde O(ε^{-2/3} n)$, using a considerably simpler algorithm. Our algorithm follows the framework of Chan, Jin, Vassilevska W., and Xu, which reduces the problem to a variant of 3SUM that we call \emph{Sumset Estimation}. We solve Sumset Estimation optimally (up to logarithmic factors) by replacing their matrix multiplication techniques with ideas from sparse recovery. Specifically, we adapt the classic Count Sketch by replacing its random signs with random complex roots of unity---a simple idea that may find further applications for other additive problems. Finally, we give evidence that our running time might in fact be optimal: we show that the $ε^{-2/3}$ dependence is \emph{best possible} for a certain natural class of algorithms, including ours and all previous algorithms.

Authors: Lucian Bicsi, Adrian Budău

In the incremental minimum spanning forest problem, weighted edges arrive one at a time. After each insertion we must report the edge that leaves the minimum spanning forest, and queries ask for the bottleneck distance of two vertices: the smallest possible maximum edge cost on a path between them. Link-cut trees solve both in $O(\log n)$ amortized time. In 2021 we wrote the folklore BottleneckTree, a short competitive-programming structure that stores one parent pointer and one cost per vertex, and conjectured that it also runs in $O(\log n)$ amortized time. We show that this conjecture is false: on a family of inputs, its amortized cost per operation is $Ω(\sqrt{n})$. We then present a structure with the same state, two arrays and a single loop, and prove that it runs in $O(\log n)$ amortized time per insertion and per query. Unlike the AM-tree of Ding, Gu and Sun, which attains the same bound, it stores no subtree sizes and maintains no balance invariant. For a connected graph with distinct costs, the structure can be viewed as an implicit link-cut tree on the Kruskal reconstruction tree: each rotation corresponds to exactly one preferred-child change, and each skip acts on a stale path-parent pointer. In experiments it is 1.3-2.1 times faster than the folklore BottleneckTree on insertions, up to 480 times faster on its adversarial input, and 6.3-16 times faster than an explicit link-cut tree.

Authors: Hector Tierno, Shuang Yang

The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give $n^{1/2+o(1)}$-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an $n^{2/15-\varepsilon}$-approximation in $\widetilde{O}(m+n)$ time for every fixed $\varepsilon\in(0,2/15)$, establishing the necessity of polynomial loss for nearly-linear time algorithms.

Authors: Yichen Huang

The online $k$-server problem is one of the most fundamental problems in online algorithms. In this problem, $k$ servers are located in a metric space and serve a sequence of requests at points in the metric space by moving a server there. The Harmonic algorithm is a very natural algorithm: it chooses a server with probability inversely proportional to its distance from the request. It is also highly efficient, being memoryless and answering each request in $O(k)$ time. However, its competitive ratio has remained unsettled between the $O(2^k \log k)$ upper bound (Bartal and Grove, JACM 2000) and the $k(k+1)/2$ lower bound (Raghavan and Snir, 1994, IBM J. Res. Dev.). We prove that Harmonic is $2k^4$-competitive on every metric space against adaptive online adversaries. Our analysis uses a potential combining corrected electrical energy with the distances of online servers to their assigned adversary locations.

Authors: Aleksandar Nikolov, Haohua Tang

In this paper we study answering counting and other linear queries online under differential privacy constraints. Recent work by Nikolov, Tang, and Ullman [STOC 2026] gave the first online algorithm that answers \emph{obliviously chosen} online linear queries privately, and achieves poly-logarithmic competitiveness against an optimal offline factorization mechanism. This also implied poly-logarithmic competitiveness against arbitrary private offline mechanisms when the private dataset is large enough. The error guarantees of their algorithm, however, can fail when the queries are adaptive. We give a new algorithm that also achieves poly-logarithmic competitiveness, while being able to handle \emph{adaptively chosen} queries. This implies that there is no large separation between the optimal error bounds for privately answering, respectively, offline linear queries, obliviously chosen online linear queries, and adaptively chosen online linear queries. Our algorithm combines the online factorization approach from prior work with a novel layered Euclidean iterative database construction, presenting a new way to use factorization in private algorithms. We also give a lower bound that shows that some poly-logarithmic factor in the competitive ratio is unavoidable. Our lower bound first shows that any interactive private mechanism implies a deterministic online factorization algorithm, and then gives a new lower bound for the competitive ratio of any deterministic online factorization algorithm.

Authors: Jan Olkowski

We consider synchronous binary Byzantine agreement among $n$ processes connected by authenticated point-to-point classical and quantum channels. The adversary is computationally unbounded, sees all classical information, adaptively corrupts up to $t\le(1/3-\varepsilon)n$ processes, and may suppress messages sent by a process in the round in which it is corrupted. We give a quantum algorithm that solves Byzantine agreement in this model with probability $1$. It uses $O(\log^4 n)$ rounds, $O(n\log^8 n)$ qubits, and $O(n^2\log^8 n)$ classical bits in expectation, with constants depending on $\varepsilon$. This reduces the quantum communication of the protocol of Ben-Or and Hassidim (STOC~2005), which achieves $O(1)$ expected rounds but whose Byzantine coin implementation requires $Ω(n^4\log n)$ qubits and classical bits. We also extend the quadratic message lower bound of Abraham et al.\ (PODC~2019) to quantum channels, obtaining an $Ω(t^2)$ lower bound on worst-case expected total communication. For $t=Θ(n)$, the communication and round complexity of our algorithm are therefore optimal up to polylogarithmic factors.

Authors: Nicola Wengiel

We prove a lower bound of $Ω_d((\log N)^{d-1/2})$ for the worst-case combinatorial discrepancy of $N$-point sets with respect to anchored boxes in every fixed dimension $d\ge3$. Together with Nikolov's upper bound of the same order and Wei's planar lower bound, this settles Tusnády's problem: the discrepancy of axis-parallel boxes is $Θ_d((\log N)^{d-1/2})$ in every fixed dimension $d\ge2$. The proof combines smoothed product test functions, sampling discretization, and an entropy argument for conditioned Gaussian vectors.

Authors: Dimitar Chakarov, Yury Makarychev

We prove that the integrality gap of the Călinescu-Karloff-Rabani relaxation for Minimum Multiway Cut is at least $1.2325$ when the number of terminals is large. By a result of Manokaran, Naor, Raghavendra, and Schwartz (2008), it is therefore NP-hard, under the Unique Games Conjecture, to approximate Minimum Multiway Cut within a factor of $1.2325$. This improves the previously best known lower bound of $1.20016$ due to Bérczi, Chandrasekaran, Király, and Madan (2020).

Authors: Vasco Schiavo

Motivated by context management in LLM agents, we study a repeated rent-or-buy model with schedule-independent history growth and a fixed reset price $K$, a discrete form of dynamic TCP acknowledgment: every call pays as rent the history accumulated since the last reset, and a reset clears it. The classical threshold rule is $2$-competitive, and no deterministic rule guarantees a smaller ratio. We show that, measured additively, its loss is governed by the changes in the growth: if the growth is constant on $P$ runs, the threshold rule, knowing neither the runs nor the horizon, pays at most $(2P-1)K$ more than the optimal schedule chosen with hindsight, and the coefficient $2P-1$ is sharp. If the growth is only within a factor $1+\varepsilon$ of $P$ runs, the bound holds up to a factor $1+\varepsilon$ and an extra $\varepsilon K$. The proof is a potential argument built from the relative value functions of the single-rate problems. On two runs no deterministic rule guarantees a loss below $2K$. A rule that also resets when the growth decreases guarantees $2K$, while the threshold rule can lose arbitrarily close to $3K$.

We investigate the depth overhead of stretch-amplification for pseudorandom generators in the black-box model. We show that any black box construction of a PRG $H: \{0,1\}^m \to \{0,1\}^M$ which makes $\mathrm{poly}(n)$ queries to a PRG $G: \{0,1\}^n \to \{0,1\}^N$ in $d$ adaptive phases during each evaluation (and with a black-box reduction to the security of $G$) must satisfy: $M \leq (m + O(\log n)) \Bigl( \frac{N}{n - O(\log n)} \Bigr)^d$. This implies that the standard amplification procedure [GM'84, GGM'86] based on repeated composition of $G$ is essentially optimal. In particular, amplifying $n \mapsto n+1$ to $m \mapsto 2m$ requires depth overhead $d = \Omega(\frac{n}{\log n})$, and amplifying $n \mapsto 2n$ to $m \mapsto m^2$ requires depth overhead $d = \Omega(\log n)$; each of these bounds is tight up to a constant factor. As an immediate corollary we obtain tight lower bounds on the depth complexity of black-box constructions of PRFs from PRGs. Both of these problems (pertaining to amplification and PRF construction) have been studied in various prior works [V'05, MV'11, BJP'11, MV'15, BMM'24, ADV'26]. Despite progress on special cases in which the structure of the reductions is constrained, it was previously unknown whether completely parallel constructions ($d=1$) existed in every stretch regime. The kinds of amplification procedures we investigate have more recently found use outside of cryptography in the study of range avoidance ("Avoid") [K'21]. We show an analogous result in this setting: any black-box $\mathrm{FP^{NP}}$ reduction from an Avoid instance $G: \{0,1\}^n \to \{0,1\}^N$ to a second Avoid instance $H: \{0,1\}^m \to \{0,1\}^M$ which has "depth $d$" in the above sense must satisfy the same bound relating $n,N,m,M,d$. Using this impossibility result for Avoid, we construct an oracle relative to which $\mathrm{E} \not\subseteq \mathrm{NC}/\mathrm{poly}$ but $\mathrm{E^{NP}} \subseteq \mathrm{P}/\mathrm{poly}$. Our oracle separation implies that in the relativized setting, the bounded arithmetic theory $S^1_2$ cannot prove the existence of functions outside $\mathrm{P}/\mathrm{poly}$, even given as an axiom the existence of functions outside $\mathrm{NC}/\mathrm{poly}$.

Hi there, argmin readers! Today’s post is a late and brief reaction to a tiny subplot of yesterday’s historic election: the widespread rejection of AI datacenters. It was inspired by an insightful Dan Davies thread on bluesky that I have been unable to get out of my head.

Elections are a muddled measurement of “public opinion,” but they’re probably the only real measurement we get. And with every surprising measurement, a good rational agent must reflect on its beliefs. So what should we passive rational observers make of this historically large swing towards the Democratic Party in yesterday’s vote?

Obviously, this is a major repudiation of Donald Trump, his policies, and the Republican Party. However, you readers probably don’t come here for my political takes, and I don’t want to use this Substack for them anyway. Even if it wasn’t the biggest issue on the ballot, something closer to home is worth pondering. The American people are loud and clear that they hate AI.

Nearly fifty measures explicitly about building data centers appeared on ballots across the nation. All of them look like they will vote to limit further construction. A datacenter moratorium was part of Gina Hinojosa’s platform in her successful bid to become the first Democratic Party governor of Texas in over 30 years. The anti-datacenter position was undeniably the winning one. Poll results from this last summer showed people would rather have a coal plant in their backyard than a datacenter. Now elections confirm these sentiments were real.

We could try to convince ourselves that this sentiment is just about datacenters themselves. They are gross, gigantic buildings that employ no one, make a ton of noise, and are often powered with dirty energy. Who would want one of those? But datacenters are also a big, ugly, legible signal of a deeply unpopular industry.

At some point, we techy folks have to reckon with how much people hate what we build. We can point to revealed preferences all we want (people are adopting it! It’s making money!), but we did this during the social media boom of the 2010s (people spend a ton of time doomscrolling, therefore it’s good!). These economic numbers are also measurements, but we have to reconcile them with other data. Adoption and economic growth are so concentrated in so few hands that, while this props up our stock indices, it doesn’t lead to tangible benefits for everyone else.

Certainly, it doesn’t help that the industry has been selling itself as coming for everyone’s jobs. It doesn’t help that many prominent people working at these companies take to social media to gleefully exclaim that they think there’s more than a 10 percent chance that their company will kill everyone on earth. It doesn’t help that the big AI companies have been caught committing felonious cybercrimes all summer. It also doesn’t help that the leaders of these companies have been quite visibly embracing the Trump administration. Hugging a loser is a bad look, guys.

It’s a shame, because the technology is truly amazing. The AI true believers (accidentally) built something very cool that I would not have thought possible five years ago. But this amazing technology makes everyone miserable! It even immiserates its biggest boosters, who get sucked into productivity doom loops managing swarms of agents that speak in a unison chorus of Claudish. What’s our positive case here? The torment nexus of “superintelligence” ain’t it.

I have a lot of friends, colleagues, and alums who make a living building AI models. And I guess a bunch will be infinitely rich after the upcoming IPOs. But if you’re working for something more hated than the tobacco industry, maybe it’s way past time you stood up to your employer and demanded a better direction. And no, an open letter doesn’t count.

I’m not hopeful that this will happen. Ten years ago, I wrote a blog post shell-shocked by the election of Trump and disgusted with my industry. The cameo from Sam Altman explains a lot of my pessimism. I’ve been soul-searching for a decade. The leaders of the tech industry, instead of offering a positive vision and doing better, ended up sucking up to the new authoritarian government. They did it with pouting and feet dragging in 2016. They did it with their chests out in a celebratory embrace in 2024.

Our industry and field need a complete reboot. But that requires collective action. How do we fix it? What do we do next? I’d love to hear your thoughts on how the tech sector can clean up its image and make a positive, populist case for itself.

Subscribe now

By Ben Recht

The Simons Institute at UC Berkeley invites applications for two new postdoctoral-level research fellowships for a two-year period on the intersections of AI and TCS. Postdocs will be associated with the Institute’s newly established Research Pod for AI and TCS.

Website: https://simons.berkeley.edu/research-pods/ai-for-tcs-research-pod
Email: cawinter@berkeley.edu

By shacharlovett

When the Clay Mathematics Institute announced the Millennium Prize Problems back in 2000, we joked that if you proved P = NP, you wouldn't only get the $1 million prize for solving P v NP, but you would get $7 million since you could use P = NP to solve the rest.

By Lance Fortnow

I asked for this in one of the earliest posts on this blog, 12 years ago. The STOC committee has finally decided to post online the submissions, thus granting us all the option to follow what is happening in the greater theory community (see my blog post for more on my reasons). I guess that’s what it takes, an Alien Invasion.

By Manu

We investigate the behavior of the non-negative rank of a matrix, $\hbox{rk}_+$, on Kronecker product, $\times$. Beasley et al. [2013] constructed matrices with $\hbox{rk}_+(M\times M)$ strictly smaller than $\hbox{rk}_+(M)^2$. We will show that i) there exists an $M$ with $\hbox{rk}_+(M\times M)\leq O(\hbox{rk}_+(M)\log(\hbox{rk}_+(M))$. Defining asymptotic non-negative rank as $\overline{\hbox{rk}}_+(M):= \lim_{k\rightarrow \infty} \sqrt[k]{{\hbox{rk}}_+(M^{(k)})}$, where $M^{(k)}$ is the $k$-th Kronecker power, we show that ii) there exists an $M$ with $\overline{\hbox{rk}}_+(M)\leq O(\log \hbox{rk}_+(M))$, iii) there exist $M,N$ with $\overline{\hbox{rk}}_+(M\times N)<\overline{\hbox{rk}}_+(M)\overline{\hbox{rk}}_+(N)$. We also refute a conjecture of Vandaele et al. [2016] that $\hbox{rk}_+(M\times M)\geq \Omega(\hbox{rk}_+(M)\hbox{rk}(M))$.

We prove that $\VPnc$ is closed under taking factors over every field. If a noncommutative circuit of size $s$ computes a nonconstant polynomial of degree at most $D$, then each left or right factor has a circuit of size $O(sD^3)$. A central factor $g$ in a decomposition $f=agb$, with nonconstant outer factors $a,b$, has a circuit of size $O(sD^6)$. The proof uses a small weighted nondeterministic finite automaton (NFA) with replacement labels. Given $f=gh$, its labels depend on a word of maximum degree in $h$ and the coefficients of its suffixes. A pairing of accepting paths proves that the induced linear map $T$ satisfies $T(gh)=g$. Matrix substitution implements $T$ in a circuit. Applying the same substitution to a Boolean-sum verifier proves $\VNPnc$ closure. The construction also proves formula closure. The automaton has one copying state and, after leaving it, uses only scalar replacements. This structure gives formulas of size $O(s^2)$ for one-sided factors and $O(s^4)$ for central factors of a size-$s$ formula. The same map proves that polynomial-size noncommutative algebraic branching programs are closed under taking factors. Polynomial-size ABP factorizations over finite fields are already known from~\cite{AJ25}. These are arithmetic size bounds, with arbitrary field constants at unit cost, including over $\Q$. Over finite fields, combining the formula construction with~\cite{AJ22} gives randomized polynomial-time complete factorization of formula inputs, with factors output as formulas. For polynomial-degree circuit inputs, we obtain polynomial-length succinct ABP descriptions with polynomial-time edge queries. We also give two algorithms that output complete ordered irreducible factorizations as polynomial-size circuits: a deterministic $\FP^{\SigTwo}$ algorithm and a zero-error randomized algorithm with an NP oracle and expected polynomial running time.

Andrews, Garg, and Schost (FOCS~2026) recently, in a breakthrough result, placed Hilbert's Nullstellensatz (HN) in the Counting Hierarchy ($CH$) using constant-depth circuits for multivariate resultants. While HN deals with exact polynomial satisfiability, Guo, Saxena, and Sinhababu (CCC~2018; Theory of Computing~2019) introduced approximate polynomial satisfiability (APS) as a natural approximative analogue of polynomial system satisfiability. They proved its ${NP}$-hardness and a $PSPACE$ upper bound, and used APS to construct hitting sets for $\overline{{VP}}$ in polynomial space, substantially narrowing the GCT chasm in geometric complexity theory. We place APS in the Counting Hierarchy for rational polynomials given by arithmetic circuits. Our proof combines Noether normalization with a geometric restriction on how points in the image of a polynomial map approach the origin, reducing APS to a test on multivariate resultants which allows solvability in $CH$. It complements the independent and concurrent proofs of Balaji, Shirmohammadi, Tavenas, and Worrell, and Andrews, Garg, Oliveira, and Schost. Moreover, we also place integral closure membership testing in the Counting Hierarchy. Here, the question is whether a given polynomial $f$ is integral over $\mathbb{C}[f_1,\ldots,f_m]$. Our approach uses a global annihilator criterion and an effective degree bound to reduce non-integrality to APS in polynomial time. In fact, we show that the reduction holds both ways, and Integral Closure Membership Testing is equivalent to APS under polynomial-time reductions.

This note is an exposition of the recent preprints from OpenAI that establish the bound $\omega \leq 9/4$ on the matrix multiplication exponent. We argue that the heart of these preprints is a new technique, which we formulate as the untwisting lemma for semidirect sums of tensors. This gives a generally applicable method for analyzing tensors. We also discuss further consequences of this method, as well as the relation between the OpenAI proof and previous work.

We study depth-$4$ algebraic circuits with bounded top and bottom fan-in over fields of characteristic $0$. These circuits compute sums of at most $k$ products of polynomials of degree at most $\delta$. We denote this class of circuits by $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$. Our hard polynomial for this class is $P_{k + 1,n}$, the sum of $k + 1$ monomials of degree $n$ on disjoint sets of variables. It can be computed by a depth-$3$ circuit of top fan-in $k + 1$ and size $O(kn)$. We give an impossibility result showing that for all constants $k$ and $\delta$ and all sufficiently large $n$, no $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuit computes $P_{k + 1,n}$. For $k \geq 2$ and $\delta = 2$, this follows implicitly from the rank bound for $\Sigma^{[k]}\Pi\Sigma\Pi^{[2]}$ identities of Garg, Oliveira, Sengupta, Shalmon, and Shpilka (CCC 2026). To the best of our knowledge, this impossibility result was not known even for $k \geq 2$ and $\delta = 3$. We also turn to border complexity, a notion central to geometric complexity theory, in which a polynomial only needs to be approximated arbitrarily well. Here impossibility fails over algebraically closed fields: Kumar (TOCT 2020) showed that $\overline{\Sigma^{[2]}\Pi\Sigma}$ circuits already approximate every polynomial, albeit with exponential size. In turn, we show that every $\overline{\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}}$ circuit computing $P_{k + 1,n}$ must have size $2^{\Omega(n)}$ when $k$ and $\delta$ are constants, in stark contrast to the exact depth-$3$ circuit of top fan-in $k + 1$ and size $O(kn)$. This lower bound gives an exponential top fan-in hierarchy for border depth-$4$ circuits of bounded bottom fan-in and answers the main open question of Dutta and Saxena (FOCS 2022, JACM 2026), who gave an analogous hierarchy for the case $\delta = 1$, i.e., depth $3$. Along the way, we develop tools for border depth-$4$ circuits that apply to arbitrary polynomials and may have further applications.

Authors: Noah Fleming, Mika Göös, Ziyi Guan, Oliver Korten, Daniel Mitropolsky, Toniann Pitassi, Artur Riazanov, Dmitry Sokolov, Tianqi Yang, Weiqiang Yuan

We determine which major $\TFNP$ classes are hard in the random oracle model (ROM). Prior work establishes average-case hardness of highly structured subclasses of $\TFNP$ from strong cryptographic assumptions such as LWE and indistinguishability obfuscation. It is not known whether weaker assumptions such as one-way functions imply hardness of any of the standard $\TFNP$ subclasses, even in the worst case. The ROM, where all parties have query access to a random function, lies, morally, between these two regimes: a random function is one-way, but public-key cryptography cannot be built from it in a black-box way. We refer to this setting as \emph{Romantica}. Our first result settles a long-standing open problem: $\PPAD$, the class of total search problems reducible to finding a Nash equilibrium, is hard on average in Romantica. Combined with the known hardness of PLS (local search), this gives average-case hardness of $\EoPL = \PPAD \cap \PLS$. In contrast, we show that $\UEoPL$ can be solved in Romantica with polynomially many oracle queries by a computationally unbounded solver, a sharp distinction between $\EoPL$ and $\UEoPL$. This resolves the black-box hardness landscape of all major $\TFNP$ classes in Romantica. Finally, we initiate the study of separations between $\TFNP$ subclasses in Romantica: $\PWPP$ and $\PPA$ do not reduce to $\PLS$ under \emph{public-coin} reductions.

Authors: Eli Goldin, Alex Lombardi, Tomoyuki Morimae

We consider the complexity implications of proofs of quantumness and (quantum verifier) oblivious state preparation. We show that both of these objects can coexist with the easiness of nondeterministic computation. That is, we give evidence that proofs of quantumness can exist when $\mathsf{P} = \mathsf{NP}$ and that (quantum verifier) oblivious state preparation can exist when $\mathsf{BQP} = \mathsf{QCMA}$. In particular, we give a classical oracle relative to which (1) $\mathsf{P}^\mathcal{O} = \mathsf{NP}^\mathcal{O}$ (2) $\mathsf{BQP}^\mathcal{O} = \mathsf{PSPACE}^\mathcal{O}$ (3) Proofs of quantumness exist. In particular, there exists a language in $\mathsf{IP}^\mathcal{O} \subseteq \mathsf{BQP}^\mathcal{O}$ which is hard on average against $\mathsf{P}^\mathcal{O}/poly$. We give a unitary oracle such that (1) $\mathsf{BQP}^\mathcal{O} = \mathsf{QCMA}^\mathcal{O}$ (2) Quantum verifier oblivious state preparation exists. These oracle separations directly imply a number of related consequences. For example, our first result implies that proofs of quantumness cannot be used to construct classical or quantum cryptography with a relativizing proof. Our second result implies that quantum computation/classical communication oblivious transfer cannot be used to construct post-quantum one-way functions with a relativizing proof.

Authors: Parikshit Gopalan, Manoj Prabhakaran, Pranay Tankala

We prove a broad learning-theoretic generalization of the celebrated hardcore lemma concerning the average-case complexity of computing a Boolean function (Impagliazzo, 1995). Our starting point is the observation that the classic notion of a hardcore measure, which reweights a function's input distribution, is equivalent to an input-dependent masking channel that injects randomness into the function's output distribution until it appears fully pseudorandom. The analogue of density of the measure is the fidelity of the channel. From this viewpoint, we develop a general framework for certifying hardness that allows for non-Boolean functions $f$ and a wide range of notions of hardness besides the classic 0-1 loss, by choosing the right notion of fidelity via convex duality. We show the difficulty of learning $f$ using a class $\mathcal{C}$ to minimize a convex loss is tightly characterized by the maximum fidelity possible for a masking channel, which measures the least amount of noise the channel must add to hide the structure of $f$ and make it $\mathcal{C}$-indistinguishable from random noise. Using our framework, we derive a number of multiclass generalizations of the hardcore lemma, and reveal some unexpected subtleties in going to larger alphabets. We construct a universal masking channel that applies to many natural notions of hardness simultaneously. Such channels are dual to omnipredictors, which optimize multiple losses at once (Gopalan, Kalai, Reingold, Sharan, and Wieder, 2022). We observe a symmetry between masking channels and generalizations of the hardcore lemma using pseudoentropy. We present a tight characterization of pseudoentropy using the MaxEnt algorithm from machine learning. A long line of research has shown that learning and hardness are two sides of the same coin; our framework gives a crisp and general formulation of this principle via convex duality.

Authors: Robert Andrews, Abhibhav Garg, Rafael Oliveira, Éric Schost

The problem of decomposing an algebraic variety into more structured components (such as equidimensional, irreducible, or connected components) is a fundamental problem in computer algebra and algebraic geometry. In this work, we study the computational complexity of computing equidimensional components of algebraic varieties, represented via Chow forms. We improve the state-of-the-art complexity bounds from PSPACE to CH, the counting hierarchy, for a number of problems related to equidimensional decomposition, including deciding (1) whether the Chow form of the $k^{\text{th}}$ equidimensional component of a given projective variety vanishes at a given point, (2) whether a given monomial is in the support of the Chow form of the $k^{\text{th}}$ equidimensional component of a given projective variety, (3) membership in a given equidimensional component of a given algebraic variety, and (4) membership in the closure of the image of an irreducible variety under a polynomial map. As an application of our algorithm to decide membership in the closure of the image of a variety under a polynomial map, we show that the approximate polynomial satisfiability problem can be decided in CH. We also show that the degree of the $k^{\text{th}}$ equidimensional component of a given projective variety can be computed in $\text{FP}^{\text{CH}}$. Our main technical result is the construction of a polylogtime-uniform family of constant-depth, exponential-size threshold circuits that compute the Chow forms of the equidimensional components of a given projective variety. We construct these circuits by combining the machinery of geometric resolutions together with the uniform constant-depth, exponential-size threshold circuits of Andrews, Garg, and Schost (FOCS 2026) for the multivariate resultant.

Authors: Dmitriy Kunisky, Xifan Yu

We study the degree needed for sum-of-squares (SoS) proofs of several basic principles of real linear algebra. For any $n\times n$ matrix $A$ of rank greater than $r$, the Weak Rank Principle states that the equations $XY^\top=A$ with $n\times r$ matrix variables $X, Y$ have no solution. We show that this principle requires degree exactly $2r+2$ to prove. On the other hand, for $A=I_n$, setting $X = Y$ gives the Tight Frame Principle, which has a degree-$4$ proof. For $n\times n$ matrices, proving that a right inverse is also a left inverse requires degree exactly $2n+2$, while proving that orthonormal rows imply orthonormal columns again has a degree-4 proof. Using our lower bounds, we also derive related SoS degree lower bounds for polynomial systems encoding sign rank, matrix rigidity, small-width homogeneous non-commutative algebraic branching programs, and tensor CP rank. Lastly, we show that quantitative bounds on the Frobenius norms of the factors in the Weak Rank Principle can lower the degree required to refute $XY^\top=I_n$, but sufficiently large bounds still preserve the exact degree $2r+2$ from the unbounded case, giving a quantitative version of the Archimedean property arising in classical results on SoS proofs.

Authors: Andrew D. Lin

A \emph{rainbow cycle} in a list-edge-colored graph is a cycle where no color appears more than once. We give a short and simple proof of a result of [ABSZZ] showing that a properly edge-colored $n$-vertex graph with average degree $Ω(\log n\log\log n)$ always contains a rainbow cycle, and generalize it to weighted graphs with edges list colored with list size at most $\ell$ and where the total weight of all edges containing a given color $i$ incident to a vertex is at most $Δ$, showing that $Ω_\ell(Δ\log n\log\log n)$ average degree guarantees a rainbow cycle. Using the reduction of [AG26] and the new generalized rainbow cycle theorem, we prove that for $r\geq 3$, every binary linear $r$-query locally correctable code $E:\mathbb{F}_2^k\rightarrow \mathbb{F}_2^n$ satisfies $k\leq \tilde{O}(n^{1-2/(r-1)})$ by showing a rainbow analogue of the odd $r$-LDC lower bounds of [BHKL25,JM25], closing the gap between the best known lower bounds for odd- and even-query binary linear $r$-LCCs.

Authors: Geoffroy Couteau, Nikolas Melissaris, Thejas Radhika Sajith

We study the possibility of basing fine-grained cryptography on the hardness of fundamental problems in linear algebra. Our main technical contribution is a hardness self-amplification method based on random low-rank updates: we show how to turn an algorithm that solves an inverse-polynomial fraction of random linear systems into a solver which succeeds for every right-hand side of almost every matrix. Our reduction increases the runtime only linearly in the inverse of the original success probability. In particular, this yields fine-grained one-way functions from the almost worst-case hardness of linear systems over large enough fields. Using the same approach, we also obtain tighter worst-case to average-case reductions for matrix multiplication and online matrix-vector multiplication, as well as variants of our reductions that recover exact solutions from approximate algorithms, whose expected coordinate agreement is only $1/q+\varepsilon$, with inverse-quadratic dependence on $\varepsilon$ up to logarithmic factors, over every finite field. Finally, we also use it to connect the existence of fine-grained key agreement to the problem of computing the rank of a matrix: over a suitable sequence of growing characteristic-two fields, the almost-everywhere average-case hardness of rank computation (for any of a large class of distributions) implies infinitely-often fine-grained key agreement.

Authors: Guy Goldberg, Tom Gur, Sidhant Saraogi

We prove a nearly optimal lower bound on the blocklength of general relaxed locally decodable codes (RLDCs), extending the result of [GGS26] to nonlinear encodings and adaptive decoders with two-sided error. Namely, we show that any $q$-query RLDC $C\colon \{0,1\}^k \to \{0,1\}^n$ must satisfy $n = k^{1+Ω(1/q)}$, closely matching the upper bound of $n = k^{1+O(1/q)}$ by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004). Our proof reduces showing RLDC lower bounds to estimating the output distribution of adaptive decoders. To this end, we introduce a capped Horvitz--Thompson estimator with uniformly bounded discrete derivatives on the $p$-biased cube. We establish its concentration of measure via self-bounding inequalities and control the downward bias induced by capping through a spreadness argument.

Authors: Yiyang Huang, Zhengyang Liu, Yonglei Yan

Autobidding equilibria link advertisers' value multipliers or participation probabilities through aggregate budget and return-on-investment (ROI) constraints. We establish the exact computational complexity of finding these equilibria across several canonical settings: exact equilibrium computation is $\mathsf{FIXP}$-complete for second-price ROI pacing, budget- or ROI-constrained generalized second-price (GSP) sponsored shopping, and second-price throttling. Furthermore, approximating the equilibrium control vector in distance to a true equilibrium is $\mathsf{FIXP}_{a}$-complete when the target accuracy is provided as input.

Authors: Adam Husted Kjelstrøm, Jaco van de Pol, Andreas Pavlogiannis

Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific hardware. A related problem is approximate membership: for a fixed set of unitaries $S$, decide whether a given circuit $C$ is within distance $\varepsilon$ of a unitary in $S$ under some metric $m$. Membership is a special case of optimization, where $S$ is a set of unitaries implementable at no cost (e.g., with noise-minimal circuits, or without magic states). Janzing, Wocjan, and Beth (Int. J. Quantum Inf., 2005) showed that, for the operator metric, the case $S=\{I\}$ (approximate identity) is QMA-complete when $C$ is promised to be either close to the identity or far from it. We generalize this setting in three directions: (i) promise-free inputs, (ii) besides $S=\{I\}$, sets $S$ containing only Clifford unitaries, or only generalized permutation matrices (i.e., no superposition), and (iii) the trace-based, spectral, and operator metrics. We show that, in all cases, approximate membership is PP-hard for wide ranges of $\varepsilon$, provided $C$'s gate-set can implement Clifford+T, as the gate-sets of standard hardware do. If $S=\{I\}$, or if $S$ contains only generalized permutation matrices, $I\in S$, and $m$ is a trace-based distance, PP-hardness holds for all non-trivial $\varepsilon$. If $S=\{I\}$ and $m$ is a trace-based distance, PP-hardness holds even for circuits over classical-reversible gate-sets. Our results indicate that approximate membership is harder over promise-free inputs than the QMA-complete promise version, and that this hardness persists across quantum resources (any gates, non-Clifford, superposition) and distance metrics. They directly imply PP-hardness of circuit optimization when minimizing total, non-Clifford, or superposition gate depth or count.

Authors: Xiaoyang Liu

A closed path can return to its starting point while analytic continuation reaches another branch. We construct a finite computational calculus in which retained logarithmic branches supply memory, analytic observations select operations, and descent through a covering exposes deeper memory. Three branch coordinates suffice, and every finite observation uses the same cubic power covering. Each program defines a globally real analytic return map whose integer-lattice execution is realized by actual path lifting. Our first theorem simulates every finite-alphabet, finite-control Post--Turing machine, preserving complete configurations, halting, and divergence. Our second theorem identifies the partial numeric functions of the calculus, under fixed primitive-recursive input and output maps, with exactly the partial recursive functions. Deleting descent leaves a Forward language with a syntax-derived finite observation quotient and a primitive-recursive halting predicate. This yields a strict separation within the calculus and identifies access to deeper memory as its decisive additional operation. The constructions and semantic correspondences are formalized in Lean 4 with Mathlib.

Authors: Ioannis Anagnostides, Ioannis Panageas, Jingming Yan

The geometry of constraints in variational inequalities (VIs) plays a central role in applications ranging from resource allocation and equilibrium computation to constrained optimization. Yet, its effect on computational complexity has received surprisingly little attention beyond special cases. We examine this question when the constraint set is an $\ell_p$ ball. This family of problems encompasses two of the most extensively studied classes of problems in algorithmic game theory: symmetric bimatrix games for $p = 1$ and multi-player polymatrix games for $p = \infty$. Both of these problems are known to be PPAD-complete even for affine operators. We establish a comprehensive complexity landscape for VIs over $\ell_p$ balls across the full range $p\in[1,\infty]$. First, for any $p\neq 2$, we show that finding an inverse-polynomial approximate VI solution is PPAD-complete even for affine operators. In contrast, for $p=2$, we give a polynomial-time algorithm for affine VIs, extending a classic result of Ye (1992) beyond symmetric operators. On the other hand, once the operator becomes quadratic, we establish PPAD-completeness even at inverse polynomial precision. From a technical standpoint, we develop a new toolkit for exploiting the geometry of the constraint set and the structure of the operator to characterize the complexity of equilibrium and optimization problems, which is of independent interest.

Authors: Alexander Hoover, Giuseppe Persiano, Kevin Yeo

Information-theoretic MPC among $n$ parties with $t$ corruptions can securely evaluate a circuit $C$ with $O(|C| \cdot t/(n-t))$ online communication in the preprocessing model and $O(|C| \cdot t/(n-2t))$ communication in the honest majority setting. Damgård, Larsen and Nielsen (CRYPTO 2019) showed that both communication bounds are tight for inner products. Fully homomorphic encryption and other assumptions known to imply public-key cryptography beat both communication bounds, but the communication complexity with symmetric-key cryptography alone is less understood. For MPC with preprocessing, we prove that the same $Ω(|C| \cdot t/(n-t))$ lower bound holds in the random oracle model, so a random oracle cannot reduce the online communication. For honest majority MPC relative to a random oracle, we present an $Ω(|C|)$ communication lower bound that is matched by a new construction for degree-2 polynomials (including inner products) when $n = O(\log λ)$, beating the information-theoretic bound. We also study quantum MPC. First, we prove that information-theoretic protocols with quantum communication (and preprocessing) cannot reduce communication compared to their classical counterparts. Furthermore, we extend our lower bound for MPC with preprocessing to protocols with a quantum-accessible random oracle, but use only classical communication. In contrast, with both quantum communication and a post-quantum one-way function, we present a simple two-party protocol that evaluates the two-party instance of these circuits with $\mathrm{poly}(λ, \log |C|)$ communication, beating these lower bounds. Finally, such communication savings do not come for free. We prove that there exist circuits $C$ such that every blackbox protocol with $o(|C|)$ quantum communication must perform $Ω(|C|)$ cryptographic operations.

Authors: Argyrios Deligkas, Michail Fasoulakis, Stavros D. Ioannidis

Computing a Karush-Kuhn-Tucker (KKT) point of a quadratic polynomial over the unit hypercube is known to be $CLS$-complete, when the coefficients of the polynomial are encoded in binary. We prove that the problem remains $CLS$-complete even when the coefficients are encoded in unary. This is the first problem proven to remain $CLS$-hard when the input is given in unary.

Authors: Oswin Aichholzer, Joseph Dorfer, Peter Kramer, Christian Rieck, Birgit Vogtenhuber

We study the problem of reconfiguring plane, straight-line spanning trees on point sets in the plane. A flip is a reconfiguration step in which one edge of a tree is replaced with another, yielding again a plane spanning tree. For a given point set $P$, the flip graph has a vertex for each plane spanning tree on $P$, and an edge between any two trees that differ by a single flip. The folklore happy edge conjecture suggests that any edge shared by both the initial and the target tree (a happy edge) is never flipped in a shortest flip sequence. This conjecture was computationally verified for up to 10 points in convex position. In this paper, we disprove this conjecture both on general point sets and on point sets in convex position by providing two counterexamples on $16$ and $30$ points, respectively. The counterexample for point sets in general position also holds for compatible flips, while the happy edge property holds for compatible flips in convex point sets as shown by Aichholzer, Dorfer, and Vogtenhuber [GD 2025].

Authors: Erik D. Demaine, Toshihiro Shirakawa, Conner Silverstein, Reed Silverstein, Michael Tardibuono, Ryuhei Uehara

We present new results on polyomino nets that fold into four or five distinct boxes. With the help of AI, we first found examples with areas 532 and 2128, respectively. We analyze these examples and reduce their areas to 178 and 358, respectively. We also generalize the construction of the five-box net and show that infinitely many polyomino nets fold into five distinct boxes.

Authors: Arjan Cornelissen, Amin Shiraz Gilani, Shiva Kintali, François Le Gall, Subhasree Patro, Xingyu Zhou

In the graph collision problem, the task is to decide whether a known graph on $n$ vertices contains an edge with both endpoints marked, given query access to the input bits specifying the marked vertices. We first refute the conjectured $Ω(n^{2/3})$ query lower bound with a bounded error quantum algorithm using $\widetilde O(n^{92/139})$ queries. We then refine this approach to obtain a $\widetilde O(n^{11/17})$ query algorithm. We also obtain a $\widetilde O((nq)^{11/17})$ query bound for all (partial) Boolean output functions with positive certificate complexity at most 2 and alphabet size $q$, contrasting a known $Ω(n^{2/3})$ lower bound for such problems with large alphabet sizes. We complement these algorithms with an $Ω(\sqrt{n\log n})$ quantum query lower bound for graph collision, exceeding the $O(\sqrt n)$ certificate complexity barrier for the positive adversary method.

Authors: Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold, Konstantinos Stavropoulos, Pranay Tankala

Given a class of machine learning models and sample access to a data distribution with binary labels, which computational task is harder: training a discriminative model that distinguishes positive and negative labels as well as the best member of the class, or training a generative model whose outputs are indistinguishable from real data by all members of the class? We prove that these two fundamental tasks in computational learning theory are not just closely related, but actually equivalent to each other in complexity. One direction of this equivalence was previously known. Indeed, the powerful regularity lemma in complexity theory gives an efficient oracle reduction from the indistinguishability task (a.k.a. multiaccuracy) to the distinguishing task (a.k.a. agnostic learning) in the style of boosting algorithms. Our main contribution is an efficient oracle reduction in the other direction. Taking this idea further, we show that a multiaccuracy oracle is a remarkably powerful primitive, achieving not just agnostic learning but also a wide range of seemingly more demanding learning objectives via similarly efficient and direct constructions. Our results crucially use the power of making adaptive queries to the oracle, and stand in stark contrast to prior work, which showed that post-processing a single multiaccurate predictor is insufficient for even weak forms of learning. On a technical level, we draw a connection between our (offline) problem and a version of no-regret learning in the online setting, which allows us to use follow-the-leader type algorithms to modify the label distribution and aggregate the predictions of the multiaccuracy oracle.

Authors: Josh Alman, Baitian Li, Neha Pant, Kevin Pratt, Ryan Williams

We show that for any fixed $k$, there exists $\varepsilon_k > 0$ such that, given a $(k-1)$-uniform hypergraph $H$ on $n$ vertices, one can count the number of $k$-hypercliques in $H$ in $O(n^{k-\varepsilon_k})$ time. This refutes the hyperclique conjecture of Lincoln, Vassilevska Williams, and Williams (SODA 2018). Our result follows from the uniform construction of a family of arithmetic circuits of size $O(n^{k-\varepsilon_k})$ for the $k$-hyperclique tensor, a natural higher-order generalization of the matrix multiplication tensor. We obtain two corollaries. First, for every $k$, there exists $\varepsilon > 0$ such that Max-$k$SAT can be solved in $2^{(1-\varepsilon)n} \cdot \mathrm{poly}(m,n)$ time. Second, for every $k$, there exists $\varepsilon > 0$ such that arithmetic progressions of length $k$ in subsets of $\{0,1,\ldots,n\}$ can be detected in $n^{2-\varepsilon}$ time. Both corollaries refute other prominent conjectures in the literature.

Authors: Zimai Guo, Cheng Hong, Zhechen Li

In this paper, we study exact online integer priority queues under differential obliviousness in the balls-and-bins model. Given a public upper bound $T$ on the number of operations and assuming that the priorities are bounded by a polynomial in $T$, we construct an $(\eps,δ)$-differentially oblivious priority queue supporting insertion and minimum extraction, which requires $\polylog(T)$ private memory. For constant $\varepsilon>0$ and $δ=\exp(-Θ(\log^2 T))$, our construction incurs $O(\log T/\log\log T)$ expected amortized total work per operation, which breaks the $Ω(\log T)$ barrier for fully oblivious priority queues~[Jacob et al., SODA'2019]. Further, we prove a matching lower bound for $(\eps,δ)$-differentially oblivious priority queues with $\varepsilon=O(1)$ and $δ=o(1)$, which indicates that our construction is asymptotically optimal in terms of total work.

Authors: Tamio-Vesa Nakajima, Zephyr Verwimp, Stanislav Živný

We study the following family of search problems: given a system of equations $x+y+z\equiv 0\pmod p$ promised to admit a solution that is nonconstant on every equation, find a $c$-colouring of the variables that makes no equation monochromatic. For $p\in\{2,3\}$, the problem recovers known tractable Promise Constraint Satisfaction Problems (PCSPs). For $p > 3$, we obtain a complete complexity classification: the problem is polynomial-time solvable for $c \geq 4$, yet even its decision version is NP-hard for $c = 3$, and it is not well-defined for $c = 2$. Our main conceptual contribution is a general tractability framework for PCSPs based on Abelian embeddings, a notion introduced by Bhangale, Khot, and Minzer [STOC 2022] in the study of quantitative approximation of satisfiable CSPs. We show that suitable Abelian embeddings yield polynomial-time PCSP reductions realised by singleton algorithms in the sense of Zhuk [FOCS 2026]. On the hardness side, the promise relation is far removed from the reconfigurable regime covered by the conditional hardness framework of Banakh, Barsukov, and Nakajima [LICS 2026]; our proof instead relies on a new additive-combinatorial rigidity theorem classifying special $3$-colourings of $\mathbb{Z}_p$.

Authors: Alexandru Popa

The vertices of a Boolean birthday graph are partial assignments on $\ell$-subsets of $n$ variables. Although a satisfying assignment induces a $K$-clique for $K=\binom n\ell$, an arbitrary selection of $K$ vertices may repeat some views and omit others. This makes soundness substantially harder than under uniform view sampling. For bounded-occurrence, constant-gap Boolean ternary CSPs whose constraints each involve three distinct variables (allowing arbitrary Boolean predicates), we prove that the graph's maximum induced $K$-vertex density satisfies \[ ρ^*(K)\le 2\exp\!\left(-c\, \frac{\ell^3}{n^2\log(en/\ell)}\right) \] for $2\le\ell\le x_0n$ and $\ell\log(en/\ell)\ge C_0\log(n+1)$, with positive constants depending only on the source parameters. The argument refines the biclique counting method by charging the entropy of an adversarially chosen flattening to mutual information and a combinatorial obstruction energy. In the overlapping parameter range it strengthens the explicit soundness exponent previously established for this graph. We also establish an unconditional stability theorem for arbitrary sets $H$ of exactly $K$ distinct local assignments, with missing views and multiple answers: $f_*(H)\le34(n/\ell)q_{\mathrm{con}}(H)$ for every $1\le\ell\le n$. It gives a complementary additive near-clique soundness bound. We do not derive a new fine-grained hardness theorem.

Authors: L. Sunil Chandran, Rishikesh Gajjala

Binary prefix coding assigns prefix-free binary words to symbols to minimize their frequency-weighted cost. Huffman solved the equal-letter-cost case in polynomial time in 1952 [Proc. IRE'52]. For unequal letter costs, Karp gave an integer-programming formulation in 1961 [IRE Trans. Inf. Theory'61]. Exact polynomial-time algorithms for fixed integer costs were given by Golin and Rote [IEEE Trans. Inf. Theory'98] and Bradford, Golin, Larmore, and Rytter [J. Algorithms'02]. For input-dependent costs, Golin, Mathieu, and Young gave a polynomial-time approximation scheme [SICOMP'12]. The exact complexity when letter costs are part of the input had remained unresolved. We resolve this $65$-year-old problem by proving that deciding whether there exists a binary prefix-free code of frequency-weighted cost at most a given threshold is NP-complete, even when the letter costs are consecutive positive integers $(M,M+1)$ supplied as part of the input. All frequencies, letter costs, and thresholds are encoded in binary. Consequently, finding an optimal code is NP-hard. Our proof uses two polynomial-time reductions, starting from Planar Independent Set. The intermediate problem prescribes the number of leaves at each depth of a full ordered binary tree and minimizes a signed linear score on their sorted right-edge counts. The first reduction represents an independent-set verification program by a tree growing level by level. A fixed-profile identity converts narrow coordinate restrictions into linear penalties that enforce the computation. The second reduction adds large dyadic terms to the symbol frequencies to force prescribed depths. These terms contribute a constant to the weighted number of ones, leaving smaller signed perturbations to reproduce the tree score.

Authors: Zemin Chao, Jianhe Cen, Hengzhao Ma, Hongzhi Wang

We characterize the optimal space for one-pass spanning-forest computation in dynamic streams of $v$-vertex simple graphs with failure probability at most $δ$. Nelson and Yu proved an $Ω(v\log^2v\log(v/δ))$-bit lower bound, establishing the AGM algorithm's optimality for each fixed $0<ε<1$ and $2^{-v^{1-ε}}<δ\le1/4$. We resolve the remaining high-confidence regime: for every $0<δ\le1/4$, matching lower bounds and an algorithm give \[ Θ\!\left(\min\left\{v^2,\;v\log(v/δ)\log^2\!\left(2+\frac{v}{\log(v/δ)}\right)\right\}\right) \] bits, improving space by up to a factor of $Θ((\log v/\log\log v)^2)$ in this regime. We also study streams with at most $Z$ previously inserted edges deleted and not yet reinserted at report time, where the integer $Z\ge0$ is given in advance. Total deletions, restorations, and intermediate absence counts are unrestricted. For a single report and every $0<δ\le1/4$, matching lower bounds and a one-pass randomized algorithm yield optimal space $Θ(\mathcal L(v,Z,\log(1/δ)))$ bits, where $x_Z(t)=\min\{Z+1,v,\sqrt{vt}\}$ and \[ \mathcal L(v,Z,t)=v\log v\min\{\log^2v,\log^2(Z+2)\} +vt\log\!\left(1+\frac{x_Z(t)}t\right)\log\!\left(1+\frac v{x_Z(t)}\right). \] At zero error, a lower bound for all zero-error algorithms and a matching deterministic algorithm give optimal space \[ Θ\!\left(\min\{v^2,v(Z+1)\log(1+v/(Z+1))\}\right) \] bits. Together, these results characterize the memory required across all confidence levels and report-time edge-loss bounds.

Authors: Jianan Zhang, Shuangping Li

The binary perceptron is a random constraint satisfaction problem that asks for a sign vector satisfying a system of random linear inequalities. Its solution space has a strikingly extreme geometry: at every positive constraint density, all but a vanishing fraction of the solutions are isolated. Yet polynomial-time algorithms find solutions at small enough constraint density, which raises the question of how efficient algorithms navigate such a landscape. Linear programming is a natural algorithm to study here, but its analysis has so far been limited to a single round. Li, Schramm, and Zhou (STOC 2025) analyzed one linear program followed by iterative rounding. In this work, we overcome this limitation and give a precise analysis of iterated linear programming for the binary perceptron. (1) For Gaussian matrices and any fixed number of rounds, we characterize the iterated linear programs exactly through a deterministic state-evolution recursion. (2) Adding a final rounding step, we obtain a randomized polynomial-time algorithm for the binary perceptron. Numerical evaluations of the recursion provide evidence that it succeeds at constraint density $α=0.60$ with zero margin, well beyond the range $α\le0.1$ guaranteed by the single-LP analysis and $α\approx0.327$ (Jo and Lee, 2026), the best guarantee so far. (3) We establish universality, showing that the same characterization holds for matrices with i.i.d. entries drawn from any centered, unit-variance subgaussian law. The key idea of our proof is that, although conditioning on earlier rounds makes the matrix non-Gaussian, its conditional law can be computed explicitly and remains close to a Gaussian law, so the convex Gaussian min-max theorem applies in every round. For universality, we compare Gaussian and subgaussian matrices through the Lindeberg principle, using a regularized version of each linear program.

Authors: Baitian Li

This note is an exposition of the recent preprints from OpenAI that establish the bound $ω\leq 9/4$ on the matrix multiplication exponent. We argue that the heart of these preprints is a new technique, which we formulate as the untwisting lemma for semidirect sums of tensors. This gives a generally applicable method for analyzing tensors. We also discuss further consequences of this method, as well as the relation between the OpenAI proof and previous work.

Authors: Robinson D. H. Cung, Adway Girish, Emre Telatar

We study statistical inference and function evaluation problems in which the input binary vector is available only through a binary linear sketch, i.e., a fixed number of parity measurements. We show that under a certain monotonicity condition, simply truncating the input by retaining a subset of its coordinates is optimal among all linear sketches of the same size. In particular, this applies to distributed testing of correlations of binary vectors when they are of opposite signs and evaluating unate Boolean functions on uniformly random inputs. Additionally, given that truncation is optimal, we immediately have lower bounds for arbitrary binary linear sketches. To illustrate this application, we consider the one-way communication complexity of a distributional graph connectivity problem on $n$ vertices and show that truncation, and hence all binary linear sketches, requires $Θ(n \log n)$ bits to achieve constant error, while a nonlinear protocol only requires $O(\log n)$ bits.

Authors: Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande

A tournament is an orientation of a complete graph. A vertex $v$ controls a vertex $u\neq v$ if there is a directed path of length at most two from $v$ to $u$, and a $δ$-king is one that controls at least $δ(n-1)$ vertices. In the query complexity model, each query reveals the orientation of an edge. Shen, Sheng and Wu [SICOMP'03] established an $Ω(n^{4/3})$ lower bound on the deterministic query complexity of finding a $1$-king, and a non-matching upper bound of $O(n^{3/2})$. Neither bound has been improved in over two decades, despite substantial progress on variants of the problem. For $δ$-kings with $δ< 1$, Biswas, Jayapaul, Raman and Satti [Discrete Applied Mathematics'22] showed that $O(n^{4/3})$ queries suffice to find a $\frac12$-king. Lachish, Reidl and Trehan [FSTTCS'22] improved this guarantee to $\frac12+\frac{2}{17}$ using $\widetilde{O}(n^{4/3})$ queries, and asked whether a larger fraction could be achieved within the same query bound. We answer this question affirmatively for every fixed fraction below one: for every fixed $\varepsilon\in(0,1)$, we give a deterministic algorithm that finds a $(1-\varepsilon)$-king using $O(n^{4/3})$ queries. The design of our algorithm is informed by a structural analysis combining a sparse regularity lemma due to Allen, Kohayakawa, Mota and Parente [Electronic Journal of Combinatorics'14] with a new sampling argument based on a reachability theorem of Afek, Gafni and Linial [arXiv'19].

Authors: Da Wei Zheng, Daniel Prigan

We give an improved algorithm for weighted directed planar diameter that runs in $\widetilde{O}(n^{3/2})$ time. This improves upon the $\widetilde{O}(n^{5/3})$ time algorithm for weighted directed planar diameter of Gawrychowski, Kaplan, Mozes, Sharir, and Weimann [SIAM J. Comput. 2021] and the recent $\widetilde{O}(n^{8/5})$ time algorithm for unweighted undirected planar diameter of Fredslund-Hansen, Mozes, and Weimann [SOSA 2027]. The main new result is an improved data structure for computing the farthest vertex when given feasible planar distances to the vertices on the outer face. The critical insight is the fact that normalized distances to the vertices of a face behave like pseudolines, for which we can leverage range searching and upper envelope data structures. Using the farthest vertex data structure, we are able to compute all vertex eccentricities and diameter in $\widetilde{O}(n^{3/2})$.

Authors: Lucas de Oliveira Silva, Elisa Dell'Arriva, Flávio Keidi Miyazawa

We study the geometric bin packing problem for simple polygonal regions, i.e., non-degenerate, connected, rational regions, in the minimum number of unit-square bins, allowing only translations. We even consider packing general non-convex objects, possibly with holes, where we can then pack smaller objects. Previous schemes cover squares (MOR'06), circles and other $L_p$-balls (Algorithmica'16), sufficiently skewed rectangles (Algorithmica'23), and convex fat objects with a constant number of distinct shapes under resource augmentation (arXiv'24, WAOA'23). The result for circles and other $L_p$-balls needs bin augmentation to obtain rational packing realizations. For restricted classes of $L$-shaped polygons, Gerlach et al. (SoCG'26) give constant worst-case guarantees, while for general non-convex objects, bounding-box reductions give just approximation factors that depend on fatness. Against this background, we present a general framework that provides asymptotic polynomial-time approximation schemes (APTAS) for bin packing of any fixed class of simple polygonal regions satisfying just two assumptions. First, covering any object by the grid cells intersecting its interior in any sufficiently fine square grid, relative to the object's bounding box, increases its area by at most a small fraction. Second, the class can be partitioned into a constant number of sequences such that each object in a sequence can be translated to fit inside every preceding object. In particular, certain classes of star-shaped polygons and more general polygonal regions, including some with simple holes, satisfy both assumptions. In addition, our framework does not require a bound on the objects' boundary complexity. We emphasize that our results require no bin augmentation whatsoever and yield explicit, exact rational packings of polynomial encoding length for all input objects.

Authors: Shiri Chechik, Gur Lifshitz

We study approximation algorithms for All-Pairs Shortest Paths (APSP) in directed graphs under the roundtrip metric. In directed graphs, even finite-factor approximation of ordinary one-way distances must distinguish reachable from unreachable vertex pairs, and therefore computes transitive closure, a problem equivalent to Boolean matrix multiplication (BMM) under standard reductions. The roundtrip distance, defined as $\text{dist}_G(u \leftrightarrows v) = \text{dist}_G(u \to v) + \text{dist}_G(v \to u)$, offers a natural and robust relaxation. It measures the cost of traveling from $u$ to $v$ and back, satisfies the triangle inequality, and is inherently symmetric. While this metric has become central to the study of directed roundtrip spanners and compact routing, the fundamental problem of all-pairs roundtrip distance approximation has remained largely unexplored. In this work, we present a comprehensive study of roundtrip APSP and distance oracles, presenting several new lower and upper bounds. On the algorithmic side, our main result is a combinatorial algorithm that computes a stretch-$3$ approximation to all-pairs roundtrip distances in $\widetilde{O}(n^2 + \min\{m\sqrt{n},\, m^{1/3}n^{5/3}\})$ time. For edge weights in $[1,W]$, we also obtain a $(3+\varepsilon)$-approximation in $\widetilde O((n^{2.037}+nm^{2/3})\log(nW)/\varepsilon)$ time and a $(4+\varepsilon)$-approximation in $\widetilde O(n^{2.032}\log(nW)/\varepsilon)$ time using fast matrix multiplication. On the hardness side, we show that any stretch below $3$ would imply a breakthrough for BMM. We also obtain additional tradeoffs between stretch and running time.

Authors: Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Mingchen Ma

We introduce Gaussian partitioning, an algorithmic primitive for distributions smooth with respect to a Gaussian. It partitions space into polyhedral regions so that almost all mass lies in thin strips restricting a few orthogonal directions. Within each strip, the conditional distribution approximately matches low-degree Gaussian moments in the unrestricted directions. Our construction builds on logconcave partitioning of Diakonikolas, Kane, and Ma (FOCS 2026). Under input marginals smooth with respect to the standard Gaussian, we obtain agnostic learners with error $(1+c)\mathrm{opt}+ε$ for broad classes of Boolean multi-index models, including functions of halfspaces, low-dimensional convex concepts, and low-dimensional polynomial threshold functions. For functions of $k$ halfspaces, both agnostic and testable agnostic learners achieve this error with dimension dependence $d^{\mathrm{poly}(k/c)}$, improving the previous exponential dependence on $k/c$ in the agnostic exponent. For learning from positive examples with imperfect unlabeled data (PUI), we give algorithms and Statistical Query (SQ) lower bounds that qualitatively characterize complexity through Gaussian moment matching. For fixed smoothness and positive-mass parameters, we learn intersections of $k$ halfspaces with dimension dependence $d^{O(\log(k/ε))}$ and matching SQ lower bounds, improving the previous $d^{\mathrm{poly}(1/ε)}$ upper bound even for one halfspace. A general reduction from agnostic reliable learning to PUI yields negative reliable learners for these intersections with the same dimension dependence, for fixed smoothness. Finally, for PQ learning and testable learning with distribution shift, we prove qualitatively optimal SQ lower bounds of $d^{Ω(1/ε^2)}$, even for intersections of two halfspaces with Gaussian training data and arbitrary test distributions.

Authors: Alex Conway, Hanna Komlós, William Kuszmaul

A defining feature of the linear-probing hash table is its spatial locality: at load factor $1 - \varepsilon$, the hash table can be implemented so that each operation scans a single contiguous region of expected size $O(1/\varepsilon)$ (this is known as the \emph{scan cost}). This guarantee, however, relies on all items having unit size. In this paper, we ask whether it is possible to achieve a similar guarantee, but in a hash table that stores items of arbitrary lengths $|x| \ge 1$. The main result of the paper is a new hash table called \emph{Catalan hashing}, which supports amortized expected scan cost $O(|x|/\varepsilon)$ for positive queries, $O(1/\varepsilon)$ for negative queries, and $O(|x|\varepsilon^{-1}\log^{1+δ}|x|)$ for insertions/deletions, for any constant $δ> 0$. As a corollary, we obtain the same bounds in the cache-oblivious model, with a scan cost of $S$ translating to $1 + O(S/B)$ I/Os. Along the way, we introduce several high-level techniques that may be of independent interest; this includes a novel way of using erasure codes in order to perform write optimization within a hash table, and a connection to scheduling that allows us to place elements in a way which avoids clustering at high load factors.

Authors: Jonathan Leake, Anqi Li

Let $μ$ be a probability distribution on a spin system with $n$ sites and possibly infinite spin spaces. We prove local-to-global spectral-gap bounds for block Glauber dynamics. Given a symmetric, entrywise nonnegative matrix $A$ with zero diagonal and $λ_{\max}(A)<1$ encoding local spectral bounds for a spin system, we derive global spectral-gap bounds for block dynamics on its marginal distributions. These bounds are sharp: the Gaussian system with covariance $(I-A)^{-1}$ attains equality for every choice of disjoint blocks. Our proof extends the Bochner method through an abstract inequality for orthogonal projections on Hilbert spaces. As an application, we prove that Glauber dynamics for the $O(N)$ model, with $N\geq 2$, arbitrary external fields, and couplings of either sign, has spectral gap at least $(1-\|J_{\mathrm{abs}}\|_{\mathrm{op}}/N)/n$, where $J$ is the interaction matrix and $J_{\mathrm{abs}}=(|J_{ij}|)$. We also obtain spectral bounds for swap walks and local spectral expansion of partite simplicial complexes. For complexes formed from disjoint groups of ranks in random flags of subspaces over $\mathbb F_q$, we obtain a one-sided local spectral expansion bound of $2\sqrt q/(q+1)$. This bound is independent of the number and sizes of each group, and is nontrivial for every prime power $q$. Finally, for random forests $F$ of any finite graph with arbitrary positive edge weights, we prove that \[ \Pr(e,f\in F)\le \frac{4}{3} \Pr(e\in F)\Pr(f\in F) \] for distinct edges $e,f$, improving the factor 2 supplied by general log-concavity bounds for matroid independent sets. The argument combines our extended Bochner method with the analysis of an auxiliary real stable polynomial.

Authors: Martin Bichler, Abheek Ghosh

Colonel Blotto is a fundamental resource-allocation game in which two players divide their budgets across battlefields, and the higher allocation on each battlefield wins its value. The problem of computing an equilibrium efficiently has remained unresolved for its classical continuous version with arbitrary budgets and with values that may vary across battlefields but are the same for both players. We give a fully polynomial-time approximation scheme that computes an $\varepsilon$-Nash equilibrium in time polynomial in the input length and $1/\varepsilon$, and nearly linear in the input length for fixed $\varepsilon$. For sufficiently balanced budgets and battlefield values, we also compute exact equilibria in linear time.

Authors: Mohammad Hajiaghayi

We prove that every connected $n$-vertex graph admits a probabilistic embedding into its spanning trees with expected distance stretch $O(\log n)$. This settles the logarithmic stretch conjecture of Alon, Karp, Peleg, and West, whose spanning-tree game appeared at the 1991 DIMACS Workshop on On-Line Algorithms and in SIAM Journal on Computing in 1995. A weighted form of the theorem also yields a distribution over spanning trees with capacities exactly equal to their fundamental graph cuts. Every tree dominates every graph cut, every cut is approximated within $O(\log n)$ in expectation, and the same capacity distribution defines an $O(\log n)$-competitive fractional oblivious routing. The distance and capacity distributions may differ. Diamond graphs give matching logarithmic lower bounds for stretch, congestion, and cut distortion. For rational input, both distributions are constructed deterministically in polynomial time and use at most $m$ trees, where $m$ is the number of graph edges. We prove an $Ω(m/ρ)$ support lower bound for congestion $ρ$; in particular, $(1-o(1))m$ trees can be necessary for near-unit congestion, even when the optimum tends to one. Thus linear dependence on $m$ is unavoidable in this regime. The weighted theorem combines a protected-geodesic petal decomposition with a pathwise entropy bound for locally selected centers. A local averaging inequality derandomizes the radii, and an adaptive rational packing procedure constructs the distributions.

Authors: Serge Gaspers

Using the bisection bound of Monien and Preis, Fomin and Høie proved in 2006 that every graph of maximum degree 3 on $n$ vertices has pathwidth at most $n/6+o(n)$. We prove that the pathwidth, bisection width and cutwidth of these graphs are at most $c_3 n+o(n)$, where $c_3=\frac{3}{4π}\arccos\frac56\approx0.1398$. For bisection width this improves the bound $n/6+o(n)$ of Monien and Preis (2006) and extends to all such graphs the bound that Lichev and Mitsche (2023) obtained for random cubic graphs. For maximum degree 4, we prove that bisection width and cutwidth are at most $n/3+o(n)$, improving the bound $2n/5+o(n)$ of Monien and Preis for 4-regular graphs, and that pathwidth is at most $0.2458n$, improving the bound $n/3$ of Fomin, Gaspers, Saurabh and Stepanov (2009). We show that every graph with $m$ edges has pathwidth at most $7m/48+o(n)$, improving the bound $13m/75$ of Scott and Sorkin (2007), and we give further bounds of the form $\sum_{d\ge3}a_d n_d+o(n)$ with $a_d<1$, where $n_d$ is the number of vertices of degree $d$. The path decompositions, and linear orderings of the stated cutwidth, can be computed in polynomial time. Instead of deriving pathwidth bounds from bisection width, we give each vertex a Gaussian label, a weighted sum of independent standard normal variables over a ball around it, and sweep a threshold through the labels; the bags are frontiers, the vertices above the threshold with a neighbor below it. We bound the probability that a vertex lies in a frontier by comparison with an explicit Gaussian model of a vertex and its neighbors. Faster exact algorithms follow: for feedback vertex set and the traveling salesperson problem on graphs of bounded maximum or average degree, and on general graphs for minimum weight dominating set (by branching until the instance is sparse), Max 2-CSP and counting subgraphs with $k$ edges (by the bound in $m$).

Authors: Ralf Klasing, George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis

In classical gossiping, each participant initially knows a distinct piece of information. Whenever two participants call each other, they exchange everything they know. We study Gossiping: given an undirected multigraph whose vertices represent participants and whose edges represent available calls, decide whether the calls can be ordered so that every participant learns all information, using each edge at most once. Equivalently, can one time label per edge make the graph temporally connected by strict temporal paths? This recognition problem is NP-complete; we study its parameterized complexity. After linear-time preprocessing, we give an exact $O(3^{n/3}n^3)$-time algorithm and a deterministic $2^{O(tw)}n$-time algorithm, where $n$ is the number of vertices and $tw$ is the treewidth of the underlying simple graph. We introduce a Tree Contraction Rule that extends the treewidth algorithm to single-exponential algorithms for parameters that may remain small on dense graphs, such as tree-independence number and clique-width, without requiring a decomposition as input. For the excess $δ=m-(2n-4)$ over the minimum number of calls, where $m$ is the number of edges, we give a randomized $2^{O(δ)}n^3$-time algorithm with one-sided error. Its main subroutine solves Rooted Independent Cycle: finding a cycle through four prescribed vertices whose edges are independent in a represented linear matroid. We solve this problem deterministically in $2^{O(r)}m$ arithmetic operations over the finite field representing the matroid, where $r$ is its rank. Gossiping is polynomial-time solvable at maximum degree four, counting parallel edges, but NP-complete on planar simple graphs of maximum degree five. The treewidth algorithm yields a $2^{O(\sqrt n)}$-time algorithm on planar graphs.

Authors: Chandrima Kayal, Frédéric Magniez, Sayantan Sen, Dániel Szabó

We prove a quantum analogue of the classical moment matching method, a popular framework used to prove lower bounds in property testing. For two random variables $X_0$ and $X_1$ whose moments match up to the first $r-1$ moments, the classical moment matching method says that no classical algorithm can reliably distinguish between input instances of length $N$ constructed from $X_0$ and $X_1$, respectively, unless it performs at least $Ω(N^{1-1/r})$ queries. While this method has been widely explored since its inception in the seminal work of Raskhodnikova, Ron, Shpilka, and Smith (STOC 2007) to prove lower bounds for symmetric properties, it has remained an open question whether a quantum analogue of it could be proved. We prove two variants of this quantum moment matching method, which are incomparable. Our first quantum query lower bound scales as $Ω(N^{1/2-1/(2r)})$, while our second moment matching theorem yields a sharper lower bound of $Ω(N^{1/2-1/(2(2^r-1))})$, albeit for smaller parameter ranges. Our results combine a new continuous hybrid argument with the polynomial method. The continuous hybrid argument compares two hard input distributions generated from i.i.d. samples by continuously varying both distributions, keeping them identically distributed at every intermediate stage. It reduces the comparison to the effect of changing the distribution of a single sample. The polynomial method then cancels the terms determined by the matched moments. We apply these moment matching theorems to prove new optimal lower bounds on $k$-distinctness, $k$-star-freeness, planarity and outerplanarity testing, as well as to improve prior lower bounds on image size testing and $K$-junta testing by logarithmic factors. A key advantage of our framework is its simplicity: it reduces quantum lower bound proofs to the construction of suitable moment-matching distributions.

Authors: Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma, Lisheng Ren, Trung Tran

We give an algorithm for PAC learning intersections of $k$ degree-2 polynomial threshold functions over $R^d$ under a Gaussian distribution. Our algorithm achieves classification error $ε$ using $d^{O(k)}2^{O_k(\log^3(1/ε))}$ time and samples, improving over the $d^{O(k^2/ε^2)}$ running time of the polynomial regression approach. To our knowledge, our result is the first to obtain a dimension exponent independent of the accuracy parameter, even for $k=2$. We complement our algorithmic result with an SQ lower bound showing that the complexity dependence of $d^{Ω(k)}$ is unavoidable. Lifting the input to polynomial features turns the target into an intersection of $k$ halfspaces. This suggests using the first two labeled moments for subspace recovery. In the lifted space, however, these moments can reveal nothing. Our starting point is a Gaussian comparison theorem showing that, for sufficiently regular defining quadratics, the labeled moments needed for subspace recovery are approximately preserved. To handle arbitrary defining quadratics, we establish a new structural result showing that every direction with significant resampling influence can be detected through degree-$O(k)$ moments. These results yield an initial $d^{O(k)}2^{\mathrm{poly}_k(1/ε)}$-time learner using adaptive restrictions. To improve the exponential dependence on $1/ε$, we develop a two-stage dimension-reduction approach that avoids the costly adaptive partitioning. After identifying a subspace containing all directions with large influence, we use generalized regularity and Gaussian comparison to recover the remaining relevant quadratic features through a new derivative-based moment operator. The recovered features support an intersection close to the target. Combining them with robust hinge-loss minimization gives our quasipolynomial-time learner.

Authors: Gary Hoppenworth, George Z. Li, Sepideh Mahabadi, Jakub Tarnawski

In the semi-streaming model, the edges of an $n$-vertex graph arrive in a stream, and an algorithm makes multiple passes over that stream while using only $\widetilde{O}(n)$ space. The number of passes needed to compute single-source reachability in directed graphs is a long-standing open question in streaming algorithms, going back to Henzinger, Raghavan, and Rajagopalan (1998). The best known semi-streaming algorithm uses $n^{1/2+o(1)}$ passes due to Jambulapati, Liu, and Sidford (2019), while the best lower bound is $Ω(\log n/\log\log n)$ passes due to Guruswami and Onak (2016). We give streaming algorithms for computing single-source reachability and shortest paths on $n$-vertex directed graphs using $\widetilde{O}(n)$ space and $n^{1/3+o(1)}$ passes. Our algorithms are based on implicit hopsets, which are large hopsets that can be represented implicitly in $\widetilde{O}(n)$ space. We introduce this notion and give new constructions for implicit hopsets with small hopbound. Along the way, we obtain new work-depth tradeoffs for parallel shortest paths in directed graphs, improving the recent result of Ashvinkumar, Bernstein, Probst Gutenberg, and Saranurak (2026).

Authors: Pin-Hsian Lee, Peng-Ting Lin, Meng-Tsung Tsai, Ting-An Wu

The Nash-Williams--Tutte theorem characterizes the existence of $k$ edge-disjoint spanning trees by a condition on every vertex partition. We prove that, for simple graphs, the same condition guarantees $k$ edge-disjoint spanning trees, each of diameter $O(n/δ)$ and with $O((n/δ)\log(δ+1))$ internal vertices, where $n$ is the number of vertices and $δ$ is the minimum degree. Both bounds hold simultaneously for every tree, with absolute implicit constants independent of $k$, and each is asymptotically optimal in general. Our proof is constructive and yields a randomized algorithm with expected running time $\tilde{O}(n^5)$. We derive applications to short edge-disjoint routes and weak linkages, small Steiner trees, and survivable networks with short paths. The joint bounds also yield low-diameter spanning Eulerian subgraphs and short tours for postman and general routing problems.

Authors: Xian Chen, Pan Peng

We study (non-induced) subgraph counting under interactive local edge differential privacy (LEDP). Given a fixed pattern graph $H$ with $k$ vertices, $\ell\ge1$ edges, and $q$ connected components, our goal is to approximately count its copies in an arbitrary $n$-vertex undirected graph while preserving edge privacy. We give two complementary accuracy guarantees. First, for every $H$, we give Linear Noise Cancellation (LNC), a two-round $\varepsilon$-LEDP algorithm with additive error and root mean square error both $O(n^{k-3/2}/\varepsilon^\ell)$ on every $n$-vertex graph. For fixed sufficiently small $\varepsilon$, this improves the optimal noninteractive additive error for triangles by a factor of $\sqrt n$ and gives the same improvement in worst-case root mean square error for all cliques on at least three vertices. To our knowledge, this is the first separation between interactive and noninteractive LEDP subgraph counting, showing that a single additional round can improve worst-case accuracy polynomially. Second, we determine how accuracy improves when the graph has maximum degree at most a public bound $d$. Our Predict and Correct (PC) framework gives an $(\ell+2)$-round $\varepsilon$-LEDP algorithm with additive error $O(n^{q-1/2}d^{k-q-1}\log^{3\ell-2}n/\varepsilon^\ell)$. For connected patterns, its polynomial factor is $\sqrt n\,d^{k-2}$, giving sublinear error on constant-degree graphs at fixed privacy. We prove matching lower bounds in $n$ and $d$, up to logarithmic factors at fixed privacy, even under arbitrary interaction and approximate privacy with sufficiently small $δ$. At $d=Θ(n)$, the lower bound also establishes the optimality of LNC's dependence on $n$.

Authors: Santhini K A, Raghu Raman Ravi, Meghana Nasre

Assigning applicants to posts in the presence of applicant preferences and quotas associated with posts is extensively investigated. For a post, a lower quota guarantees, and an upper quota limits the number of applicants assigned to it. Typically, quotas are assumed to be fixed, which need not be the case in practice. We address this by introducing a soft quota setting, in which every post is associated with two values - lower target and upper target - which together denote a range for the intended number of applicants in any assignment. Unlike the fixed quota setting, we allow the number of applicants assigned to a post to fall outside the range. This leads to assignments with deviation. Here, we study the problem of computing an assignment that has two orthogonal optimization objectives - minimizing the deviation (maximum or total) with respect to soft quotas and ensuring optimality with respect to preferences of applicants (rank-maximality or fairness). The order in which these objectives are considered, the different possibilities to optimize deviation combined with the well-studied notions of optimality with respect to preferences open up a range of optimization problems of practical importance. We present efficient algorithms based on flow networks to solve these optimization problems. We also consider a generalization of the soft quota setting, where every deviation is associated with a cost. We show extensions of our algorithms for solving the problems in this setting.

Authors: Tatsuya Terao

We consider monotone submodular maximization subject to a matroid constraint. The seminal continuous greedy algorithm of Calinescu, Chekuri, Pál, and Vondrák~[SICOMP'11] achieves the tight approximation of $(1-1/e)$. Since then, a line of works by Badanidiyuru and Vondrák~[SODA'14], Buchbinder, Feldman, and Schwartz~[SODA'15 \& MOR'17], Kobayashi and Terao~[ICALP'24], Buchbinder and Feldman~[FOCS'24 \& SICOMP'25], and Buchbinder and Feldman~[STOC'25] has developed efficient $(1-1/e-\varepsilon)$-approximation algorithms for this problem. We present a combinatorial randomized $(1-1/e-\varepsilon)$-approximation algorithm that requires $\tilde{O}_{\varepsilon}(n)$ independence-oracle and value-oracle queries, where $n$ is the number of elements in the matroid. This is the first $(1-1/e-\varepsilon)$-approximation algorithm with both independence-oracle and value-oracle query complexities nearly-linear in $n$ and polynomial in $1/\varepsilon$. To achieve this, we develop a new local search algorithm, which we call \emph{protected local search}, based on the potential function of Buchbinder and Feldman~[FOCS'24 \& SICOMP'25].

Authors: Fabrizio Grandoni, Stefano Leonardi, Matteo Russo

We study online metric facility location in the batched random-order model. An adversary partitions $n$ clients into $B$ nonempty batches, which arrive in uniformly random order. Each batch is revealed in full, and its clients must be connected to open facilities before the next batch arrives. Openings and assignments are irrevocable, and the objective is to minimize the total opening and connection cost. For both uniform and nonuniform opening costs, we prove that the tight competitive ratio is \[ Θ\!\left(\min\left\{\log(B+1), \sqrt{\log(n-B+2)}\right\}\right). \] Thus, the ratio is constant both when there is a single batch and when every batch is a singleton, but intermediate numbers of batches can require a $Θ(\sqrt{\log n})$ ratio. Our algorithms build on Meyerson's algorithm (2001) and do not need to know $n$ nor $B$. A key algorithmic novelty is that we process the clients in a batch one by one in uniform random order (hence neglecting the global properties of the batch). We present a novel analysis of this algorithm that hinges on the random order of the batches, as well as of the clients within each batch. We also provide a matching competitive ratio lower bound already for uniform costs, and even when the entire metric is known in advance.

Authors: Gopalan Sajith, Manas Kumar Panda, Ranajit Senko

We study the problem of sorting on the Parallel Random Access Machine (PRAM), Parallel Comparison Model (PCM) and Parallel External Memory Model (PEM). On PRAM, we present a Concurrent Read Exclusive Write algorithm that runs in $O(\log n)$ time with $n$ processors; our algorithm is very different from Cole's Merge Sort. On PCM, we present the first optimal algorithm for sorting after AKS; our algorithm runs in $O(\log n/\logα)$ comparison rounds with $nα$ processors, for $1\leqα\leq n$. On PEM, we present a Concurrent Read Exclusive Write algorithm that sorts $N$ elements in $O\left(\log\frac{N}{B}\right)$ I/O rounds with $p\geq \frac{N}{B}$ processors.

Authors: Artur Czumaj, Pan Peng, Yuyang Wang

We study testing acyclicity of directed graphs in the bounded-degree incidence-lists model, where a tester can query the outneighbors of a vertex but not its inneighbors. Despite significant effort, no tester with $o(n)$ queries is known, while the best established lower bounds are $\widetildeΩ(n^{5/9})$ for one-sided testers (Chen, Randolph, Servedio, and Sun, 2022) and $Ω(n^{1/3})$ for two-sided testers (Bender and Ron, 2002). We show that a query exponent arbitrarily close to one is necessary: for every fixed $η\in(0,1)$, there exists a constant $\varepsilon_η>0$ such that, for every constant $d\ge2$, every randomized adaptive two-sided $\varepsilon_η$-tester for acyclicity of simple $n$-vertex directed graphs whose indegrees and outdegrees are at most $d$ makes $Ω(n^{1-η})$ queries. Our proof overcomes two barriers. First, in previous constructions, the acyclic part of the graph is easy to recognize, which helps an algorithm stay inside the cyclic part. We hide a high-girth cyclic core inside a hierarchy of acyclic masking regions, in which each region imitates the levels below it and can be told apart from them only through rare events, and an iterated information-theoretic argument shows that every exploration observes only small, low-diameter forest components of the core. Second, a two-sided tester may exploit the statistics of collisions without ever seeing a cycle, and at a near-linear budget collisions are unavoidable. We compare complete transcripts with those of an acyclic input built on a fixed core by counting injective embeddings of the observed forest: in high-girth cores, all connected collision patterns of bounded order contribute identically, which makes the two transcript distributions statistically indistinguishable.

Authors: Marco Bressan, Stefano Clemente, Giacomo Fumagalli, Daniel Paul-Pena, C. Seshadhri

A hypergraph $H = (V,E)$ describes a set system over a vertex universe $V$. Hypergraphs are increasingly popular in network science, as they represent interactions between subsets of vertices. A natural challenge is to design a data structure for $H$ to quickly answer basic questions about it, e.g. how many neighbors a vertex $v$ has or whether a hyperedge contains a vertex subset $S$. Such questions are trivial for graphs, for which we simply inspect the adjacency list. The gold standard, from a data structures perspective, would be near-linear time preprocessing and query answering in (poly)logarithmic time. Since this is unlikely for arbitrary $H$, we ask for well-motivated hypergraph properties that can make such a goal possible. We introduce bidegeneracy, a measure of hypergraph sparsity that strictly generalizes many other measures, including bounded degree, bounded rank, and bounded $\infty$-degeneracy. We show that bounded bidegeneracy yields fast hypergraph data structures. For a large set of fundamental queries, including their listing and sampling versions, we obtain near-linear preprocessing and (poly)logarithmic query time. Moreover, direct reductions from assumptions like the Orthogonal Vectors Conjecture suggest that, without assumptions on the input, these structures require almost-quadratic preprocessing or almost-linear query time. We use bidegeneracy to compute a compressed representation of $H$ and perform careful reductions to stabbing and searching problems in $\mathbb{R}^d$. Our framework significantly extends the well-studied "partial matching" problem of finding database entries through wildcard search. It also uncovers an intriguing connection between hypergraph sparsity, compression, and the complexity of hypergraph primitives. We also find remarkably low bidegeneracy in hypergraph datasets from the literature, suggesting practical consequences.

Authors: Diana Ghinea, Fabian Kuhn, Chen-Da Liu-Zhang, Zahra Parsaeian

We study deterministic algorithms for locally checkable graph problems in the synchronous LOCAL model with crash failures, where a crashing node may send messages to only some neighbors. We introduce consistent neighborhoods: partial radius-$R$ views that agree locally across surviving edges and are complete without crashes. For $R=T+\ell+1$, these views allow local simulation of $T$-round fault-free algorithms that remain correct on subgraphs, satisfying constraints wherever the radius-$\ell$ checking neighborhood contains no crash. On graphs with at most $n$ nodes and maximum degree at most $Δ\geq3$, we construct these views in $O(\min\{n,(Δ-1)^R,RΔf\})$ rounds when a crash bound $f\geq1$ is globally known; the first two bounds require no knowledge of $f$. For $Δ=2$ or girth greater than $2R$, including forests, $O(R)$ rounds suffice. Our upper bounds are essentially tight in suitable parameter regimes. One crash can force $Ω(n)$ rounds even for $R=3$ on diameter-two graphs. For each fixed $Δ\geq3$ and sufficiently large $R$, we prove a $(Δ-1)^{R-O(\sqrt R)}$ lower bound even with crashes restricted to round beginnings. We also prove an $Ω(ΔRf)$ lower bound when $R\geq4\lceil\log_{Δ-1}f\rceil+4$ and $n\geqΔRf$. For locally checkable labeling (LCL) problems, we preserve $O(\log^* n)$ complexity under any number of crashes whenever this bound holds without faults on all graphs with a fixed degree bound. In contrast, we construct an LCL on graphs of maximum degree at most five with fault-free complexity $Θ(\log n)$ and crash-tolerant complexity $Θ(n)$. Finally, any fault-free sinkless-orientation algorithm can be transformed to tolerate any number of crashes with only one additional round, guaranteeing correctness even at surviving nodes adjacent to crashes.

Authors: Morteza Alimi, Tobias Mömke, Alexandru Popa, Michael Ruderer

Given intervals and points on a line, each point with a demand, and a budget $K$, Maximum Interval Multicover asks for at most $K$ intervals that satisfy as many points as possible, a point being satisfied if it lies in at least as many chosen intervals as its demand. One application is committee elections in which each candidate is approved by consecutive voters and voters have individual demands. Xu, Ran and Zhang introduced the problem and gave a $1/2$-approximation; the objective is not submodular when demands exceed one. Li, Tu, Zhang and Cao gave a polynomial-time approximation scheme (PTAS) for the minimization counterpart, unweighted partial interval multicover, and asked for its complexity. We prove that both problems are NP-hard, even for intervals of equal length; as their optima are integers bounded by the input size, neither has a fully polynomial-time approximation scheme unless $\mathrm{P}=\mathrm{NP}$. We then give a PTAS for Maximum Interval Multicover, also for arbitrary nonnegative nondecreasing rewards for the coverage of each point. Building on a decomposition from Nonner's PTAS for Densest $k$-Subgraph on interval graphs, our scheme cuts the line into pieces at a small loss and solves every piece exactly. The key dynamic program handles intervals crossing a common point by choosing an interleaving of their left and right endpoints rather than sweeping along the line; it needs only two counters to track these intervals. The same algorithm yields PTASes on convex bipartite graphs for Bipartite Dense Subgraph, improving on the ratio $2/3$ of Backer and Keil for the subclass of bipartite permutation graphs, and on interval graphs for Maximum $k$-Vertex Cover and weighted clique counts.

Authors: Zehan Lin, Xiaowei Wu, Shengwei Zhou

We study randomized allocations (lotteries) of indivisible chores under additive costs and introduce the notion of MMS1, which requires each agent's bundle to satisfy the maximin share (MMS) bound after the removal of at most one chore. Our main result establishes that every instance admits an ex-ante proportional lottery in whose support every allocation is MMS1 and all but $o(n)$ agents satisfy MMS. Consequently, every realized allocation can be made MMS by disposing of at most $o(n)$ chores. The proposed framework further achieves ex-ante proportionality alongside ex-post $4/3$-MMS, $o(n)$-AMMS, or $1$-out-of-$d$ MMS for $d=(1-o(1))n$. These guarantees substantially improve upon state-of-the-art bounds for MMS allocation for chores with disposal or subsidy, best-of-both-worlds fairness, approximate AMMS, and ordinal MMS approximations.

Authors: Philip Bille, Inge Li Gørtz

Regular expression matching asks whether a string of length $n$ belongs to the language described by a regular expression of length $m$. We give an algorithm that solves this problem in linear space and $O(nm \log \log n/\log^2 n + n + m)$ time. This improves the leading term of the previous best worst-case constant-alphabet time bound by a factor of $\sqrt{\log n}$. The key new technique is a two-dimensional tabulation specialized to the regular expression.

Authors: Nick Fischer, Adam Polak, Jonas Schmidt

Efficient graph algorithms often use techniques that are specific to integer-valued inputs and do not work for real-valued versions of the problems. Is it a limitation of current techniques, or are the real-valued variants inherently harder? One way to study this question is through real-to-integer reductions. We give (randomized, combinatorial) subcubic real-to-integer reductions for two central graph problems in fine-grained complexity: All-Pairs Shortest Paths and Exact Triangle. That is, we show that if the integer variants of these problems can be solved in truly subcubic time, then the real variants can also be solved in truly subcubic time. Our work extends and combines techniques from three previous works: (1) our real-to-integer reduction for the 3SUM problem (Fischer, Polak, Schmidt, FOCS 2026), which itself combines the Frank--Tardos theorem from optimization with Freiman's theorem from additive combinatorics; (2) universe reduction for APSP (Fischer, STOC 2026), which we generalize to reals and use to reduce the doubling of the set of edge weights; and (3) the ``Fredman's trick meets dominance product'' technique (Chan, Vassilevska Williams, Xu, STOC 2023), which is needed to adapt the prior real-to-integer framework from equality constraints to inequalities. As a corollary, our reduction combined with Yuval's fast Integer APSP algorithm in the real RAM model with multiplication (IPL 1976) shows that the Real APSP Hypothesis is false in this model, which also follows from the very recent breakthrough by Alman and Vassilevska Williams using a very different approach.

Authors: Tianshun Miao

We give a near-linear-time sampler for the zero-field ferromagnetic Ising model throughout the tree-uniqueness regime, including the threshold itself. The method also gives sampling algorithms for the XY and integer Potts models. On an $n$-vertex graph with $m$ edges and maximum degree at most $Δ$, we obtain the following expected-work bounds, with total variation error at most $\varepsilon$. 1.Near-linear Ising sampling. For $Δ\ge3$, the work is $O(n+m\log^3(n/\varepsilon))$ throughout the tree-uniqueness regime, including the threshold $β=Δ/(Δ-2)$. 2.Almost-linear XY sampling. For $Δ\ge8$, we sample the XY model in $\widetilde O(m+n^{1+o(1)})$ expected work at inverse-polynomial accuracy up to and including the robust phase-transition threshold on the $Δ$-regular tree. 3.Near-linear Potts sampling. For integer $q\ge3$, we sample the $q$-state Potts model in $\widetilde O(n+q^{O(1)}m)$ expected work whenever $β-1\le 0.1(β_{\mathrm{od}}(q,Δ)-1)$, where $β_{\mathrm{od}}$ is the ordered/disordered coexistence parameter. We express the even-subgraph representation of critical Ising as a polymer model that admits near-linear-time sampling, thereby bypassing the critical slowdown of Glauber and Swendsen--Wang dynamics. Building on the low-degree approximation approach of Miao and Yin, we establish general spectral conditions for fast polymer sampling. We verify these conditions through explorations that also implement the sampler efficiently, and apply the same framework to flow representations of the XY and Potts models. We also establish polynomial-time counting and sampling for the ferromagnetic XY model at every fixed temperature.

Authors: Yixin Cao, Ying Xu

The best-known approximation factor for constrained correlation clustering stood at three for nearly two decades, until a recent improvement to below $16/7$. We give a randomized polynomial-time $(2+\varepsilon)$-approximation using \emph{Repulsion}, a recursive operation that separates a metric ball from its complement. Repulsion naturally respects hard constraints and admits a short potential-based analysis; as a warm-up, radius-$2/3$ Repulsion rounds the standard metric LP into a feasible partition of cost at most three times its objective. The $(2+\varepsilon)$-approximation takes a two-stage approach, first removing must-links with arbitrarily small loss in the approximation ratio. The second stage combines lossless, constraint-aware preclustering with the bounded sub-cluster LP framework of Cao, Cohen-Addad, Lee, Li, Newman, and Vogl (STOC 2024). Repeated positive conditioning and sampling produce candidate sets, which radius-one Repulsion partitions into feasible clusters at controlled cost. We also give an approximation-preserving reduction from vertex cover to cluster deletion, a special case with only cannot-links. Apart from establishing a matching factor-two hardness threshold under the Unique Games Conjecture, it motivates our two-stage approach and Repulsion.

Authors: Pan Peng, Ranran Shen

Testing expansion asks to distinguish graphs of large conductance from graphs that are far from having large conductance. We study a relaxation in which only part of the graph is required to expand: does an $n$-vertex graph of bounded degree contain an induced expander on a constant fraction of its vertices, when the rest of the graph, including the edges leaving the expander, is arbitrary? Let $P_{α,φ}$ denote the property of containing an induced subgraph on at least $αn$ vertices with inner conductance at least $φ$. For every constant $κ\in(0,1)$, we give a tester that accepts graphs in $P_{α,φ}$ and rejects graphs outside $P_{κα,μφ^2}$, where $μ=Θ_{α,κ}(1/\log n)$, using $O_{α,κ}(\sqrt n\,φ^{-2}\log n)$ queries. For fixed $α\in(0,1]$, $κ\in(0,1)$, and $0<φ\le9/20$, we further show that distinguishing these two classes requires $Ω_{α,κ,φ}(n^{1/2+c_{κ,φ}μ})$ queries for every sufficiently large $n$ and every $0<μ\le1$, where $c_{κ,φ}>0$. The bound holds for adaptive algorithms, uniformly in $μ$. Hence, for testers with $\sqrt n\,\mathrm{polylog}(n)$ queries, the logarithmic loss in conductance is necessary up to a $\log\log n$ factor. The same tester also permits distance-based rejection at a weaker conductance while retaining the original core size. Our tester compares the endpoint distributions of random walks from different vertices with each other, rather than with the uniform distribution. Its analysis uses the trace chain, which observes the walk only at its visits to the unknown expanding core. Our lower bound builds on the noisy-parity construction of [CKK+18], using vector-valued parity labels in $\mathbb F_2^r$ to create many hidden classes, each too small to contain a qualifying induced expander.

Authors: Shiri Chechik, Avi Kadria, Gur Lifshitz, Liam Roditty

Compact routing schemes route messages along short paths while every vertex stores little information. We study the trade-off between the stretch and the storage of compact routing schemes in undirected graphs, in four models: labeled and name-independent schemes, with average or worst-case local storage. We improve the best known stretch in all four models. Our main result is a labeled routing scheme with expected stretch $2k-1$ and $\widetilde O(n^{1/k})$ average local storage, in which only the routing is randomized. Under the Erdős girth conjecture, no scheme with this storage has stretch below $2k-1$, so our scheme is optimal, up to polylogarithmic factors in the storage. With deterministic routing, we obtain stretch $\approx2.47k$, the best known deterministic stretch with average storage. Worst-case local storage is the classical setting of compact routing. The leading coefficient $4$ in the stretch $4k-5$ of Thorup and Zwick~[SPAA'01] was improved only by Chechik~[PODC'13], to $\approx3.68$ in unweighted graphs. In unweighted graphs, we obtain expected stretch $(\frac83k+O(1),O(k))$, and deterministic stretch $\approx3.05k$. Name-independent routing is harder, since the source knows only the name of the destination. The best known stretch with $\widetilde O(n^{1/k})$ local storage in unweighted graphs was $96k$, by Abraham, Gavoille, and Malkhi~[DISC'04]. We improve it by more than a factor of $8$. With average storage, we obtain expected stretch $4k-5$, which matches the labeled scheme of Thorup and Zwick. With worst-case storage in unweighted graphs, we obtain expected stretch $(8k+O(1),O(k))$. All our schemes for unweighted graphs extend to weighted graphs with a small loss in the stretch, and still improve the previous unweighted bounds.

Authors: Mehrshad Taziki, Ali Vakilian

Min-max multi-criteria optimization asks for a single feasible solution minimizing the maximum of its costs under $\ell$ nonnegative cost functions, a formulation that captures both fairness across groups and robustness across scenarios. It has proved hard to approximate even for basic problems: for robust shortest paths, polylogarithmic approximations are known only in quasi-polynomial time. For network design, the best known guarantee is an $\ell$-approximation, which is tight for the natural LP relaxation. We show that exponentially better and nearly optimal guarantees are achievable for two fundamental network design problems. For multi-criteria connectivity augmentation (MC-CAP), which asks to increase the edge connectivity of a given undirected graph by one, we give a randomized polynomial-time $O(\log \ell)$-approximation algorithm. Applying our augmentation procedure iteratively and analyzing its randomized choices jointly across iterations yields an $O(\log k \log \ell)$-approximation for the multi-criteria $k$-edge-connected spanning subgraph (MC-$k$-ECSS) problem, for every $k \geq 2$. We complement these algorithms with a nearly matching lower bound: for every fixed $\varepsilon > 0$, MC-CAP admits no polynomial-time $O(\log^{1-\varepsilon} \ell)$-approximation, even when the underlying graph is a star, unless $\mathsf{NP}\subseteq\mathsf{DTIME}\bigl(n^{\log^{O(1)}n}\bigr)$. The same hardness extends to the MC-$k$-ECSS problem.

Authors: Lakshay Saggi, Ariel Sapir

Dor, Halperin and Zwick [FOCS'96; SICOMP'00] showed that $(2-\varepsilon)$-APASP is at least as hard as BMM for every fixed $0<\varepsilon<1$. Zwick [FOCS'98; JACM'02] gave a $2$-APASP algorithm in $\widetilde O(n^{ω+o(1)}\log W_{\max})$ runtime, where $W_{\max}$ is the maximum edge weight. Bringmann, K{ü}nnemann and W{ę}grzycki [STOC'19] removed this logarithmic factor. Using OpenAI's recent bound $ω\leq\frac{9}{4}$ gives $\widetilde O\left(n^{\frac{9}{4}+o(1)}\right)$ time. We present two weighted undirected $2$-APASP algorithms. The first uses $(\min,\max)$-products. Earlier rectangular FMM bounds of Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou [SODA'24] and Alman, Duan, Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou [SODA'25] give $\widetilde O(n^{2.36999465})$ runtime, below the previous $ω\leq2.371177$ of Dupont, Eisenberger, Kozlovskii, Mehrabian, Ruiz, See, Zhou, Alman, Vassilevska Williams and Balog [arXiv'26]. Current rectangular FMM bounds give $\widetilde O(n^{2.34549151})$, independent of $W_{\max}$. For integer weights, our second algorithm has $\widetilde O(n^{ω-\frac{(ω-2)^2}{ω-1}+o(1)}\log^{O(1)}W_{\max})$ runtime, with exponent below $ω$ whenever $ω>2$. The rectangular bounds of Uzna{ń}ski [arXiv'26] or of Amanov, van den Berg and Zuiddam [arXiv'26] give $\widetilde O(n^{2.17157288}\log^{O(1)}W_{\max})$.

Authors: Shiri Chechik, Gur Lifshitz

In a seminal work [STOC'01; JACM'05], Thorup and Zwick showed that every weighted undirected graph admits a tree cover where each vertex belongs to $O(kn^{1/k})$ trees in expectation, and every pair has a path of stretch at most $2k-1$ in some tree. In this paper, we extend this structural property to directed graphs with nonnegative edge weights. Let $\mathrm{dist}_G(u \leftrightarrows v) = \mathrm{dist}_G(u \to v) + \mathrm{dist}_G(v \to u)$ denote the roundtrip distance. For every integer $k$, we construct a collection $\mathcal{T}$ of tree-pairs, each consisting of an in-tree and an out-tree rooted at the same vertex. Each vertex belongs to $O(kn^{1/k})$ tree-pairs in expectation, and for every ordered pair $(u, v)$ some tree-pair $T_{in}\cup T_{out} \in \mathcal{T}$ satisfies $\mathrm{dist}_{T_{in}\cup T_{out}}(u \to v) \le \mathrm{dist}_G(u \to v) + (k-1)\mathrm{dist}_G(u \leftrightarrows v).$ We call this a \emph{$k$-strong (roundtrip) tree cover}. While prior techniques partition distances into geometric scales and build separate structures for each scale, our construction handles all distances simultaneously within a single, unified hierarchy. This yields the first directed tree cover for general $k$ matching the classic Thorup-Zwick stretch-size trade-off. Our cover immediately implies improved constructions of roundtrip spanners, path-reporting distance oracles, and compact routing schemes, as well as their source-wise and prioritized variants. We also provide faster algorithms for these structures: for general $k \ge 4$, all the above objects can be constructed in $\widetilde{O}(\min\{mn, n^{2.5}\})$ expected time, breaking the $mn$ barrier in dense directed graphs.

Authors: Yansong Feng, Itamar Nir

Let $f\in\mathbb Z[x]$ be a polynomial of degree $n$ with integer coefficients of absolute value less than $2^b$. Using Pan's approximate factorization theorem, we give a deterministic algorithm that finds all distinct integer roots of $f$ in $\widetilde O(nb)$ bit operations. This matches the bit size of the input up to logarithmic factors and does not require $f$ to be square-free. Since we were unable to verify parts of the running time analysis of Pan's theorem, we also give a self-contained deterministic algorithm with running time $\widetilde O(nb+\min(n,b)^3b^2)$, which is $\widetilde O(nb)$ whenever $b\leq n^{1/4}$. This answers a question of Harvey and Hittmeir (2022), who asked whether integer roots can be found deterministically in quasilinear time, conditionally on Pan's theorem, and unconditionally for $b\leq n^{1/4}$. The fastest previous deterministic algorithm, due to Nir, takes $\widetilde O(n^{3/2}b)$ bit operations and works only for square-free polynomials. Instead of $p$-adic lifting, we combine approximate complex root finding with exact polynomial evaluation. We first approximate the complex roots of the polynomial formed by the top $\min(n,b)+1$ coefficients of $f$. Every integer root $r$ of $f$ with $|r|\geq 2$ lies within distance $2$ of some complex root of this truncated polynomial. Rounding the real parts of the approximate roots therefore gives a list of $O(\min(n,b))$ candidate integers that is guaranteed to contain all integer roots of $f$. Although a single candidate can have up to $b$ bits, a bound via the Mahler measure shows that the bit lengths of all candidates sum to $O(b)$. This allows us to test all candidates by exact multipoint evaluation in $\widetilde O(nb)$ bit operations.

Authors: Zongrui Zou

We study the offline release of a public family of $k$ statistical queries on a database of $N$ records from a public universe of size $d$, under pure $\varepsilon$-differential privacy. We give an efficient algorithm that, with probability at least $1-β$, answers all queries simultaneously to error $$O\left(\min\left\{1,\sqrt{\frac{\log(d/β)\log k}{N\varepsilon}}\right\}\right).$$ The output is a synthetic histogram on the data universe, and its running time depends polynomially on $N,d$ and $k$. This resolves a conjecture of Nikolov and Ullman (2021) with an efficient, polynomial-time construction. Fitzsimons (2026) recently established the same square-root error scale via an information-theoretic construction that relies on a computationally intractable Lipschitz envelope over the exponential space of possible outputs. In contrast, we introduce an input-side smoothing approach: we run a selection-only multiplicative-weights process after a single sparse Laplace perturbation of the input histogram. Departing from standard first-order stability analyses, we investigate the stability of stability by establishing a uniform lower bound on the second-order log-derivatives of the output transcript across $T$ rounds of multiplicative weight updates. We then develop an analytic smoothing principle showing that this curvature bound allows a sparse, coordinate-wise perturbation to guarantee pure differential privacy globally, attaining optimal utility through a conceptually simple, polynomial-time pure-DP mechanism.

Authors: Xiongxin Yang

We show that for every $γ>0$ and every sufficiently large $Δ$, the Glauber dynamics for proper $q$-colorings of any $n$-vertex graph of maximum degree $Δ$ has spectral gap $Ω_γ(1/n)$, and hence mixing time $O_γ(n^2\log q)$, whenever $q\ge(1+1/\mathrm{e}+γ)Δ$. Our proof establishes a Bochner-type inequality by exploiting the spectral gaps of hard-core models hidden in the color classes. The constant $1+1/\mathrm{e}\approx1.368$ comes from the uniqueness threshold $\approx\mathrm{e}/Δ$ of the hard-core model on the infinite $Δ$-regular tree.