Theory of Computing Report

Authors: Michal Hospodár, Galina Jirásková, Viktor Olejár, Juraj Šebej, György Vaszil

The 17th International Conference on Automata and Formal Languages (AFL 2026) was held in Košice, September 7-10, 2026. It was organized by the Faculty of Science, P. J. Šafárik University in Košice and the Mathematical Institute of the Slovak Academy of Sciences. This volume contains the texts of the three invited lectures and the 18 papers selected by the Program Committee from a total of 27 submissions. The accepted papers, submitted by authors from 14 countries, cover all important areas of automata and formal language theory and their applications such as grammars and acceptors for strings, trees, and graphs, algebraic theories and algorithms for automata and languages, decision problems, relations to complexity theory, picture description and analysis, and other fields.

Authors: Venkatesan Guruswami, Shilun Li, Mihir Singhal

We prove that for every prime power $q$ and every $p \in (0, 1-1/q)$, a random $\mathbb{F}_q$-linear code of rate $1 - h_q(p) - ε$ is $(p, C_{p,q}/ε)$-average-radius list-decodable with probability at least $1 - q^{-Ω(n)}$, i.e., for every center $y \in \mathbb{F}_q^n$, the $C_{p,q}/ε$ codewords closest to $y$ have average fractional Hamming distance at least $p$ from $y$. This extends a similar result for (standard) list-decoding due to Guruswami, Håstad, and Kopparty (2010) to the stronger average-radius guarantee, with the same $O(1/ε)$ list size. For average-radius list-decoding, such a result was previously known only for binary linear codes (Guruswami, Li, Mosheiff, Resch, Silas, and Wootters, 2021) and for general (non-linear) random codes over arbitrary alphabets (Elias, 1991).

Authors: Kirill Osipov

We develop a resource representation for step recursion in which mutable-state width and recursion descent are explicit and independent parameters. A width bound $u$ controls the size of the encoded machine state, while an effective descent $ρ$ determines the available recursion depth $δ_ρ(u)$. For generalized-inverse descents, we derive the depth directly from generator growth and characterize the increasing sequences that can occur as generator orbits. We then connect this depth--width geometry to standard finite-branching computation. Every deterministic bounded-state dynamics is realizable by a single ordinary bounded step recursion over a fixed finite numerical basis. Using deterministic, existential, universal, or alternating aggregation on the same local dynamics yields the corresponding machine semantics. After closure under the width reparameterizations needed to absorb fixed local cost, the resulting language classes are exactly the machine time--space classes on profiles $(δ_ρ(u),u)$. Finally, profile domination quotients effective descents by admissible width reparameterization. Some depth curves collapse, yet polynomial widths support an explicit infinite strict hierarchy between the canonical polynomial- and exponential-depth profiles. Thus descent remains a nonredundant resource coordinate after polynomial width reparameterization; standard complexity classes are calibration points.

Authors: Mark Jerrum, Heng Guo

We show that approximately counting the vertices of a bounded 0/1 polytope, presented as a system of rational linear inequalities, is, informally speaking, NP-hard. In particular, there is no FPRAS for this problem unless RP=NP. The proof is by a reduction from approximately counting homomorphisms from a given graph to a particular four-vertex graph. The main proof ideas were found using GPT-5.6 Sol Ultra.

Authors: Sijia Dai, Minming Li, Xiaowei Wu, Yong Zhang

The house allocation problem is a classical one-sided matching problem that concerns the assignment of a set of $m$ houses to $n$ agents according to their preferences, where each agent is assigned exactly one house. Among the various objectives studied in this setting, envy-freeness is one of the most widely adopted fairness criteria. As envy-free house allocations do not always exist, we address this challenge by introducing subsidies and aim to compute allocations that achieve envy-freeness with minimum total subsidy. For binary instances, we show that a total subsidy of at most $(n-1)$ suffices to guarantee envy-freeness in house allocation, and this bound is tight. Building on the known NP-hardness for general utilities, we further show that computing an allocation that minimizes the total subsidy is NP-hard, even under binary utilities. However, when there are only a bounded number of types of agents with binary utilities, the problem can be solved in polynomial time. Finally, we present a polynomial time algorithm that computes the minimum subsidy required to achieve envy-freeness for two types of agents with general utilities.

Authors: Zhefan Duan, Huawei Wu

We study the deterministic norm-query complexity of computational problems in finite-dimensional vector spaces over $\mathbb{Q}_p$ equipped with an arbitrary ultrametric norm. For orthogonalization, we prove that no uniform finite query bound depending only on the dimension exists: for every deterministic algorithm that produces an $N$-orthogonal basis for every ultrametric norm $N$, the number of norm queries is unbounded as $N$ varies. We then study the Longest Vector Problem (LVP) for a rank-$m$ $p$-adic lattice. By adapting a brute-force search to the general norm-query setting and eliminating the scalar redundancy among nonzero coefficient vectors modulo $p$, we obtain an algorithm using exactly $(p^m-1)/(p-1)$ norm queries for $m\ge 2$, and prove that no deterministic norm-query algorithm can use fewer queries in the worst case. Finally, we consider the Closest Vector Problem (CVP). Apart from the trivial cases in which no norm query is needed, we prove that the deterministic worst-case norm-query complexity of the CVP is unbounded, even when the lattice and the target vector are fixed.

Authors: Hongmin Li

We study fixed-layout local verification with target-dependent local tests. Let $M$ be a random variable on $\{0,1\}^K$, and let $S$ record the test selected at each coordinate. For each $s\in\operatorname{supp}(S)$, let $F_s$ be the corresponding target fiber and set $D_{\mathrm{fib}}=\max_s\operatorname{VCdim}(F_s)$. We prove $H(M\mid S)\le \log_2\!\left(\sum_{j=0}^{D_{\mathrm{fib}}}\binom Kj\right)$. A fiber that shatters $d$ coordinates yields a weak relaxed locally decodable code with message length $d$ and block length $d+P$ over the original proof alphabet. For a uniform $K$-bit target and fixed proof alphabet, $Q$, and $σ$, the Goldberg--Gur--Saraogi lower bound implies that $I(M;S)\leγK$, for fixed $γ<1$, forces $P=Ω\!\left(K^{1+1/a}/(\log K)^{2+2/a}\right)$, where $a=\lceil Q/σ\rceil$. If $P\le K(\log K)^c$, then $I(M;S)\ge K-O\!\left(K^{a/(a+1)}(\log K)^{3+ac/(a+1)}\right)=K-o(K)$. Any discrete verifier state $T$ determining $S$ satisfies the same information lower bound. Bounded-randomness adaptive branches can be simulated nonadaptively by exposing their decision trees. A branch using at most $r$ random bits and $q$ adaptive proof queries yields a decoder with perfect completeness and at most $1+2^{r+1}\sum_{j

Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard

We study low-degree testing for group-valued functions over a Boolean slice. Specifically given a degree parameter $d$ and oracle access to a function $f:\{0,1\}^n_{n/2}\to G$ where $\{0,1\}^n_k$ denotes the set of vectors in $\{0,1\}^n$ of Hamming weight $k$ and $G$ is an Abelian group, the low-degree testing problem asks us to distinguish the case where $f$ is a polynomial of degree at most $d$ (with coefficients from $G$) or is $\varepsilon$-far from the set of all such polynomials. Classical works in this area considered functions with domain $\mathbb{F}_q^n$ and range $\mathbb{F}_q$. More recent works have considered the setting where the domain is the Boolean cube [Bafna, Srinivasan, Sudan (Random Struct. Algorithms 2020), Amireddy, Srinivasan, Sudan (RANDOM 2023)], or when the domain is the slice (i.e., $\{0,1\}^n_{k}$) and the range is $\mathbb{F}_2$ [David, Dinur, Goldenberg, Kindler and Shinkar (SIAM J. Comput. 2017), Kalai, Lifshitz, Minzer and Ziegler (FOCS 2024)]. Each of the changes introduces new challenges in designing and analyzing low-degree tests and this happens again in our setting with domain being a slice and range is general. Our main theorem gives a test that makes $O_d(1)$ queries to $f$ and accepts degree-$d$ functions while rejecting functions that are $\varepsilon$-far with probability $Ω(\varepsilon)$. The central proof idea is to reduce this low-degree testing problem to the problem of low-degree testing on the cube. Specifically we show how to randomly embed the $n/2$-dimensional cube $\{0,1\}^{n/2}$ in the $n$-dimensional slice while nearly preserving the proximity of $f$ to the space of degree-$d$ polynomials on this cube. While the embedding is simple and natural, the analysis involves a careful induction with a novel use of a basis of degree-$d$ polynomials on slices (from a work of Anstee, Rónyai and Sali (Graphs and Combinatorics 2002)).

Authors: Michael Emmerich

We prove that minimum Riesz $s$-energy subset selection in the Euclidean plane is NP-complete already for the fixed exponent $s=2$. To our knowledge, this is the first Euclidean hardness result for exact Riesz-energy subset selection in which both the ambient dimension and the exponent are fixed. The reduction uses Barahona's planar cubic Ising model with uniform field. A spin is encoded by one diagonal of a four-point square. Axis-aligned selector chains implement ferromagnetic consistency, while a $45^\circ$ terminal geometry yields an antiferromagnetic source interaction. Rational diagonal perturbations realize the magnetic field, and all remaining interactions are dominated by polynomial separation. Because $s=2$ and all coordinates are rational, every constructed energy and the decision threshold are rational exactly.

Authors: Bowen Liu, Yizhou Wang, Lingqian Meng

Triangle-based measures, commonly referred to as badness functions, are widely employed to quantify the extent to which a distance matrix deviates from an ideal geometric configuration. Different formulations of these functions may capture distinct facets of local non-uniformity, and their behavior is often influenced by the underlying distance metric chosen for evaluation. In practical settings, although a canonical badness function may be conceptually preferred, factors such as computational cost, algorithmic constraints, or data-specific characteristics frequently necessitate the adoption of modified versions-for instance, approximate forms or alternatives defined under different distance metrics. This gives rise to a central question: to what degree do these variants retain the structural consistency properties of their original counterparts? To address this issue, we develop a systematic correlation-based framework for evaluating structural consistency. As an illustrative instantiation of this framework, we compute badness sequences from a set of representative distance matrices alongside randomly generated triangle configurations, which are designed to cover variants that may arise under diverse practical scenarios. We then assess pairwise similarities among these sequences using four correlation coefficients. The experimental outcomes indicate that certain badness variants exhibit a notably high degree of structural consistency, whereas others reveal complementary behavioral patterns; moreover, the choice of distance metric exerts a considerable influence on the observed trends. These findings offer practical insights for the informed selection of distance metrics and triangle badness function variants in tasks including geometric reconstruction, triangulation, and structural analysis of pairwise distance data.

Authors: Zeping Yi, Yongjun Wanga, Baoshan Wang, Jian Zhang, Songyi Liu

Deploying wireless nodes to maximize coverage area within a given region is an important challenge in wireless sensor networks, UAV path planning, base station placement and other industrial fields. This practical problem can be mathematically equivalent to an optimal circle covering problem. Although theoretical optimal configurations exist for simple cases in mathematics, the NP-hard nature of this problem makes it computationally prohibitive for complex polygons with numerous nodes. Existing approaches are usually designed for regular domains, while those applicable to irregular polygons often suffer from poor initialization, excessive coverage overlap and failure to constrain nodes within the boundary, leading to low coverage efficiency and long runtime. To address these issues, we propose an improved quasi-physical dynamic algorithm (IQPD) for wireless node deployment in arbitrary convex polygons. Our contributions are threefold: (1) proposing a structure-preserving initialization that maps a hexagonal close packing pattern into the target polygon via scaling and affine transformation, ensuring near-optimal initial node distribution; (2) constructing a refined virtual force model by incorporating friction and a radius-expansion optimization mechanism to reduce coverage area overlap; (3) developing a boundary encircling strategy leveraging normal and tangential gradients to reposition nodes deployed outside boundaries after initial optimization. Extensive experimental results demonstrate that our method consistently outperforms other new metaheuristic algorithms across diverse convex polygon shapes, including randomly generated data and real-world scenarios. Our method achieves the highest coverage rate and node utilization rate among all compared algorithms, greatly improving wireless coverage efficiency.

Authors: Nicolás Honorato-Droguett

Given $n$ points on a line or closed cycle and a threshold $r>0$, the connectivity-maintenance problem is to move the points so that every gap between consecutive points is at most $r$, whereas the points-spreading problem requires every gap to be at least $r$. Li and Wang [CCCG 2015; CGT 2025] and Chen, Gu, Li, and Wang [SWAT 2012; DCG 2013] gave $O(n)$-time algorithms for the cyclic versions of min-max points-spreading and min-max connectivity-maintenance, respectively. Ghadiri and Yazdanbod [CCCG 2016] gave an $O(n\log n)$-time algorithm for the linear version of min-sum points-spreading. In this paper, we show that the two problems can be reduced in linear time to each other for both objectives and on both linear and cyclic domains. As an implication, min-sum connectivity-maintenance is solvable in $O(n\log n)$ time on both domains. Finally, we extend the reduction to points on a line with individual thresholds when their initial order is preserved.

Authors: Qizhi Chen, Zhebei Shen, Zhehan Yu

We prove a strict space separation between static and ordinary dynamic approximate membership at every fixed error rate. For each fixed $\varepsilon\in(0,1)$, a capacity-$n$ ordinary dynamic filter over a universe of size $u$, with zero false negatives, pointwise false-positive probability at most $\varepsilon$, arbitrary history dependence, a free public random tape, and at most $H$ bits of persistent state, satisfies \[ H\ge \bigl(\log_2(1/\varepsilon)+a_\varepsilon^{\rm c}\bigr)n-o(n), \] under only $u/n\to\infty$. The constant $a_\varepsilon^{\rm c}$ is an explicit variational threshold obtained by preserving the dependence between the parent accepted mass and the successor reservoir. The structural step is a common-continuation transport lemma. A joint posterior KL bound gives a branch-specific survivor support; the same legal delete--insert word transports that support to one successor state, forcing an accepted reservoir. We then keep the parent outside mass $1-X$ in the conditional-entropy argument instead of replacing it by $1-\varepsilon$. This yields a two-variable analytic envelope, with no selected thresholds, dyadic witnesses, or numerical assumptions.

Authors: Lin F. Yang

Let $k_ε(n)$ be the smallest number of real linear measurements needed by a randomized, oblivious sketch that estimates the nuclear norm of every fixed real $n\times n$ matrix within a factor $1\pmε$, with probability at least $2/3$. For every fixed $0<ε<1$, the proved result is $$ \frac{n^2}{(\log n)^{A_ε}} \;\le\; k_ε(n) \;\le\; C_ε\frac{n^2\{\log\log(e^e n)\}^2}{\log(e n)} $$ for all sufficiently large $n$, where $A_ε,C_ε$ depend only on $ε$. Previously, the best bounds for general linear sketches were $Ω(n)$ and the trivial $O(n^2)$ upper bound (Li, Nguyen, Woodruff, 2019). The theorem therefore nearly resolves the open measurement-complexity question left by that work: the displayed lower and upper bounds are tight up to polylogarithmic factors. In particular, the complexity is $n^{2-o(1)}$, and for every fixed $c>0$, $O(n^{2-c})$ measurements are impossible. The upper bound is obtained by a fixed Gaussian sketch whose decoder combines implicit low-rank recovery with moment estimation on a high-stable-rank residual. The lower bound constructs moment-matched spectra, randomizes their singular vectors, and compares every low-dimensional observation through an odd-order tensor estimate and a Fisher-information path argument.

Authors: Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld

We give a catalytic logspace algorithm for the problem of graph spectral sparsification. Given an undirected graph $G$ on $n$ vertices and $\varepsilon>0$, our algorithm outputs an $\varepsilon$-spectral sparsifier of $G$ with $O(n\varepsilon^{-2}\log n)$ edges, matching the effective resistance sampling of Spielman and Srivastava (STOC 2008). This gives a new, natural problem in catalytic logspace that is not known to be in deterministic $\mathbf{NC}$ or $\mathbf{SC}$. Our main contribution is an entirely new technique in the compress--or--random paradigm for catalytic logspace that we believe will have further applications. We first analyze effective-resistance sparsification using a pessimistic estimator that can itself be computed in catalytic logspace. The estimator is motivated by the viewpoint of graph quasirandomness and immediately gives a simple, deterministic greedy algorithm for graph sparsification. Subsequently, we show that such a pessimistic estimator can be transformed into an algorithm that performs an in-place compression of a string with bad potential. Our algorithm is based on using the potential function to define a measure over strings, and implementing arithmetic coding using this measure in-place. This compression technique is substantially distinct from all prior tools in the field of catalytic computation.

Authors: Noga Alon, Shay Moran, Shlomo Moran

Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to $k$ of the returned counterexamples may be untruthful, where $k$ is not known in advance. We determine the optimal query complexity up to constant factors: \[ Θ(n\log n + nk). \] Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$. The upper bound is based on a geometric representation of permutations and Grünbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in $\mathbb{R}^d$, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of $O(d^2\log n+dk)$ and a lower bound of $Ω(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.

Authors: Yuta Inoue, Ken-ichi Kawarabayashi, Rintaro Matsuo, Atsuyuki Miyashita, Bojan Mohar, Tomohiro Sonobe

A graph $G$ is \emph{apex} if $G$ has a vertex $v$ such that $G-v$ is planar. We prove that every $2$-connected apex cubic graph is three-edge-colorable. This result gives the final piece of the proof for the well-known Tutte's three-edge-coloring conjecture from 1966 \cite{tutte}. The proof, as well as the result, generalizes that of the Four Color Theorem, which requires computer checks. As in the previous proof of the Four Color Theorem, the proof is constructive. More precisely, given a $2$-connected apex cubic graph $G$ on $n$ vertices, our reducibility and discharging procedure yields a three-edge-coloring of $G$ in $O(n^2)$ time. As an additional reproducibility check for our computer checks, independent implementations reconstructed from the detailed pseudocode (given in the appendix) using generative AI systems reproduced the required computational results. These reconstructions are not part of the mathematical justification of the theorem, but provide additional evidence for the reproducibility of the computations.

Authors: Robert Krauthgamer, Asaf Petruschka, Nir Petruschka

Metric decompositions are a fundamental tool in the design of algorithms involving distances. We study fast algorithms for sampling from probabilistic metric decompositions of $n$-point sets in $\ell_\infty$ and $\ell_2$ spaces of high dimension $d$. For $\ell_\infty$, we design a padded-decomposition algorithm that runs in time $\tilde{O}(nd^2)$, which is near-linear in $n$, and achieves padding parameter $\tilde{O}(\log n)$. Our algorithm constructs a new sparse neighborhood cover that is based on geometric properties of $\ell_\infty$ [Indyk, JCSS'01], and utilizes recent reductions between covers and decompositions [Conroy and Filtser, STOC'25]. For $\ell_2$, we design a separating-decomposition algorithm that achieves near optimal separation $\tilde{O}(\sqrt{\log n})$ in almost-linear time $n^{1+o(1)}$. Our bounds improve over known algorithms with similar running time by a factor $Ω(\sqrt{\log n})$, and the techniques have additional applications to spanners and nearest-neighbor search.

Authors: Or Zamir

Consider the canonical universal hash family $h(x)= ((ax+b)\text{ mod } p)\text{ mod } m$, where $a,b$ are chosen uniformly from $\mathbb Z_p$, which we call linear hashing, being used to hash $n$ elements into $m=Θ(n)$ buckets. For any universal family, the expected size of the largest bucket is at least $Ω(\log n / \log\log n)$ and at most $O(\sqrt{n})$. The only improvement upon these trivial bounds for linear hashing is a 2019 upper bound of $\tilde{O}(n^{1/3})$ by Knudsen. We show that for any $p$ sufficiently larger than $n$, there is a set of $n$ keys whose expected maximum load is $n^{Ω(1/\log\log n)}$, proving linear hashing does not have a polylogarithmic maximum load. We extend the same bounds to the classical multiply-shift hash family of Dietzfelbinger, Hagerup, Katajainen, and Penttonen. We prove an equivalence between the maximum load problem to a density variant of arithmetic Kakeya sets. We then complete the lower bound using a construction of Green and Ruzsa of a small set containing long arithmetic progressions with every difference in a prescribed range. Surprisingly, our equivalence also implies that any substantial improvement over Knudsen's upper bound would imply new results about standard arithmetic Kakeya sets.

Authors: Andrew Au

The Bitner--Ehrlich--Reingold algorithm generates the binary reflected Gray code with constant work per codeword, using a focus-pointer array. Its compact update is easy to state but gives little indication of why such pointers should exist. This note reconstructs a geometric route to the algorithm. The sequence of flipped bit positions is the ruler sequence, OEIS A007814. We realize its finite prefixes as in-order traversals of recursively expanding trees, decorate each activation with its nearest ancestor to the right, contract all stack operations between successive outputs into successor jumps, and prepare the bounded level-indexed stack by predicting its future slot values. This gives and proves a branch-based loopless generator. The construction grew from an earlier informal public exposition by the author. Viewing horizontal position in the tree as time then explains each stack-slot write as a prediction for the next activation at the same level. Finally, the two possible future roles---an inherited continuation for a right child and a default continuation for a left child---are scheduled together, leading to the two assignments of the published focus-pointer algorithm. The account is a reconstructed derivation, not a claim about the historical reasoning of Bitner, Ehrlich, or Reingold.

Authors: David Wajc

In this brief note, we close the asymptotic gap between known upper and lower bounds for fractional online matching under edge arrivals. We prove that the optimal competitive ratio for this problem is $1/2+Θ(1/n)$. The algorithm was suggested and analyzed by OpenAI's ChatGPT Sol based on a single prompt. The presentation was streamlined over a few hours, based on a back and forth discussion with the author, who assumes responsibility for any errors.

Authors: Paweł Górecki, Agnieszka Mykowiecka, Jarosław Paszek

The classical duplication episode clustering (EC) model introduced by Guigó et al. in the 1990s provides a foundational approach for inferring genomic duplication events crucial to understanding genome evolution. This model clusters single gene duplications from a collection of gene trees at locations in the species tree to minimize the total number of such locations, called duplication episodes. Here, we introduce NetEC, a novel extension of this problem to phylogenetic networks. To solve NetEC, we first develop a polynomial-time dynamic programming (DP) algorithm for testing whether a given set of network nodes can serve as episode locations. We then propose a main inference algorithm that utilizes this DP component to optimize the episode count; while the feasibility test runs in polynomial time, the full optimization has exponential worst-case complexity, and an optional heuristic mode is provided for larger instances. We also propose an extended episode analysis procedure that identifies additional genomic duplication candidates below reticulation nodes, complementing the main algorithm by resolving potential upward clustering of duplications induced by reticulation. We evaluate our method on simulated data and on an empirical Pandanales dataset comprising over 29,000 gene trees, demonstrating exact and accurate inference of genomic duplication events even in the presence of multiple reticulations.

Authors: John Burke, Ciaran McGoldrick

Current approaches to quantum search fail to deeply exploit extant structure in the underlying Hilbert space. Decomposing the search by this structure empowers new strategies and formulations for quantum search and algorithm design. We present a new decomposition technique acting directly on this structure by recursively decomposing the Hilbert space and constructing the search operator from reflections over the resulting partition. When initial and target states factorise over this partition, dynamics reduce to a single rotation in a two-dimensional plane at each level, with angle given by a scalar recurrence. This recurrence avoids error accumulation from separately bounding success probabilities at each level, yielding an exact state description enabling treatment of the recursion as a whole. We obtain the target state deterministically and derive oracle and non-oracle costs independently of the search setting. For unstructured search, our approach attains the simultaneously optimal $Θ(\sqrt{N})$ oracle and non-oracle gate counts. For spatial search on $d$-dimension grids, it recovers the $O(\sqrt{N})$ time for $d\geq3$ and the $O\bigl(\sqrt{N}(\log N)^{3/2}\bigr)$ bound of Aaronson and Ambainis for $d=2$. The exact description of the recursion extends over our decomposition to new subdivision structures and provides a new approach for applying and analysing recursion in quantum algorithm design.

Authors: Wenxuan Tao, Jianan Wang, Fen Zuo

Quantum states with conserved total spins, or spin eigenfunctions, are important for studying quantum chemistry and quantum manybody physics problems. A typical class of spin eigenfunctions are Dicke states, which attain maximal spins. While we already have many efficient quantum algorithms to prepare Dicke states, it is not yet clear if we could do so for arbitrary spin eigenfunctions deterministically. Generalizing Bärtschi and Eidenbenz's elegant algorithms for Dicke state preparation, we successfully prepare arbitrary spin eigenfunctions characterized by branching paths and binary spin trees. As a byproduct, we also develop the corresponding classical algorithms to reconstruct all these spin states.

Authors: Rong-Hua Li, Meihao Liao, Yichun Yang

We study spectral density estimation for the normalized adjacency matrix of an unweighted graph under local access model. Previously, Cohen-Steiner et al. [KDD 2018] proposed an algorithm for $\varepsilon$-approximate spectral density estimation in the Wasserstein-1 distance, using $2^{O(1/\varepsilon)}$ local queries to the graph. In this paper, we prove that every constant-success estimator with Wasserstein--$1$ error at most $\eps$ requires $2^{Ω(1/\eps)}$ queries, showing that the Cohen-Steiner algorithm is optimal up to constant in the exponent. This resolves the open problem left by previous researches Jin et al. [COLT 2023] and Peng et al. [COLT 2026]. We then turn to quantum local access model. We give an $\widetilde O(\eps^{-3})$-query algorithm estimating the spectral density with Wasserstein-1 error at most $\eps$. Finally, we prove a $\widetildeΩ(\eps^{-4/3})$ quantum lower bound when the graph is sufficiently large. As a result, quantum local access model changes the dependence on $\eps$ from exponential to polynomial.

Authors: Ganesh P Kumar

The uniform car-parking process is the one-dimensional random sequential adsorption of unit cars on a segment of finite length $s$: cars arrive at uniformly random positions and park wherever they fit, until no gap admits another. This paper develops the exact finite-$s$ theory. The joint density of the parked positions is resolved into jamming cells, on each of which it is a rational function, and evaluated by a subset recursion in $O(2^n n)$ operations; the marginal and gap order statistics are obtained as hyperlogarithms whose weight is fixed by the number of coordinates integrated out; and the absorption count and the aggregate quantities are treated through the integral equation descending from Rényi.

Authors: Julia Baligacs, Bartłomiej Bosek, Paweł Putra, Marek Sokołowski, Anna Zych-Pawlewicz

We study one-sided online bipartite matching with recourse. In this setting, one side of a bipartite graph is known in advance, while vertices on the other side arrive online together with their incident edges. After each arrival, the algorithm must maintain a maximum-cardinality matching while minimizing the total number of reallocations, also known as the recourse budget. Despite extensive work, the exact recourse complexity of the problem remains unsettled: the best lower bound is $Ω(n \log n)$, whereas the best upper bound is $\mathcal{O}(n \log^2 n)$, where $n$ denotes the number of online vertices. Tight upper bounds of $\mathcal{O}(n \log n)$ are known only for restricted graph classes, such as forests. The best known upper bounds are attained by a very simple and natural algorithm SAP, which after each arrival applies a shortest augmenting path, and it is conjectured to be optimal. All known upper bound analyses of this algorithm do not depend on the particular maximum matching maintained by the algorithm. Consequently, they also apply to a more difficult problem, which we call the malicious matching setting: after each arrival, the maintained matching is replaced by a worst-case maximum matching for the next step. This led to the conjecture that the malicious setting still admits an $\mathcal{O}(n \log n)$ recourse bound, in line with the conjectured optimal complexity of the original model. Our main result is an $Ω(n \log^2 n)$ lower bound for the malicious matching setting, thus disproving the conjecture. Together with the previous upper bound, this settles the asymptotic recourse complexity of the malicious variant of the problem. We complement our lower bound with an upper bound of $\mathcal{O}(n \log n)$ for expander graphs.

Authors: Amir Carmel, Yakov Kosoburd, Robert Krauthgamer

The 3SUM problem asks, given sets $A,B,C$ of integers, whether there exist $a\in A$ and $b\in B$ whose sum belongs to $C$. In the preprocessed variant with unknown $C$, one preprocesses sets $A$ and $B$, each of size $n$, and subsequently answers a query specified by subsets $A'\subseteq A$, $B'\subseteq B$ and a target set $C'$ of size $O(n)$, by solving the 3SUM instance $(A',B',C')$. Kirkpatrick, Kuszmaul, Mathialagan, and Vassilevska Williams [ICALP 2026] gave the first algorithm with subquadratic space for this problem, achieving $\tilde{O}(n^{3/2+ε})$ query time using $\tilde{O}(n^{2-2ε/3})$ space, for every $ε\in[0,1/2]$. Their algorithm employs separate mechanisms for heavy and light targets, and for each heavy target it stores explicitly the list of pairs $(a,b)$ summing to it; these lists dominate the space bound. We present a unified construction that uses a single mechanism for all queries. Instead of storing these lists of pairs, we recover them on demand by leveraging the Fiat--Naor data structure [SICOMP 1999] to invert the function $(a,b)\mapsto (a+b\bmod p)$. This simplification improves the space bound to $\tilde{O}(n^{\max(2-ε, 11/6-ε/3)})$, while maintaining the same query time. Moreover, our construction is the first to achieve subquadratic space while supporting adaptively chosen queries.

Authors: Mina Khoshmehr, Fernando Beltran

In many practical deployments of differential privacy, queries do not arrive all at once. We study online differentially private query answering under a finite zero-concentrated differential privacy (zCDP) contract. In this setting, queries arrive sequentially, carry different accuracy thresholds, and may overlap with information already released. We formulate this setting as residual privacy budgeting: for each arriving query, the mechanism first credits reusable support from previous DP outputs and then spends new budget only on the remaining support required to satisfy the current threshold. The controller separates feasible cases, where the minimal residual support is allocated exactly, from scarcity cases, where a weighted shortfall-conservation optimiser assigns limited support according to query difficulty. We define the weight using the Query Influence Factor (QIF), a diagnostic signal for query difficulty and instability rather than query importance. For scalar Gaussian exact reuse, inverse-variance fusion justifies additive support. We prove zCDP composition, residual minimality, 1-competitiveness against the offline optimum in the feasible regime, and avoidable expenditure for allocators that ignore released history. A scarcity impossibility result shows that no online allocator can guarantee a competitive ratio better than 1/n in threshold satisfaction, contextualising the QIF scarcity layer as a design choice for an inherently hard online problem.

Authors: Sihan Wang

We prove that for every fixed inverse temperature $β< 1 / 2$, with high probability over the disorder, the single-site Glauber dynamics for the $n$-spin Sherrington-Kirkpatrick model mixes from every initial configuration to within total variation distance $\varepsilon$ in $O_β\left(n \log\left(n / \varepsilon\right)\right)$ steps. The bound holds uniformly over all external fields and is optimal up to constants depending only on $β$. The main ingredient is a deterministic criterion for optimal-order Poincaré inequalities in general Ising models, established via the integrated Bakry-Émery criterion together with a new two-spin estimate. A standard application of the localization-scheme framework of Chen and Eldan then upgrades the Poincaré inequality to a modified log-Sobolev inequality, yielding the optimal mixing-time bound. The main ideas underlying the proof of the Poincaré inequality were generated by GPT-5.6 Sol Ultra.

Authors: Mohsen Ghaffari, Cheng Jiang

A longstanding limitation of known techniques for parallel derandomization was that they incurred at least polylogarithmic overhead in work. For instance, for fundamental and frequently used problems such as maximal independent set, maximal matching, and $(Δ+1)$-coloring, where $Δ$ denotes the maximum degree of the graph, the best-known deterministic parallel algorithms with polylogarithmic depth used $Ω((m+n)\mathrm{poly}(\log n))$ work on $n$-vertex, $m$-edge graphs; see, e.g., Luby [FOCS '88]. Consequently, at least $\mathrm{poly}(\log n)$ processors were needed for these algorithms to outperform straightforward single-processor algorithms. Recently, Ghaffari and Grunau [FOCS '25] introduced a new parallel derandomization method that substantially reduced the overhead from $\mathrm{poly}(\log n)$ to $\mathrm{poly}(\log\log n)$, achieving work bounds of $O((m+n)\mathrm{poly}(\log\log n))$. In this paper, we settle this line of research by obtaining linear work bounds of $O(m+n)$, thereby achieving truly work-efficient parallel derandomization.

Authors: Janina Reuter

We present an algorithm with a natural geometric interpretation for computing the determinant of a matrix $B\in\mathbb{Z}^{d\times d}$. It improves upon the current fastest deterministic algorithms by a factor of $d^{ω(1)+1-ω(2)}\approx d^{0.1213}$, where $ω(k)$ denotes the exponent required for multiplying a $d\times d$ matrix with a $d\times d^k$ matrix. Our approach builds on a recent result of Klein and Reuter (STOC 2025), who introduced a novel algorithmic idea for lattice basis computation that can be viewed as extending the Euclidean algorithm from $\mathbb{Z}$ to $\mathbb{Z}^d$. By adapting their techniques, we compute the determinant with the same bit complexity as applying the generalized Euclidean algorithm to an input matrix $A\in\mathbb{Z}^{d\times 2d}$ with $\|A\| = \|B\|$, namely $\tilde{O}(d^{ω(2)}\log\|B\|)$. Prior to this work, the fastest deterministic algorithm for computing the determinant required $\tilde{O}(d^{ω(1)+1}\log\|B\|)$ bit operations.

Authors: Rikuya Hamai, Yuto Nakashima, Shunsuke Inenaga

Fine and Wilf [Proc. Amer. Math. Soc. 1965] showed that any string of length at least $p+q-d$ with periods $p$ and $q$ also has period $d=\gcd(p,q)$. For parameterized strings, Apostolico and Giancarlo [Discrete Appl. Math. 2008] proved an analogue with length bound $p+q$, assuming that the two induced bijections commute. Ideguchi et al. [SPIRE 2023] removed this assumption and gave the bound $p+q+\min(p,q)(σ-1)$, where $σ$ is the number of distinct letters. This was later improved by Hamai et al. [SPIRE 2024] to $p+q+\min(p,q)(σ-2)$, which was used to bound the number of non-equivalent parameterized squares. In this paper, we establish the optimal Fine--Wilf type bound for parameterized strings. Namely, if a string $s$ containing $σ$ distinct letters has parameterized periods $p$ and $q$ and satisfies $|s| \ge p+q+(σ-3)d+1$, where $d=\gcd(p,q)$, then $d$ is also a parameterized period of $s$. We also give matching lower-bound instances, proving that our bound is optimal for any $σ\geq 2$.

Authors: Morteza Alimi

We study the rounding of a supplied half-integral feasible solution of the root-assignment bidirected cut relaxation for Steiner Forest (Forest-BCR). Byrka, Grandoni, and Traub [IPCO 2025] proved a $16/9$ guarantee for a recursive framework that normalizes the LP point, selects a vertex set of maximum projected LP density, buys a minimum spanning tree on that set, contracts it, and recurses. We prove that the same framework has guarantee $8/5$. The new analysis keeps the orientation and the root label of each projected half-unit of LP mass. In a simple projection, the cut constraints at a terminal of degree two determine the root-assignment vector of every demand incident with it, and half-integrality leaves only two possibilities: a unit assignment to one root, which forces excess outdegree inside that root's support, or a split assignment to two roots, which forces overlap between their supports. For every connected component $C$ of the split-root graph this yields $ β_C\ \ge\ \frac{L_C}{2}$, where $β_C$ is the circuit rank of the union of the root supports in $C$ and $L_C$ is the number of its vertices of degree two in the full projection. Balancing the density certificate obtained from this inequality against the ordinary degree sum gives a vertex set of density at least $5/8$, and the inherited contraction lemma turns that into the $8/5$ rounding. For every $q\ge3$ we also construct a normalized half-integral point whose maximum projected density is exactly $5q/[2(4q-1)]$, so the universal projected-density bound is asymptotically tight.

Authors: Alexander Taveira Blomenhofer, Benjamin Lovitz

We show that border rank is equal to rank for Kruskal tensors. We also give an analogous Kruskal condition for alternating tensors, which certifies uniqueness of skew rank decompositions. Furthermore, we show that border skew rank is equal to skew rank for alternating Kruskal tensors, and we give an algorithm to find the minimum skew rank decomposition of alternating Kruskal tensors.

Authors: Clemens Eisenhofer, Yuwen Jia, Daniel Kroening, Sergey Pupyrev

Modern machine learning compilers select tensor memory layouts to minimize execution cost under hardware constraints. Layout selection is global: an operator may be fastest under one layout while its consumers prefer another, and aligning these preferences requires explicit layout conversions that can hurt model performance. Despite its practical importance, layout selection lacks a formal basis, so current compilers rely on ad-hoc heuristics. This paper presents the first formal study of layout selection in machine learning compilers. We formulate the problem as combinatorial optimization over dataflow graphs, minimizing the sum of operator execution costs and the per-tensor cost of these conversions. Our theoretical analysis shows that optimal layout selection is computationally hard, even for programs containing only matrix multiplications over two-dimensional tensors. We design an optimal polynomial-time algorithm for dataflow graphs of bounded treewidth. For general instances, we give a weighted MaxSAT encoding that an off-the-shelf solver can optimize. The formulation unifies several existing layout optimization strategies, including XLA's layout assignment, partition dimension selection in systolic array compilers, and layout planning in mobile GPU optimizers. We implement the formalization in a production compiler for an AI accelerator and measure the execution time of the compiled models under greedy heuristics, the compiler's rule-based strategy, and an optimal solver. Simple heuristics degrade execution time by up to $5\times$ on some workloads. Where the compiler's cost model is accurate, the solver matches or beats the rule-based strategy. On workloads with complex data movement it falls behind, and since the solver minimizes the stated objective exactly, that gap isolates cost-model error from search quality, showing where compiler effort actually pays off.

For a very long time, my favorite activity was to sit and think about mathematical questions. Staring at a blank sheet of paper, trying to grasp in my mind abstract concepts, bouncing ideas off colleagues and students. There is nothing quite like the feeling that you are exploring the unknown by only using your mind. 

Mathematicians have different styles and motivations for doing math. For some, it is about the challenge of solving hard problems. Others might have some application in mind, or a question they feel compelled to find the answer to. But I believe that none would stick with this profession if they did not find the process of doing mathematics satisfying. We cannot deny that this process is going through a profound change with AI. Some mathematicians have been meeting this change with excitement, while others with grief. I share both sentiments.

When considering the future of math (and science at large), it is worth reflecting on its past. For centuries, mathematicians and scientists typically worked under the patronage of nobles and royals: Archimedes advised King Hiero II, al-Khwarizmi was supported by the Abbasid caliphs, and Galileo by the Medicis, while medieval universities remained largely teaching institutions. It was only after the emergence of the royal academies and research universities from the seventeenth century onwards that scientists were paid by the state for pure research. Beyond patrons and academies, scientists have supported themselves in varied ways: military engineering (Archimedes), day jobs in law (Fermat), personal wealth (Darwin), the Royal Mint (Newton), tax farming (Lavoisier), and of course, examining patents.

But if there is one constant that has held true from Archimedes to our time, it is the importance of a scientific community. Scientific communication evolved from personal correspondence and networks of letters, through academies, to modern journals. But throughout this evolution, scientists valued the community of their peers.

What these communities focused on has changed over time. These days proving theorems is considered the prized activity in mathematics, but throughout much of history, the focus was on calculations or solving problems, rather than rigor. In the sixteenth century, Italian mathematicians earned jobs through equation-solving duels, which caused them to keep formulas such as the solution to the cubic equation secret. Euclid and al-Khwarizmi are known to this day not because of their new discoveries as much as for organizing known results.

Today, there are many self-selected and self-organizing scientific communities, which set up their own publication venues, norms, and processes. They are by and large self-governing, and each scientist chooses in which of these communities to participate. The university, which typically pays the scientist’s salary, largely defers to the judgment of their community as to the value of their work. Together with the mechanism of tenure, this leads to a remarkable lack of direct employer oversight of scientists’ output. 

Many discussions of science’s culture, including peer review, the publication process, and tenure, focus on their various defects and problematic cases. Yet science has been immensely successful. To use AI terminology, the last “pretrain” humanity got was hundreds of thousands of years ago with Homo sapiens (internal codename: homo-erectus-v5-pro-max). And yet we have managed to advance so much on that basis.

I am also surprised by how we managed to keep science legible. Theories like general relativity and quantum mechanics are the results of hundreds, if not thousands, of years of work by humanity’s most brilliant scientists and mathematicians. And yet we are able to routinely teach them to undergraduate students.

Impact of AI on Math

At this point, it is undeniable that AI can make significant contributions to solving mathematical problems. Solving open problems has been a prized activity in mathematics for a long time. One reason is that it is the easiest way to verify that one has done something that is both novel and interesting. And if we’re lucky and the problem was chosen well, the solution will not be a highly specific trick, but a more general insight or technique that can be used broadly. However, this does not mean that solving open problems is the only or even the most important contribution, and thankfully the “inefficiency” of the mechanisms for evaluating researchers allows many other types of contributions to still flourish.

For the same reason as above, solving open problems with AI is a straightforward way to dispel the skepticism of people who believe it cannot do research-level mathematics. But once we go beyond such skepticism, it is not clear that solving open problems should be the only or even the main use of AI. If you hope or believe AI is inherently incapable of posing problems, writing exposition, or building theories, then you are bound to be disappointed. 

What does this mean for mathematics and the role of human mathematicians? There have been radically different responses to this. On one extreme, Weinreich called for a “total opposition to artificial mathematics,” and in particular for mathematics departments to “[establish] anti-AI policies for student work, [reserve] hire lines for mathematicians who eschew AI, [and value] AI-free papers more highly in tenure promotion.” (It is unclear if, under his proposal, “AI-free” papers would be allowed to cite results that did use AI.) On the other hand, Tao said that AI will change how we do math, and that “we do have to somehow let go of conventional assumptions of what intellect is.”

Weinreich’s point of view resonates with the view of mathematics as an art, which is about human expression. On the other hand, many of the strongest mathematicians in history, including Archimedes, Newton, Euler, Gauss, and von Neumann, had a deep interest in its applications. If you care about mathematics’ applications, eschewing AI-enabled discoveries is not an option. Hence, I do not believe that an AI-free vision of mathematics, of the type promoted by Weinreich, is a viable future for it as an academic field. Recreational and competitive mathematics will have different standards, but the lessons of chess (which is actually thriving!) suggest that a complete rejection of AI is unwise even in these domains.

This does not mean that we will have no need for human mathematicians. As mentioned above, the modes of scholarship and funding models for mathematicians have changed over the years, and can change again. In particular, education has long been one of the primary missions and occupations of mathematicians, and it will be as important as ever. If we want (as I do) humans to keep control of their destiny, an educated society will be only more important as AI systems become more powerful.

I believe that human curiosity and legibility will also continue to play a crucial role in science and mathematics. One lesson from history is that it’s extremely hard to predict which directions will have practical applications, and the answers to questions pursued out of pure intellectual curiosity can have great practical impact. In 1940, the mathematician G. H. Hardy wrote that “Real mathematics has no effects on war. No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems very unlikely that anyone will do so for many years.” Needless to say, since then people have found many useful, and even warlike applications for these fields, and in particular GPS and public-key cryptography.

Given the track record of curiosity-based science, it would not be wise to eliminate humans from this process and replace them with “artificial scholarly communities” any time soon. Even if it were possible to get the same value, given the unpredictability and time lag of basic science applications, we will not be able to verify this in the near future. Also—and here I am biased—curiosity-based science is good in itself. Number theory is beautiful and would have been beautiful even without cryptography.

Could humans even keep up with understanding AI advances? I believe the answer is yes. Humans have always developed increasingly powerful abstractions to handle complexity. This is the only way we can use brains much like those of our cave-dwelling ancestors to grasp quantum mechanics, write complex software, manage companies, and organize societies many orders of magnitude larger than they did. Abstraction is what allowed us to compress thousands of years of scientific progress into an undergraduate program, and will allow AI to compress its findings and make them legible to us. It may well be that such levels of abstraction will mean that we do not always follow all steps of a proof, just like we do not verify today that a program correctly multiplied two large numbers.

AI will impact much more than science and math. Mathematicians are people too, and they face many greater risks (as well as potential benefits) from AI than those related to its impact on their profession. If AI leads (as I very much hope) to a flourishing human society, then it would be one that values education, curiosity and creativity. We might not explore math using a blank sheet of paper in the same way as I did as a graduate student, but we would still be making and sharing new discoveries. Emma Goldman is often (mis)quoted as saying “If I can’t dance, I don’t want to be part of your revolution.” Similarly, I don’t want to be part of an AI revolution that has no room for human scientists, mathematicians, or artists.

By Boaz Barak

Authors: Madina Kojanazarova, Sidaty El Hadramy, Philippe C. Cattin

Accurate soft tissue simulation is essential for surgical training, pre-operative planning, and haptic feedback systems. While learning-based surrogate models trained on data using the finite element method (FEM) offer a promising path to real-time inference, their reliability depends on well-calibrated constitutive models. Existing approaches neither provide systematic guidance on model selection across stiffness levels, nor generalize across different tissue stiffnesses or geometries. We perform a comprehensive calibration of hyperelastic constitutive models in the SOFA Framework using gravity-loaded silicone beams with different stiffnesses. Using calibrated simulations as training data, we use a softness conditioned equivariant graph neural network, enabling deformation and force prediction across multiple tissue types and unseen geometries. Our model achieves sub-millimeter mean deformation accuracy at 0.010s inference time, while showing that force prediction quality is directly tied to upstream calibration consistency.

Authors: Luciano Melodia

Magnitude homology is graded by length and knows nothing of persistence. Its persistent refinement knows nothing of where its bars begin and end. We show that the two are one construction: filtering the length nerve by sublevel sets of the length yields the persistence module, and the associated graded of that filtration is the magnitude complex. A long exact sequence exchanges them, and each side gains what it lacked. Magnitude homology locates the critical values of the barcode, so a graded computation lists the lengths at which an endpoint can occur, and the barcode acquires a stability estimate of $(n+1)δ$ in degree $n$ under a perturbation of size $δ$, while a computed perturbation moves a barcode by more than $δ$, so the factor cannot be dropped. We apply this to quantitative equational theories, whose free algebras are metric spaces built from syntax: an inclusion of theories induces a morphism of the presenting monads and a comparison of barcodes with an explicit bound, so the invariant measures axiomatic strength. Four examples are computed, one in every degree.

Authors: Anagha Gokul, Jason Hartline, Lunjia Hu, Jonathan Ullman, Yifan Wu

Calibration requires probabilistic reports to be conditionally unbiased and reliably interpretable as probabilities. A calibration measure assigns numerical error to miscalibrated reports. Haghtalab et al. (2024) proposed an approximately truthful calibration measure for online prediction, leaving open whether exact truthfulness is compatible with completeness and soundness. We resolve this question negatively for sequential binary prediction: exact truthfulness is incompatible with completeness and soundness, even for independent outcomes. We then show that this impossibility is specific to exact truthfulness. We give two general reductions from a base calibration measure, producing additively and multiplicatively approximately truthful calibration measures, respectively. Applying the multiplicative reduction, for every $0 < \varepsilon < 1$ we construct a sound and complete calibration measure that is $(1+\exp(-T^{(1-\varepsilon)/2}/2))$-multiplicatively truthful. This improves the approximate-truthfulness guarantee of Haghtalab et al. (2024).

Authors: Patricio Asenjo, Sergio Cavero, Mauricio Soto-Gomez, Christopher Thraves Caro

We study \emph{$T$-Robinson spaces}, a tree-based generalization of Robinson spaces in which every path of a compatible tree induces a Robinson subspace. This framework extends the classical notion of Robinsonian representations from linear orderings to tree structures, allowing the modeling of hierarchical and branching data. We establish a complete combinatorial characterization of $T$-Robinson spaces by proving their equivalence with several graph- and hypergraph-theoretic properties. In particular, we show that a dissimilarity space is $T$-Robinson if and only if all its level graphs are dually chordal with a common compatible tree. Combined with the characterization of hypertrees established by Brucker~\cite{brucker2005hypertrees}, this yields the equivalent characterization in terms of the associated cluster, ball, and 2-ball hypergraphs being hypertrees. Building upon these structural results, we develop a recognition algorithm with complexity \(O(K n^{2})\), where \(K\) denotes the number of minimum spanning trees of the dissimilarity space, improving upon existing hypertree-based approaches whenever \(K\) remains moderate. We further introduce a quantitative measure of $T$-Robinson structure that evaluates the extent to which an arbitrary dissimilarity space admits a tree-like representation. Finally, we discuss applications to real-world datasets, illustrating how $T$-Robinson spaces provide an interpretable framework for analyzing and organizing relational data.

Authors: Zhiyi Huang, Kaifeng Lin, Qinpei Lou, Xinyue Xiang, Peilin Yang

Consider a set of bins and two-choice balls arriving by a Poisson process. We must allocate each incoming ball immediately to one of two incident bins. For a given function $f$ and every bin, we aim to bound the expectation of $f(L)$---where $L$ is the bin's final load---based on the arrival rate of balls incident to that bin. We call this problem Generalized Balls into Bins, capturing many problems as special cases including the original Balls into Bins by Azar et al. (1994) and Online Stochastic Matching by Feldman et al. (2009). We show that Greedy provides optimal amortized bounds for all convex and concave functions $f$. Further, we propose another algorithm that achieves non-trivial bounds without amortization. As an application, we design a competitive algorithm for a stochastic model of completion time minimization on unrelated machines.

Authors: Felix Rauh, Jannik Matuschke, Hande Yaman

Planning accessible public services such as health care, emergency response, and schools often requires not only choosing where to open facilities but also improving the network that connects people to them, for example upgrading flood-prone roads in vulnerable regions. Most location models, however, take the network as fixed and the budget as given. We study the Maximum Covering Network Design Problem, in which a single budget is shared between opening facilities and upgrading weak links to maximize the population within a target travel distance of an open facility. The problem is hard even on the simplest networks, and planners usually want to see how coverage grows with the budget, not a single plan. We develop an exact dynamic-programming framework that exploits a property common to real road networks: their low connectivity, with many cut points whose removal disconnects the network. On trees, the recursion is self-contained: each state reduces to a few simple facility and upgrade choices that are fast to compute without a solver, giving predictable running times; for larger budgets and travel distances it outperforms solving the MILP formulation directly. On general low-connectivity networks, the framework decomposes the problem at the cut points and embeds a given MILP formulation to solve the resulting pieces, coordinating them through coverage conditions at the interfaces. This lets us compare a formulation on its own against the same formulation inside the framework: across 306 test cases the framework matches or outperforms direct solving on more than 80% of instances. Because it evaluates all budget levels in a single run, it also yields the full coverage-versus-budget curve at no extra cost, whereas direct solving must split its time across individual budgets.

Authors: Aryan Esmailpour, Khoi Le, Stavros Sintos

Bipartite graphs are a fundamental representation for relational data arising in recommendation systems, social networks, and communication graphs. A key challenge in these settings is to store and transmit large bipartite graphs compactly while preserving exact structural and path information. We study biclique-based representations of bipartite graphs $\boldsymbol{G}=(\boldsymbol{V},\boldsymbol{U},\boldsymbol{E})$, where the edge set is encoded using a collection of complete bipartite subgraphs. We focus on the Weighted Biclique Covering problem, which minimizes the total number of vertices used across all bicliques, and introduce a generalized variant that additionally penalizes the number of bicliques, capturing practical overheads in storage, transmission, and model complexity. While the weighted biclique covering problem is known to be $\mathsf{NP}$-Complete, we show that the generalized variant is also $\mathsf{NP}$-Complete. Despite this hardness, many real-world bipartite graphs admit low-dimensional geometric embeddings or can be well approximated by them. Leveraging this observation, we develop the first approximation algorithms with provable guarantees for the (generalized) weighted biclique covering problem on geometric bipartite graphs. Specifically, for $δ$-disk bipartite graphs in low-dimensional $\ell_\infty^d$ spaces, we design a polynomial-time algorithm that achieves an $O(\log |\boldsymbol{U}| \cdot \log^d |\boldsymbol{V}|)$-approximation, combining ideas from greedy set cover, geometric range searching, and densest subgraph optimization. We also show how our algorithms extend to $\ell_α^d$ metrics for any $α\geq 1$. Finally, we evaluate our algorithms on real-world bipartite datasets and show that they efficiently compute significantly smaller biclique-based representations than natural baselines, while scaling to large graphs.

Authors: Ethan N. W. Epperly

The randomly pivoted Cholesky algorithm is one of the leading methods for computing a low-rank approximation to a large positive-semidefinite matrix. However, while it consistently achieves accuracy comparable to or better than competing methods of its type in experiments, its theoretical analysis lags somewhat behind other methods. This paper closes this gap, proving that randomly pivoted Cholesky produces an approximation with expected error within a $1+\varepsilon$ factor of the optimal rank-$r$ approximation in $\mathcal{O}(r/\varepsilon + r\sqrt{\log r})$ steps. This result nearly matches the optimal complexity $Θ(r/\varepsilon)$ for any low-rank approximation method based on a partial Cholesky decomposition (also known as a column Nyström approximation). The paper also presents bounds on the randomly pivoted Cholesky trace and spectral-norm errors that hold with high probability. The mathematical argument is largely due to GPT 5.6-Sol (Pro), with some refinements by the author.

Authors: Walid Ben-Ameur, Tijani Chahed, Shamisa Nematollahi

We study a stochastic multi-robot monitoring problem on a connected graph $G=(V,E)$, where each robot moves according to a Markov chain on $G$ and monitors the closed neighborhood of its current vertex. The performance of $r$ robots is evaluated in steady state via two objectives: average-case coverage (the expected number of covered vertices) and worst-case coverage (the minimum coverage probability over all vertices). We consider three models: independent homogeneous strategies, where all robots share the same stationary distribution; independent heterogeneous strategies, where robots use different stationary distributions; and centralized strategies, allowing arbitrary correlations between robot locations. For the heterogeneous model, we prove that maximizing average coverage is NP-hard even for two robots, and that replicating an easy-to-compute optimal homogeneous strategy yields a \(\left(1-\left(1-\frac{1}{r}\right)^r\right)\)-approximation for both objective functions in the heterogeneous setting; moreover, no polynomial-time algorithm can achieve a ratio better than \(1-\nicefrac{1}{e}\) unless \(\text{P}=\text{NP}\). Centralized strategies can exploit correlations to reduce redundancy. We develop a hierarchy of approximation factors: for any positive integer \(r'\le r\), writing \(r=hr'+b\) with \(0\le b

Authors: Deeparnab Chakrabarty, Cooper LaPorte, C. Seshadhri

We study the problem of estimating the number of hyperedges in an arbitrary $n$-vertex hypergraph using sublinear in $n$ queries. Note that the number of hyperedges, $m$, can be exponential in $n$. For $k$-uniform hypergraphs, estimating $m$ is equivalent to estimating the average vertex degree, a problem studied in Barhum's Master's thesis (Weizmann Inst., 2007) under the standard access model of sampling random vertices, querying vertex degrees, and accessing incident hyperedges. Barhum's techniques do not extend to arbitrary hypergraphs, and simple lower-bound examples show that the standard access model cannot yield strongly sublinear algorithms when hyperedges have unbounded size. To obtain non-trivial sublinear bounds, we consider a natural generalization of the access model called the \emph{dual access model}, which allows sampling (labels of) random hyperedges, querying edge sizes, and accessing vertices in a hyperedge. In this model, we give a randomized algorithm that returns a $(1+\varepsilon)$-approximation to $m$ with high probability, making $O(\varepsilon^{-2}\sqrt{n} + \sqrt{n}\log n)$ queries. Complementing our algorithm, we prove a nearly matching lower bound showing that $Ω(\sqrt{n})$ queries are necessary for any algorithm that obtains a constant factor approximation to $m$.

MATS Winter 2027 is a fully funded, 12-week AI safety research and field-building fellowship in Berkeley and London, with seven tracks, mentorship from researchers at Anthropic, Google DeepMind, OpenAI and more, a $6,400/month stipend, up to $16,000/month for technical participants, and housing, meals, travel and office space covered.

Website: https://www.matsprogram.org/apply?utm_source=cstheory-jobs&utm_medium=job-board&utm_campaign=w27
Email: applications@matsprogram.org

By shacharlovett

So yeah, Anthropic has announced that it’s now watermarking the outputs of Claude, using a scheme based on Google’s SynthID, which is in turn based on the Gumbel Softmax scheme that I proposed at OpenAI back in 2022—as far as I know, the first LLM watermarking proposal, though far from the last one. I’m gratified that Anthropic credits me for this, even though I shirked my duty by never publishing a paper about it (by the time I sat down to write one, it seemed like the whole field had already assimilated my scheme and moved beyond it—AI just moves too fast for me!).

For those who don’t know, watermarking means slightly changing the way that an LLM operates to insert a subtle signal that lets you prove later, with high statistical confidence, that a text indeed came from your specific LLM. It uses the randomness that’s already present anyway in LLM outputs, replacing some of it by pseudorandomness that favors certain word combinations over others in a way that’s later detectable, given only the sequence of tokens itself (not the prompt or the probabilities) along with the key of the pseudorandom generator. Christ, Gunn, and Zamir then substantially improved my scheme to get true cryptographic indistinguishability, and there have been other improvements since.

I’d been meaning to blog about this for days. Thankfully, Zvi Mowshowitz, the world’s foremost blogger about AI, has now written a wonderful post, entitled AI Text Watermarking Is Free And Good, which saves me from the need to write my own long post. In particular, Zvi masterfully explains the central point that I needed to explain to everyone back in 2022-23: why, contrary to many people’s intuitions, there’s no inherent tradeoff between watermarking and the quality of LLM output. Basically, nearly every LLM output was already a sample from a cloud of exponentially many possibilities, all of them about equally good, so there’s plenty of room to steer within that cloud without affecting anything that an ordinary user would notice. As my kids would put it, the math mathes.

As Zvi explains, the central technical drawback of watermarking schemes like the one I proposed, and what Anthropic is now using, is that it’s possible to remove the watermarks with a little extra work (even stuff as simple as, e.g., translating between English and French, asking the LLM for words interspersed with emojis and then removing the emojis, or using an open model to paraphrase the output). Zvi gives detailed arguments for why he expects watermarking to remain a net positive in practice despite this vulnerability.

I could add that, in addition, there’s recent progress (see here for example) on what I’ve called “semantic watermarking,” or watermarking at the level of the underlying concept vectors rather than the tokens themselves. This actually seems to work, albeit with no theoretical guarantees, and will hopefully make removing watermarks a lot harder—although the Barak et al. impossibility result suggests that under plausible assumptions, no LLM watermarking method will be completely foolproof.

Anyway, I worked out my scheme in Fall 2022, then gave lots of talks about it (including, as it happens, at Anthropic), and also worked with Hendrik Kirchner at OpenAI, who actually implemented and tested my scheme. Unfortunately, OpenAI leadership decided against deploying watermarking, worried mostly about risks to the product (i.e., customers disliking the idea, and leaving for a competing LLM that doesn’t watermark). You can read this Wall Street Journal investigation from two years ago for more. I was hopeful that the State of California was going to solve the collective-action problem by mandating watermarking for AI models, but then they decided to do that for audiovisual content only, for some reason exempting text.

Nevertheless, Google DeepMind implemented something very similar to my proposal in its SynthID, deployed in all its Gemini text models. But they heavily restricted who gets to detect the watermark, which made their admirable decision of limited use to my academic colleagues, who’ve been begging me for a way to detect whether their students are using AI to cheat. (For now, I mainly send them to Pangram, a leading AI detector not based on watermarking, as a first line of defense.)

And now, apparently to comply with EU regulations, Anthropic says they’ve deployed a watermarking scheme like mine where anyone will be able to do detection (though they also say in their FAQ that they’re still working on the detection API). Even OpenAI suggests that it plans to follow suit. So, four years after I seriously thought about this, it looks to my surprise like this is actually happening. Thanks, EU!

Tell you what: read Zvi’s post, and then whatever questions you still have, you can come here and ask in the comments. Just please don’t use Claude to write the comments. With any luck, I’ll eventually be able catch you if you do.

By Scott

We prove a common generalization of two structure theorems: the dimension-free decomposition theorem for idempotent Schur multipliers and the idempotent theorem in harmonic analysis. Roughly speaking, our result shows that an invariant integer-valued kernel with Hilbert-space factorization norm $\gamma$ admits a signed decomposition into at most $2^{O(\gamma^4)}$ elementary pieces. In the matrix setting these pieces are blocky matrices, while in the group setting they are indicators of cosets. In the locally compact abelian setting this quantitatively strengthens the theorem of Green and Sanders, while in the non-abelian setting it gives a quantitative strengthening of Host's idempotent theorem and, for finite groups, of Sanders's quantitative result. It also improves the exponent in the dimension-free matrix decomposition from $\gamma^6$ to $\gamma^4$.