Theory of Computing Report

Authors: Piotr Kawałek, Jacek Krzaczkowski

Most classical results in circuit complexity theory concern circuits over the Boolean domain. Besides their simplicity and the ease of comparing different languages, the actual architecture of computers is also an important motivating factor. On the other hand, by restricting attention to Boolean circuits, we lose sight of the much richer landscape of circuits over larger domains. Our goal is to bridge these two worlds: to use deep algebraic tools to obtain results in computational complexity theory, including circuit complexity, and to apply results from computational complexity to gain a better understanding of the structure of finite algebras. In this paper, we propose a unifying algebraic framework which we believe will help achieve this goal. Our work is inspired by branching programs and nonuniform deterministic automata introduced by Barrington, as well as by their generalization proposed by Idziak et al. We begin our investigation by studying the languages recognized by natural classes of algebraic structures. In particular, we characterize language classes recognized by circuits over simple algebras and over algebras from congruence modular varieties.

Authors: Amatya Sharma, Santhoshini Velusamy

We study the single-pass streaming complexity of deciding satisfiability of Constraint Satisfaction Problems (CSPs). A CSP is specified by a constraint language $Γ$, that is, a finite set of $k$-ary relations over the domain $[q] = \{0, \dots, q-1\}$. An instance of $\mathsf{CSP}(Γ)$ consists of $m$ constraints over $n$ variables $x_1, \ldots, x_n$ taking values in $[q]$. Each constraint $C_i$ is of the form $\{R_i,(x_{i_1} + λ_{i_1}, \ldots, x_{i_k} + λ_{i_k})\}$, where $R_i \in Γ$ and $λ_{i_1}, \ldots, λ_{i_k} \in [q]$ are constants; it is satisfied if and only if $(x_{i_1} + λ_{i_1}, \ldots, x_{i_k} + λ_{i_k}) \in R_i$, where addition is modulo $q$. In the streaming model, constraints arrive one by one, and the goal is to determine, using minimum memory, whether there exists an assignment satisfying all constraints. For $k$-SAT, Vu (TCS 2024) proves an optimal $Ω(n^k)$ space lower bound, while for general CSPs, Chou, Golovnev, Sudan, and Velusamy (JACM 2024) establish an $Ω(n)$ lower bound; a complete characterization has remained open. We close this gap by showing that the single-pass streaming space complexity of $\mathsf{CSP}(Γ)$ is precisely governed by its non-redundancy, a structural parameter introduced by Bessiere, Carbonnel, and Katsirelos (AAAI 2020). The non-redundancy $\mathsf{NRD}_n(Γ)$ is the maximum number of constraints over $n$ variables such that every constraint $C$ is non-redundant, i.e., there exists an assignment satisfying all constraints except $C$. We prove that the single-pass streaming complexity of $\mathsf{CSP}(Γ)$ is characterized, up to a logarithmic factor, by $\mathsf{NRD}_n(Γ)$.

Authors: Nicholas Kocurek, Shayan Oveis Gharan, Dante Tjowasi

We design an efficient sampling algorithm to generate samples from the hardcore model on random regular bipartite graphs as long as $λ\lesssim \frac{1}{\sqrtΔ}$, where $Δ$ is the degree. Combined with recent work of Jenssen, Keevash and Perkins this implies an FPRAS for the partition function of the hardcore model on random regular bipartite graphs at any fugacity. Our algorithm is shown by analyzing two new Markov chains that work in complementary regimes. Our proof then proceeds by showing the corresponding simplicial complexes are top-link spectral expanders and appealing to the trickle-down theorem to prove fast mixing.

Authors: Ishay Haviv

We study the kernel complexity of constraint satisfaction problems over a finite domain, parameterized by the number of variables, whose constraint language consists of two relations: the non-equality relation and an additional permutation-invariant relation $R$. We establish a conditional lower bound on the kernel size in terms of the largest arity of an OR relation definable from $R$. Building on this, we investigate the kernel complexity of uniformly rainbow free coloring problems. In these problems, for fixed positive integers $d$, $\ell$, and $q \geq d$, we are given a graph $G$ on $n$ vertices and a collection $\cal F$ of $\ell$-tuples of $d$-subsets of its vertex set, and the goal is to decide whether there exists a proper coloring of $G$ with $q$ colors such that no $\ell$-tuple in $\cal F$ is uniformly rainbow, that is, no tuple has all its sets colored with the same $d$ distinct colors. We determine, for all admissible values of $d$, $\ell$, and $q$, the infimum over all values $η$ for which the problem admits a kernel of size $O(n^η)$, under the assumption $\mathsf{NP} \nsubseteq \mathsf{coNP/poly}$. As applications, we obtain nearly tight bounds on the kernel complexity of various coloring problems under diverse settings and parameterizations. This includes graph coloring problems parameterized by the vertex-deletion distance to a disjoint union of cliques, resolving a question of Schalken (2020), as well as uniform hypergraph coloring problems parameterized by the number of vertices, extending results of Jansen and Pieterse (2019) and Beukers (2021).

Authors: Noah Weninger

In the knapsack interdiction problem, there are $n$ items, each with a non-negative profit, interdiction cost, and packing weight. There is also an interdiction budget and a capacity. The objective is to select a set of items to interdict (delete) subject to the budget which minimizes the maximum profit attainable by packing the remaining items subject to the capacity. We present a $(2+ε)$-approximation running in $O(n^3ε^{-1}\log(ε^{-1}\log\sum_i p_i))$ time. Although a polynomial-time approximation scheme (PTAS) is already known for this problem, our algorithm is considerably simpler and faster. The approach also generalizes naturally to a $(1+t+ε)$-approximation for $t$-dimensional knapsack interdiction with running time $O(n^{t+2}ε^{-1}\log(ε^{-1}\log\sum_i p_i))$.

Authors: Gianlorenzo D'Angelo, Riccardo Michielan

We study the efficient generation of random graphs with a prescribed expected degree sequence, focusing on rank-1 inhomogeneous models in which vertices are assigned weights and edges are drawn independently with probabilities proportional to the product of endpoint weights. We adopt a temporal viewpoint, adding edges to the graph one at a time up to a fixed time horizon, and allowing for self-loops or duplicate edges in the first stage. Then, the simple projection of the resulting multigraph recovers exactly the simple Norros--Reittu random graph, whose expected degrees match the prescribed targets under mild conditions. Building on this representation, we develop an exact generator based on \textit{edge-arrivals} for expected-degree random graphs with running time $O(n+m)$, where $m$ is the number of generated edges, and hence proportional to the output size. This removes the typical vertex sorting used by widely-used fast generator algorithms based on \textit{edge-skipping} for rank-1 expected-degree models, which leads to a total running time of $O(n \log n + m)$. In addition, our algorithm is simpler than those in the literature, easy to implement, and very flexible, thus opening up to extensions to directed and temporal random graphs, generalization to higher-order structures, and improvements through parallelization.

Authors: Eleanor Wiesler, Trace Baxley

We propose a learning-augmented framework for accelerating max-flow computation and image segmentation by integrating Graph Neural Networks (GNNs) with the Ford-Fulkerson algorithm. Rather than predicting initial flows, our method learns edge importance probabilities to guide augmenting path selection. We introduce a Message Passing GNN (MPGNN) that jointly learns node and edge embeddings through coupled updates, capturing both global structure and local flow dynamics such as residual capacity and bottlenecks. Given an input image, we propose a method to construct a grid-based flow network with source and sink nodes, extract features, and perform a single GNN inference to assign edge probabilities reflecting their likelihood of belonging to high-capacity cuts. These probabilities are stored in a priority queue and used to guide a modified Ford-Fulkerson procedure, prioritizing augmenting paths via an Edmonds-Karp-style search with bottleneck-aware tie-breaking. This avoids repeated inference over residual graphs while leveraging learned structure throughout optimization. We further introduce a bidirectional path construction strategy centered on high-probability edges and provide a theoretical framework relating prediction quality to efficiency via a weighted permutation distance metric. Our method preserves max-flow/min-cut optimality while reducing the number of augmentations in practice. We also outline a hybrid extension combining flow warm-starting with edge-priority prediction, establishing a foundation for learning-guided combinatorial optimization in image segmentation.

Authors: Amihood Amir, Ayelet Butman, Michael Itzhaki, Dina Sokol

This paper addresses the problem of identifying palindromic factors in texts that include wildcards -- special characters that match all others. These symbols challenge many classical algorithms, as numerous combinatorial properties are not satisfied in their presence. We apply existing wildcard-LCE techniques to obtain a continuous time-memory tradeoff, and present the first non-trivial linear-space algorithm for computing all maximal palindromes with wildcards, improving the best known time-memory product in certain parameter ranges. Our main results are algorithms to find and approximate all maximal palindromes in a given text. We also generalize both methods to the $k$-mismatches setting, with or without wildcards.

Authors: Alexander Zlokapa

Estimating local observables in Gibbs states is a central problem in quantum simulation. While this task is BQP-complete at asymptotically low temperatures, the possibility of quantum advantage at constant temperature remains open. The Sachdev-Ye-Kitaev (SYK) model is a natural candidate: at any constant temperature, its Gibbs states have polynomial quantum circuit complexity and are not described by Gaussian states. Rigorous analyses of the SYK model are difficult due to the failure of known techniques using random matrix theory, cluster expansions, and rigorous formulations of the quantum path integral and replica trick. Despite this, we give a rigorous proof of a quasipolynomial-time classical algorithm that estimates SYK local thermal expectations at sufficiently high constant temperature. Our result introduces a new Wick-pair cluster expansion that we expect to be broadly useful for disordered quantum many-body systems.

We prove a lower bound of $\Omega\left(n^{1.5}\right)$ for the number of product gates in non-commutative arithmetic circuits for an explicit $n$-variate degree-$n$ polynomial $f_{n}$ (over every field). We observe that this implies that over certain non-commutative rings $R$, any arithmetic circuit that computes the induced polynomial function $f_{n}: R^n \rightarrow R$, using the ring operations of addition and multiplication in $R$, requires at least $\Omega\left(n^{1.5}\right)$ multiplications. More generally, for any $d\geq 2$ and sufficiently large $n$, we obtain a lower bound of $\Omega\left(d\sqrt{n}\right)$ for $n$-variate degree-$d$ polynomials, for both these models. Prior to our work, the only known lower bounds for the size of non-commutative circuits, or for the size of arithmetic circuits over any ring, were slightly super-linear in $\max\{n,d\}$: $\Omega\left(n\log d\right)$ by Baur and Strassen, and $\Omega\left(d\log n\right)$ by Nisan. (Nisan's bound was proved for non-commutative arithmetic circuits and implies a bound for arithmetic circuits over non-commutative rings by our observation).

July 3, 2026 University of Warwick, UK https://sites.google.com/view/algorithmscomplexitywarwick3/home Registration deadline: May 31, 2026 The workshop Algorithms & Complexity @ Warwick will be held at the University of Warwick on July 3, 2026. The aim of the event is to highlight several recent exciting advances in the field of Algorithms and Complexity and to facilitate interactions … Continue reading Algorithms and Complexity Workshop @ Warwick

By shacharlovett

After spending a week trying to figure out what to say in one lecture, I realized I could teach an entire class on architecture. In fact, in hindsight, that’s what this class should have been! Oh well. I knew this from the outset, but I couldn’t figure out how to stitch a syllabus together last December. Inevitably, I had to work my way through a full semester of cleaning out the skeletons in my learning-for-control closet before I could figure out what I wanted to dive more into. To be clear, this is a success story and a model of how teaching classes ought to go.

Given that I’m already committed to a schedule for next year,1 a class on architecture will have to wait a bit. But nothing stops me from putting together a syllabus now, right? While preparing this week’s lecture, I assembled an unfortunately long reading list for this hypothetical class. Synthesizing this material promises a very interesting story. Let me explain how I’m thinking about its contents.

Though architectural theory is figured out on the fly, adapting existing systems to manage newfound complexity, there are repeated patterns that we can extract from our contemporary human-cyber-physical infrastructure. The architecture class would attempt to synthesize the design principles needed for enabling diversity and error handling. The paper I referenced yesterday by Matni, Ames, and Doyle takes a stab at this sort of view, but I want to look beyond robotics. I’d want to cover as diverse a set of applications as possible while still maintaining some degree of cohesion.

I’d probably start with computing systems. You’ll get different answers about what is needed to build good architectures in your operating systems, programming languages, and networking classes. And maybe you should. I’ll keep repeating myself: I’m not convinced that there’s a “universal theory” of architecture. However, that doesn’t mean we can’t move up a layer of abstraction and draw the common threads together. What are the shared patterns in hardware, software, and network design? I’m particularly interested in studying the 75-year development of software from manually mapping bits on registers to the complex high-level languages of today. There are a lot of interesting theories on modularity, abstraction boundaries, and protocol design, and those should be thrown into the mix.

I’d also extend downward into the physical layer, adding a “cyberphysical” systems view that connects to larger systems like the power grid or transportation network (good references on these two topics are currently missing from the bibliography). I’d spend time on the history of architectures in robotics and control, where we have settled on a platform, arguably by the discipline-wide adoption of the Robot Operating System. The principles were there in the Apollo project: a separation between low-level control, sensing, navigation, and mid-level feedback, and high-level planning. There have been other proposed architectures, like Brooks’ subsumption architecture, that didn’t gain much traction beyond the Roomba. There is something inescapable about the standard three-level architecture, and I want to unpack more about this diversity-enabled sweet spot.

I would like to examine some architectural theories in systems biology, especially those of Gerhart and Kirschner. We’d have to at least read some parts of The Plausibility of Life, mostly because it’s really good. I also think that we do learn a lot by reflecting our technology onto biological systems. I’m sure we’ll find interesting examples and insights by seeing how others have done this.

I also want to look at how we engineer architectures for organizing people. The complexity of the corporation and the computer grew symbiotically, and there are clear influences of human organizational behavior on information technology. There’s clearly a co-evolution of computing architectures with human architectures. Herb Simon, who has had as much influence on management science as computer science, would be a key figure here.

And since I can’t pass up an opportunity to dig into more Cold War technological history, we’d look at some classic theorizing about complex systems. This class would not be an aughties-era complex systems class. But I’d like to find the point in time before the network science people split off from the cyberneticists. So we’d go back and read Wiener and Weaver, Ashby and Simon, and look at what they got right and what they missed.

The bibliography needs both growth and pruning. But I have plenty of time to get it in order. Help me flesh it out. What topics and references would you add? What other books on architecture, organization, protocols, and design should I throw on there? I’d love to see your suggestions in the comments.

Subscribe now

By Ben Recht

This post covers our new lower bound on the latency cost of censorship resistance. In a traditional BFT protocol, the leader has two roles: (1) It constructs (and therefore holds) the input; and (2) It proposes the input. Many BFT protocols optimize for the good case when the leader is honest. For partial synchrony, with $n \leq 5f-2$ parties, the good-case latency is 3 rounds. The leader’s monopoly over both...

By Ittai Abraham, Yuval Efron, and Ling Ren

In a previous post we decomposed PBFT into an outer shell and an inner shell consisting of two building blocks: Locked-Broadcast (LB) and Recover-Max-Lock. Here we similarly decompose Simplex into an outer shell and an inner shell consisting of a single building block: Graded-Broadcast (GB). The model is partial synchrony with $f<n/3$ Byzantine failures, and the goal is single-shot provable consensus with external validity. Single-shot Provable Consensus with External Validity...

By Ittai Abraham

Authors: Pratik Shastri

We prove that every fan-in $2$ noncommutative arithmetic circuit computing the palindrome polynomial has size $Ω(n^2)$. The proof builds on and refines a previous work of the author. The new ingredients in the proof were generated by Gemini 3.1 Pro.

Authors: Chia-Yu Chang, Fulvio Gesmundo, Jeroen Zuiddam

We determine the border subrank of higher order structure tensors of several families of algebras, and in particular obtain the following results. (1) We determine tight bounds on the border subrank of $k$-fold matrix multiplication and $k$-fold upper triangular matrix multiplication for all $k$. (2) We determine the border subrank of the higher order structure tensors of truncated polynomial algebras, null algebras, and apolar algebras of a quadric. (3) We determine the border subrank of the higher order structure tensors of the Lie algebra $\mathfrak{sl}_2$ for all orders. (4) We prove that degeneration of structure tensors of algebras propagates from higher to lower order. Along the way, we investigate which upper bound methods (geometric rank, $G$-stable rank, socle degree) are effective in which settings, and how they relate. Our work extends the results of Strassen (J.~Reine Angew.~Math., 1987, 1991), who determined the asymptotic subrank of these algebras for tensors of order three, in two directions: we determine the border subrank itself rather than its asymptotic version, and we consider higher order structure tensors.

Authors: Ka Ho Lai, Hei Tung Tsang, Gary P. T. Choi, Lok Ming Lui

Origami structures, particularly Miura-ori patterns, offer unique capabilities for surface approximation and deployable designs. In this study, a constrained mapping optimization algorithm is designed for designing surface-aligned Miura-ori via a narrow band approximation of the input surface. The Miura-fold, embedded in the narrow band, is parameterized to a planar domain, and a mapping is computed on the parameter pattern by optimizing certain energy terms and constraints. Extensive experiments are conducted, showing the significance and flexibility of our methods.

Authors: Nikola Milićević

We develop new aspects of the homological algebra theory for persistence modules, in both the one-parameter and multi-parameter settings. For a poset $P$ and an order preserving map $\varphi:P\times P\to P$, we introduce a novel tensor product of persistence modules indexed by $P$, $\otimes_{\varphi}$. We prove that each $\otimes_{\varphi}$ has a right adjoint, $\mathbf{Hom}^{\varphi}$, the internal hom of persistence modules that also depends on $\varphi$. We prove that every $\otimes_{\varphi}$ yields a Künneth short exact sequence of chain complexes of persistence modules. Dually, the $\mathbf{Hom}^{\varphi}$ also has an associated Künneth short exact sequence in cohomology. As special cases both of these short exact sequences yield Universal Coefficient Theorems. We show how to apply these to chain complexes of persistence modules arising from filtered CW complexes. For the special case of $P=\mathbb{R}_+$, the $p$-quasinorms for each $p\in (0,\infty]$ yield a distinct $\otimes_{\ell^p_c}$ and its adjoint $\mathbf{Hom}^{\ell^p_c}$. We compute their derived functors, $\mathbf{Tor}^{\ell^p_c}$ and $\mathbf{Ext}_{\ell^p_c}$ explicitly for interval modules. We show that the Universal Coefficient Theorem developed can be used to compute persistent Borel-Moore homology of a filtration of non-compact spaces. Finally, we show that for every $p\in [1,\infty]$ the associated Künneth short exact sequence can be used to significantly speed up and approximate persistent homology computations in a product metric space $(X\times Y,d^p)$ with the distance $d^p((x,y),(x',y'))=||d_X(x,x'),d_Y(y,y')||_p$.

Authors: Bernhard Haeupler, Slobodan Mitrović, Srikkanth Ramachandran, Wen-Horng Sheu, Robert Tarjan

This paper proves that a wide class of local search algorithms extend as is to the fully dynamic setting with an adaptive adversary, achieving an amortized $\tilde{O}(1)$ number of local-search steps per update. A breakthrough by Moser (2009) introduced the witness-tree and entropy compression techniques for analyzing local resampling processes for the Lovász Local Lemma. These methods have since been generalized and expanded to analyze a wide variety of local search algorithms that can efficiently find solutions to many important local constraint satisfaction problems. These algorithms either extend a partial valid assignment and backtrack by unassigning variables when constraints become violated, or they iteratively fix violated constraints by resampling their variables. These local resampling or backtracking procedures are incredibly flexible, practical, and simple to specify and implement. Yet, they can be shown to be extremely efficient on static instances, typically performing only (sub)-linear number of fixing steps. The main technical challenge lies in proving conditions that guarantee such rapid convergence. This paper extends these convergence results to fully dynamic settings, where an adaptive adversary may add or remove constraints. We prove that applying the same simple local search procedures to fix old or newly introduced violations leads to a total number of resampling steps near-linear in the number of adversarial updates. Our result is very general and yields several immediate corollaries. For example, letting $Δ$ denote the maximum degree, for a constant $ε$ and $Δ= \text{poly}(\log n)$, we can maintain a $(1+ε) Δ$-edge coloring in $\text{poly}(\log n)$ amortized update time against an adaptive adversary. The prior work for this regime has exponential running time in $\sqrt{\log n}$ [Christiansen, SODA '26].

Authors: Mohammad Abdulaziz, Thomas Ammer

We present an ongoing effort to build a framework and a library in Isabelle/HOL for formalising primal-dual arguments for the analysis of algorithms. We discuss a number of example formalisations from the theory of matching algorithms, covering classical algorithms like the Hungarian Method, widely considered the first primal-dual algorithm, and modern algorithms like the Adwords algorithm, which models the assignment of search queries to advertisers in the context of search engines.

Authors: Leon Kellerhals, Mitja Krebs, André Nichterlein, Stefan Schmid

We study the following problem that is motivated by demand-aware network design: Given a tree~$G$, the task is to find a binary tree~$H$ on the same vertex set. The objective is to minimize the sum of distances in~$H$ between vertex pairs that are adjacent in~$G$. We present a linear-time factor-4 approximation for this problem.

Authors: Sepehr Assadi, Helia Yazdanyar

A celebrated result of Johansson in graph theory states that every triangle-free graph of maximum degree $Δ$ can be properly colored with $O(Δ/\lnΔ)$ colors, improving upon the "greedy bound" of $Δ+1$ coloring in general graphs. This coloring can also be found in polynomial time. We present an algorithm for maintaining an $O(Δ/\lnΔ)$ coloring of a dynamically changing triangle-free graph that undergoes edge insertions and deletions. The algorithm is randomized and on $n$-vertex graphs has amortized update time of $Δ^{o(1)}\log{n}$ per update with high probability, even against an adaptive adversary. A key to the analysis of our algorithm is an application of the entropy compression method that to our knowledge is new in the context of dynamic algorithms. This technique appears general and is likely to find other applications in dynamic problems and thus can be of its own independent interest.

Authors: Grant Molnar

We define a multi-scale metric $d_ρ$ on strings by aggregating angle distances between all $n$-gram count vectors with exponential weights $ρ^n$. We benchmark $d_ρ$ in DBSCAN clustering against edit and $n$-gram baselines, give a linear-time suffix-tree algorithm for evaluation, prove metric and stability properties (including robustness under tandem-repeat stutters), and characterize isometries.

Authors: Yixin Cao, Peng Li

We present a polynomial-time algorithm for the cluster vertex deletion problem on chordal graphs, resolving an open question posed in different contexts by Cao et al. [Theoretical Computer Science, 2018], Aprile et al. [Mathematical Programming, 2023], Chakraborty et al. [Discrete Applied Mathematics, 2024], and Hsieh et al. [Algorithmica, 2024]. We use dynamic programming over clique trees and reduce the computation of the optimal subproblem value to the minimization of a submodular set function.

Authors: Hoang Ta, Hoa T. Vu

We establish nearly optimal upper and lower bounds for approximating decision tree splits in data streams. For regression with labels in the range $\{0,1,\ldots,M\}$, we give a one-pass algorithm using $\tilde{O}(M^2/ε)$ space that outputs a split within additive $ε$ error of the optimal split, improving upon the two-pass algorithm of Pham et al. (ISIT 2025). Furthermore, we provide a matching one-pass lower bound showing that $Ω(M^2/ε)$ space is indeed necessary. For classification, we also obtain a one-pass algorithm using $\tilde{O}(1/ε)$ space for approximating the optimal Gini split, improving upon the previous $\tilde{O}(1/ε^2)$-space algorithm. We complement these results with matching space lower bounds: $Ω(1/ε)$ for Gini impurity and $Ω(1/ε)$ for misclassification (which matches the upper bound obtained by sampling). Our algorithms exploit the Lipschitz property of the loss functions and use reservoir sampling along with Count--Min sketches with range queries. Our lower bounds follow from careful reductions from the INDEX problem.

Authors: Pavel Arkhipov, Vladimir Kolmogorov

We implement an algorithm for solving the minimum weight perfect matching problem. Our code significantly outperforms the current state-of-the-art Blossom V algorithm on those families of instances where Blossom V takes superlinear time. In practice, our implementation shows almost-linear runtime on every family of instances on which we have tested it. Our algorithm relies on solving the maximum-cardinality unweighted matching problems during its primal phase. Following the state-of-the-art cherry blossom algorithm, we use cherry trees instead of traditional alternating trees and cherry blossoms instead of traditional blossoms. We shrink cherry blossoms rather than traditional blossoms into supernodes. This strategy allows us to deal with much shallower supernodes.

Streaming algorithms in adversarial settings have attracted considerable attention recently. We show that, in the white-box adversarial streaming model [ABJ+22], the fundamental problem of estimating the $F_p$ moment to within any constant factor requires $\Omega(n)$ memory. In this model, the internal state of the (randomized) streaming algorithm is visible to an adversary, who can exploit this information when constructing subsequent stream updates. As a corollary, we also obtain a white-box lower bound for the well-studied problem of estimating the maximum matching size in graphs. [ABJ+22] proved that two-party white-box communication protocols can be derandomized. This allows them to prove deterministic communication lower bounds and automatically derive white-box (communication and streaming) lower bounds. However, such two-party lower bounds can only rule out approximation of the $F_p$ moment within a specific constant factor. Ruling out approximation within any constant factor typically requires proving a lower bound for a multi-party communication problem. We show that white-box communication protocols involving any number of parties can be derandomized, provided they compute a total function. However, this derandomization fails entirely when extended to partial functions and, consequently, to approximation problems. We are therefore compelled to prove our moment estimation lower bound for the white-box model directly. Our proof introduces a novel hybrid technique that, instead of taking hybrids over input distributions, constructs hybrids over white-box adversaries.

Rabin has sadly just passed away at 94. This is a short piece on honoring him immediately. More is planned for the future.

His work has touched key areas of mathematics as well as central areas of computer theory. Without his work theory would be completely different today. Michael’s work is an incredible mine with three rich veins. There are deep, hard theorems—for instance his work on the second-order theory of two successors. There is foundation creation—for instance his work on finite automata with Dana Scott, which was awarded the 1976 Turing award. And there is practical work—for example his beautiful string matching algorithm with Richard Karp, and much more. His concept of oblivious transfer is a bedrock primitive in secure computation. Not surprisingly he has been honored with many prizes, including the Turing Award, the Israel Prize, the Emet Prize, the Harvey Prize, the Dan David Prize, and others.

Michael Rabin Was Brilliant

Rabin showed over and over how brilliant he was. He found new ways to compute things, things that were important. Without his work whole fields would never have been possible. Almost all his work was on finding faster algorithms for such key problems. Perhaps all his work was on algorithms.

Generally he pioneered randomization as a key tool to solve critical, important problems, and he set the trend. His leadership in this respect that randomization is a fundamental algorithmic tool, practice, and then as a resource, is perhaps even more important than his individual technical contributions. He seemed to really have had the insight that randomization was going to be important, and made it so. Here are just a few examples of this terrific work.

Number Theory

Rabin used randomization to determine whether a number is prime. His insight was based on Gary Miller’s earlier work that uses deep unproven versions of the Riemann hypothesis. It is unimaginable what our world would be like today if such algorithms in number theory did not exist. Modern cryptography would be impossible without Rabin’s brilliant insight. He made this whole area possible.

String Theory

His work with Dick Karp used randomization to change forever how people think about string matching and related questions. This changed this important area forever. Their work made string algorithms possible—which changed this whole area of important work.

Geometric Theory

Rabin also used his random methods to solve basic geometry problems. Donald Knuth in volume 3 of The Art of Computer Programming (1973) called it the post-office problem. Later it became the nearest neighbor problem. Rabin showed that there was an algorithm for finding the nearest neighbor problem in linear time.

Even decades later there are still exciting questions about his algorithm and related methods. Perhaps it shows that Rabin was brilliant also when his methods were not perfect. He created new ways to look at such basic geometric problems. That these methods still need to be studied is a tribute to his leadership.

How We Should Honor Michael Rabin Forever

The theory community is planning a longer more technical piece on Rabin’s wonderful work. But we should begin now to think about how to honor Rabin. There are several ways that we might do this.

Prizes: We could create prizes in his honor. I cannot imagine that it would not be a great honor to get a prize that existed for work that advances methods he started. Perhaps the Rabin-Randomization Prize?

Conferences: We certainly could create special conferences or talks at existing conferences in his honor. Rabin was famous for his terrific talks that explained his work with such clarity. Having special talks in his honor would be cool.

Other: Perhaps other ideas can be advanced. What do you think?

Finally I wish to thank Jin-Yi Cai for invaluable comments on this piece.

By rjlipton

This is a live blog of Lecture 10 of my graduate seminar “Feedback, Learning, and Adaptation.” A table of contents is here.

Though the “theory” of computer science is most associated with algorithms and complexity, by far the most impactful theories all stem from architecture. Computer architecture, software architecture, network architecture. Architectural theory in computer science is seldom packaged in clean theorems, but there are implicit and explicit design principles that recur across dozens of abstraction layers.

Computing hardware, software, and network design all share key architectural concepts, but our courses don’t often cleanly connect the architectural dots across the application domains. In computer science, all of these different theories of architecture focus on designing hierarchical systems to support diversity and robustness. They all use similar building blocks, namely abstraction boundaries, layered hierarchies, and protocols for cross-layer communication. These protocols are all constraints that deconstrain.

In class, I walked through a few examples, though I had to entirely gloss over all the details. The result was my most Santa Fe Institute slide deck ever, an endless scroll of ugly graphs of networks. I started with the internet, which has the clearest declarative design of all the architectures. Here’s a glimpse from Berkeley’s CS 168:

The internet enables diverse applications to run on diverse networks. It does so by enforcing seven layers of protocols. All of these protocols flow through the “narrow waist” of the Internet Protocol (IP), the jewel “constraint that deconstrains.” Since every application has to flow through a single protocol, you can have incredibly diverse physical networking below and incredibly diverse applications on top. The protocols fan out above and below IP to support the diverse goals. Notably, the transport layer supports TCP, which lets applications know if their packets arrived, and UDP, which doesn’t. The internet is designed for robustness by having a strict protocol list, but pushing all of the processing and thinking about those protocols to the edge.

I also briefly discussed software, operating systems, and hardware architectures in computer science. These systems are physically more localized and have different design constraints. Their main goal is to enable local physical scale so that computers can support fast, general-purpose software. As computers became faster, more complex, and more reliable, their design became more layered and hierarchical. Here’s an image of the timeline Alberto Sangiovanni-Vincentelli shared with me

Rather than trying to design a computer chip from transistors, design cycles accelerate by letting engineers work at higher and higher levels of abstraction. Layered design now comes in to simplify choices. Alberto and Edward Lee like to echo DEVO: “Freedom from choice is what you want!” By establishing clean abstraction layers, engineers can innovate at each layer without worrying about what happens above and below.

Now, this is the point in the lecture where I split with John Doyle. John likes to use layered architectures to understand biology. Yes, you can look at biology and see architecture. Indeed, the constraints that deconstrain terminology were coined by systems biologists. Marc Kirschner and John Gerhart use the notions of constraints and deconstraints to describe how common platforms in biology facilitate agile evolution into diverse phenotypes and species. Because the platform is conserved, this enables rapid evolutionary changes that wouldn’t be predicted by simple, uniformly random variation.

However, I always find that people project technology onto biology to organize and understand biological function. In the 1600s, the body was a bunch of clocks. In the 1800s, it was an engine. Now we think of it as a computer. I’m not saying these projections of technology onto biology aren’t useful, but I don’t think that we necessarily learn more about technology from seeking common patterns in biology. Indeed, I’d rather look at recurring patterns in artificial structures to identify commonalities and general principles.

So instead of looking to biology, let’s look to management. Because man, every computer architecture diagram looks like an industrial org chart. This is not accidental. They serve similar functions. Computing and the mega-organization grew symbiotically in the post-war period, and building complex computing infrastructure required complex organizations of people. Some individuals certainly made brilliant, important advances at isolated nodes of these networks. However, the genius of layered architecture is that they admit a diversity of narrow innovations at every layer that locally grows the architectural ruleset without disrupting what everyone else is doing. In organizations, we have specific reporting and evaluation protocols, rules for bonuses and promotions, and schemes for supporting diverse business goals. The organizational architecture serves functions similar to those of computer architecture.

In “Toward a Theory of Control Architecture,” which I’ll discuss more in the next post, Nik Matni, Aaron Ames, and John Doyle set the stage with the Apollo project’s architecture, which bears a striking resemblance to today’s standard robotic architectures.

You have low-level controllers at one layer, a synthesis of sensors and trajectory optimization in the middle, and a high-level planner at the bottom. Part of this is because the abstraction makes it easier to reason locally about mitigating the complexity of launching people to a cold, barren, airless moon. However, such complexity also required massive teams of people. Here’s a small part of the organization of the Apollo Spacecraft Project Office.

A theory of architecture can’t neglect a theory of human organization. Both artificial structures work together to create the complex infrastructure underneath our contemporary condition.

Subscribe now

By Ben Recht

Michael Rabin passed away on April 14, 2026 at the age of 94.  (Scott Aaronson has also blogged about his passing, see  here.) 

I had many points to make about him; however, the first one got so long that I will just do that one for today's blog post.

Rabin is an extremely well-rounded \(\ldots\) computer scientist? Computer scientist seems too narrow, and the point of this point is that he was well rounded. So I will start this thought again.

The following is an extremely important question that permeates computer science, mathematics, and I am sure other fields:

Given a problem, how hard is it?

Note that this is a rather broad problem since the terms problem and hard are very broad.  And by hard I mean upper bounds and lower bounds.

Rabin had worked on this problem in many different domains. I list them in roughly the order of hardness, starting from the hardest.

1) Recursive Algebra: Mathematicians had proven that every field has an algebraic closure (an extension that is algebraically closed).  In 1960 Rabin asked and answered affirmatively: Does every computable field (the elements of the field are computable, \(\times\), \(+\), are computable) have a computable algebraic closure. This was an early result in what was later to be Nerode's Recursive Math Program which later became a subcase of the  Friedman/Simpson Reverse Math Program.

2) The Decidability of S2S: In 1969  Rabin proved that the the second order theory of 2 successors (S2S) is decidable. In a course I had with him he taught the proof that the weak second order theory of 1 successor (WS1S) is decidable. I teach that when I teach Automata Theory since it brings together Finite Automata and Decidability.  Here are my slides:here

S2S is one of the only decidable theories where one can actually state theorems in math of interest in them.  (I may blog about that some other time.)

S2S is the decidable theory with the hardest proof of its decidability. Rabin's proof used transfinite induction, though later proofs did not.

Personal Note: I was the subreferee on a paper by Gurevich and Harrington that simplified the proof tremendously, back in the early 1980's. Their proof is the one to read now.  Rabin was happy that the proof was simplified. The proof is still hard, just not as hard. 

3) In 1974  Fisher & Rabin showed that any algorithm to decide Presburger arithmetic required time \(\ge 2^{2^{cn}}\) for some constant \(c\). I asked chatty if better is known and it gave me answers that didn't make sense. An earlier version of this paragraph said so and had some incorrect statements in it. One of the commenters told me what is TRUE which made it easier to look it up. Anyway, there is a triple-exp algorithm, and there is a complexity class that Presburger is complete for---see the comment. Spellcheck thinks Presburger is spelled incorrectly. I can understand why it thinks so, but its wrong. 

When Rabin taught this result he pointed out that Hilbert and others not only thought that math was decidable but also that perhaps that algorithm could be used to really do math. The complexity results show that even if a theory is decidable it may still be really hard. (With AI maybe we can use computers to do math, but that is way too big a topic, and too big a tangent, to get into within a blog-obit).

4) In 1972 Rabin proved the following. Given linear forms \(L_1(x),\ldots,L_m(x)\) over the reals (so the intent is \(x\in R^n \)) we want to know if there exists \(x\in R^n \) such that, for all \(1\le i\le m \), \(L_i(x)>0 \).  The model of computation is a decision tree where each internal node can ask a question of the form \(L(x) {\rm\  RELATION\  } 0 \) where RELATION can be any of \(<,=,>\). Each leaf is labelled YES or NO.  Then the depth of the tree is \(\ge 2^{\Omega(n)} \).  This is an early paper in decision tree complexity.

5) In 1977 the Handbook of Math Logic came out. Rabin did the article on Decidable theories. He mentioned P vs NP as being really important and being the next logical (no pun intended) direction for logic. He was the only author to mention P vs NP.

6) While Rabin did not invent randomized algorithms he worked on them a lot early on.  In 1977 Solovay and Strassen obtained a polytime randomized algorithm for primality.  In 1976 Rabin noticed that Miller's Primality algorithm (which showed that if the Extended Riemann Hypothesis is true then primality is in P) could be modified to be a randomized polynomial time algorithm for primality. While preparing this blog post I noticed that I often hear about the Miller-Rabin algorithm (many cryptography protocols need a primality algorithm) but I hardly ever hear about the Solovay-Strassen algorithm. I asked Google AI why this was. In brief: Miller-Rabin is faster, has a lower probability of error, and is simpler. Is Google AI correct? I think yes since Miller-Rabin is used and Solovay-Strassen is not. I might be employing circular reasoning here. 

The Miller-Rabin primality test might be his second best known work, the best known being the last item on this list, the result of Rabin and Scott that NFA's are equivalent to DFA's.  (It's last since it is the lowest complexity class he worked on.)

 
7) Rabin obtained other randomized algorithms. I mention two:

a) Rabin-Shallit: When teaching automata theory I often give my students the following sets in NP and ask them to determine which ones are known to be in P:

\( \{ x \in N \colon (\exists y)[x=y^2] \} \)

\( \{ x \in N \colon (\exists y_1,y_2)[x=y_1^2+ y_2^2] \} \)

\( \{ x \in N \colon (\exists y_1,y_2,y_3)[x=y_1^2+ y_2^2+ y_3^2] \} \)

\( \{ x \in N \colon (\exists y_1,y_2,y_3,y_4)[x=y_1^2+ y_2^2+ y_3^2+y_4^2] \} \)

\( \{ x \in N \colon (\exists y_1,y_2,y_3,y_4,y_5)[x=y_1^2+ y_2^2+ y_3^2+y_4^2+y_5^2] \} \)

etc.

The input is in binary so searching for all possible \(y_1,y_2,y_3,y_4,\ldots,y_n\) is exponential in the length of the input.

I leave the first three to the reader.

This one:

\( \{ x \in N \colon (\exists y_1,y_2,y_3,y_4)[x=y_1^2+ y_2^2+ y_3^2+y_4^2] \} \)

is sort-of a trick question. Every number is the sum of 4 squares, so this set, and all later ones, are trivially in P. But that raises the question: how to find \( y_1,y_2,y_3,y_4 \)? This is a curious case of a problem that is in NP, the decision part is in P (in fact, trivial),  but finding the witness seems hard.

When I first assigned this problem I then looked up what was known about finding the \(y_1,y_2,y_3,y_4\). 

In 1986 Rabin and Shallit showed that, assuming ERH, there is a randomized \( O(\log^2 n) \) algorithm. I am surprised that you need both ERH and Randomness. This seems to be a less-well known result though I don't know why since it's a natural question.

b) Karp-Rabin: In 1987 Karp and Rabin obtained a really fast, really simple (that's a plus in the computer science world)  randomized pattern matching algorithm.  Since it is fast and simple I wondered if it is really used. It is! To quote Google AI:

Yes, the Karp-Rabin algorithm is used in the real world, particularly in scenarios requiring the detection of multiple patterns simultaneously, such as plagiarism detection,data deduplication, and bioinformatics.

Is Google AI correct? I leave that as an exercise for the reader. 

8) In 1979 Rabin devised a cryptosystem whose security is equivalent to factoring. How come RSA became the standard and not Rabin's system? Broadly two possibilities

a) RSA was better.

b) RSA was faster to the marketplace and other random factors.

Which is it? I leave that to the reader.

9) In 1958 Rabin and Scott showed that NFAs are equivalent to DFAs. This may be his best known work.

By gasarch

Authors: Arianne Meijer-van de Griend

In this paper, we give a mathematical proof that bounds the number of CNOT gates required to synthesize an $n$ qubit phase polynomial with $g$ terms to be at least $O(\frac{gn}{\max (\log g, 1)})$ and at most $O(gn)$. However, when targeting restricted hardware, not all CNOTs are allowed. If we were to use SWAP-based methods to route the qubits on the architecture such that the earlier synthesized gates are natively allowed, we increase the number of CNOTs by a routing overhead factor of $O(\log n) \leq α\leq O(n \log^2 n)$. However, if we only synthesize allowed gates, we do not need to route any qubits. Moreover, in that case the routing overhead factor is $1 \leq α\leq 4 \simeq O(1)$. Additionally, since phase polynomials and Hadamard gates together form a universal gate set, we get qubit routing for almost free.

Authors: Nikita Guseynov, Zoë Holmes, Armando Angrisani

We introduce coherent-state propagation, a computational framework for simulating bosonic systems. We focus on bosonic circuits composed of displaced linear optics augmented by Kerr nonlinearities, a universal model of bosonic quantum computation that is also physically motivated by driven Bose-Hubbard dynamics. The method works in the Schrödinger picture representing the evolving state as a sparse superposition of coherent states. We develop approximation strategies that keep the simulation cost tractable in physically relevant regimes, notably when the number of Kerr gates is small or the Kerr nonlinearities are weak, and prove rigorous guarantees for both observable estimation and sampling. In particular, bosonic circuits with logarithmically many Kerr gates admit quasi-polynomial-time classical simulation at exponentially small error in trace distance. We further identify a weak-nonlinearity regime in which the runtime is polynomial for arbitrarily small constant precision. We complement these results with numerical benchmarks on the Bose-Hubbard model with all-to-all connectivity. The method reproduces Fock-basis and matrix-product-state reference data, suggesting that it offers a useful route to the classical simulation of bosonic systems.

Authors: Ron Kupfer

We extend the Ting--Yao randomized maximum-finding algorithm [TY94] to inputs that need not be pairwise distinct: each parity test $P(i,B)=\prod_{a\in B}(x_i-x_a):0$ on $B\subseteq[n]\setminus\{i\}$ is simulated by $O(\log |B|)$ ordinary polynomial tests, raising depth from $O((\log n)^2)$ to $O((\log n)^3)$ while preserving the $O(n^{-c})$ failure probability for every fixed $c>0$.

Authors: Dohoon Kim, Eungyu Woo, Donghoon Shin

This paper investigates a special variant of a pursuit-evasion game called lions and contamination. In a graph where all vertices are initially contaminated, a set of lions traverses the graph, clearing the contamination from every vertex they visit. However, the contamination simultaneously spreads to any adjacent vertex not occupied by a lion. We analyze the relationships among the lion number $\mathcal{L}(G)$, monotone lion number $\mathcal{L}^m(G)$, and the graph's pathwidth $\operatorname{pw}(G)$. Our main results are as follows: (a) We prove a monotonicity property: for any graph $G$ and its isometric subgraph $H$, $\mathcal{L}(H)\le \mathcal{L}(G)$. (b) For trees $T$, we show that the lion number is tightly characterized by pathwidth, satisfying $\operatorname{pw}(T)\le \mathcal{L}(T)\le \operatorname{pw}(T)+1$. (c) We provide a counterexample showing that the monotonicity property fails for arbitrary subgraphs. (d) We show that, in contrast to the tree case, pathwidth does not yield a general lower bound on $\mathcal{L}(G)$ for arbitrary graphs. (e) For any connected graph $G$, we prove the general upper bound $\mathcal{L}(G)\le \operatorname{pw}(G)+1$. (f) For the monotone variant, we establish the general lower bound $\operatorname{pw}(G)\le \mathcal{L}^m(G)$. (g) Conversely, we show that $\mathcal{L}^m(G)\le 2\operatorname{pw}(G)+2$ holds for all connected graphs, which is best possible up to a small additive constant.

Authors: Bibhas Adhikari

We develop a unified quantum framework for subgraph counting in graphs. We encode a graph on $N$ vertices into a quantum state on $2\lceil \log_2 N \rceil$ working qubits and $2$ ancilla qubits using its adjacency list, with worst-case gate complexity $O(N^2)$, which we refer to as the graph adjacency state. We design quantum measurement operators that capture the edge structure of a target subgraph, enabling estimation of its count via measurements on the $m$-fold tensor product of the adjacency state, where $m$ is the number of edges in the subgraph. We illustrate the framework for triangles, cycles, and cliques. This approach yields quantum logspace algorithms for motif counting, with no known classical counterpart.

Authors: Michael T. M. Emmerich, Ksenia Pereverdieva, André H. Deutz

We prove that, for every fixed $θ_0>0$, selecting a subset of prescribed cardinality that maximizes the Solow--Polasky diversity indicator is NP-hard for finite point sets in $\mathbb{R}^2$ with the Euclidean metric, and therefore also for finite point sets in $\mathbb{R}^d$ for every fixed dimension $d \ge 2$. This strictly strengthens our earlier NP-hardness result for general metric spaces by showing that hardness persists under the severe geometric restriction to the Euclidean plane. At the same time, the Euclidean proof technique is different from the conceptually easier earlier argument for arbitrary metric spaces, and that general metric-space construction does not directly translate to the Euclidean setting. In the earlier proof one can use an exact construction tailored to arbitrary metrics, essentially exploiting a two-distance structure. In contrast, such an exact realization is unavailable in fixed-dimensional Euclidean space, so the present reduction requires a genuinely geometric argument. Our Euclidean proof is based on two distance thresholds, which allow us to separate yes-instances from no-instances by robust inequalities rather than by the exact construction used in the general metric setting. The main technical ingredient is a bounded-box comparison lemma for the nonlinear objective $\mathbf{1}^{\top}Z^{-1}\mathbf{1}$, where $Z_{ij}=e^{-θ_0 d(x_i,x_j)}$. This lemma controls the effect of perturbations in the pairwise distances well enough to transfer the gap created by the reduction. The reduction is from \emph{Geometric Unit-Disk Independent Set}. We present the main argument in geometric form for finite subsets of $\mathbb{R}^2$, with an appendix supplying the bit-complexity details needed for polynomial-time reducibility.

Authors: Hugo Hiu Chak Cheng, Gary P. T. Choi

Kirigami, the art of paper cutting, has been widely used in the modern design of mechanical metamaterials. In recent years, many kirigami-based metamaterials have been designed based on different planar tiling patterns and applied to different science and engineering problems. However, it is natural to ask whether one can create deployable kirigami structures based on the simplest forms of tilings, namely the monotile patterns. In this work, we answer this question by proving the existence of periodic and aperiodic monotile kirigami structures via explicit constructions. In particular, we present a comprehensive collection of periodic monotile kirigami structures covering all 17 wallpaper groups and aperiodic monotile kirigami structures covering various quasicrystal patterns as well as polykite tilings. We further perform theoretical and computational analyses of monotile kirigami patterns in terms of their shape and size changes under deployment. Altogether, our work paves a new way for the design and analysis of a wider range of shape-morphing metamaterials.

Authors: Yifan Zhang

We study a family of local depth-based corrections to maxmin landmark selection for lazy witness persistence. Starting from maxmin seeds, we partition the cloud into nearest-seed cells and replace or move each seed toward a deep representative of its cell. The principal implemented variant, \emph{support-weighted partial recentering}, scales the amount of movement by cell support. The contributions are both mathematical and algorithmic. On the mathematical side, we prove local geometric guarantees for these corrections: a convex-core robustness lemma derived from halfspace depth, a $2r$ cover bound for subset recentering, and projected cover bounds for the implemented partial-recentering rules. On the algorithmic side, we identify a practically effective variant through a layered empirical study consisting of planar synthetic benchmarks, a parameter-sensitivity study, and an MPEG-7 silhouette benchmark, together with a modest three-dimensional torus extension. The main planar experiments show that support-weighted partial recentering gives a consistent geometric improvement over maxmin while preserving the thresholded $H_1$ summary used in the study. The three-dimensional experiment shows the same geometric tendency but only mixed topological behavior. The paper should therefore be read as a controlled study of a local depth-based alternative to maxmin, rather than as a global witness-approximation theorem or a claim of uniform empirical superiority.

Authors: Michael Lampis, Manolis Vasilakis

Capacitated Vertex Cover is the hard-capacitated variant of Vertex Cover: given a graph, a capacity for every vertex, and an integer $k$, the task is to select at most $k$ vertices that cover all edges and assign each edge to one of its chosen endpoints so that no chosen vertex receives more incident edges than its capacity. This problem is a classical benchmark in parameterized complexity, as it was among the first natural problems shown to be W[1]-hard when parameterized by treewidth. We revisit its exact complexity from a fine-grained parameterized perspective and obtain a much sharper picture for several standard parameters. For the natural parameter $k$, we prove under the Exponential Time Hypothesis (ETH) that no algorithm with running time $k^{o(k)} n^{\mathcal{O}(1)}$ exists. In particular, this shows that the known algorithms with running time $k^{\mathcal{O}(\mathrm{tw})} n^{\mathcal{O}(1)}$ are essentially optimal. We then turn to more general structural parameters. For vertex cover number $\mathrm{vc}$, we give evidence against a $2^{\mathcal{O}(\mathrm{vc}^{2-\varepsilon})} n^{\mathcal{O}(1)}$ algorithm, as such an improvement would imply corresponding progress for a broader class of integer-programming-type problems. We complement this barrier with a nearly matching upper bound for vertex integrity $\mathrm{vi}$, improving the previously known double-exponential dependence to an algorithm with running time $\mathrm{vi}^{\mathcal{O}(\mathrm{vi}^{2})} n^{\mathcal{O}(1)}$ using $N$-fold integer programming. For treewidth, we show that the standard dynamic programming algorithm with running time $n^{\mathcal{O}(\mathrm{tw})}$ is essentially optimal under the ETH, even if one parameterizes by tree-depth. Turning to clique-width, we prove that Capacitated Vertex Cover remains NP-hard already on graphs of linear clique-width $6$...

Authors: Alexander Ponomarenko

We analyze greedy routing in a random graph G_n constructed on the vertex set V = {1, 2, ..., n} embedded in Z. Vertices are inserted according to a uniform random permutation pi, and each newly inserted vertex connects to its nearest already-inserted neighbors on the left and right (if they exist). This work addresses a conjecture originating from empirical studies (Ponomarenko et al., 2011; Malkov et al., 2012), which observed through simulations that greedy search in sequentially grown graphs exhibits logarithmic routing complexity across various dimensions. While the original claim was based on experiments and geometric intuition, a rigorous mathematical foundation remained open. Here, we formalize and resolve this conjecture for the one-dimensional case. For a greedy walk GW starting at vertex 1 targeting vertex n -- which at each step moves to the neighbor closest to n -- we prove that the number of steps S_n required to reach n satisfies S_n = Theta(log n) with high probability. Precisely, S_n = L_n + R_n - 2, where L_n and R_n are the numbers of left-to-right and right-to-left minima in the insertion-time permutation. Consequently, E[S_n] = 2H_n - 2 ~ 2 log n and P(S_n >= (2+c) log n) <= n^(-h(c/2) + o(1)) for any constant c > 0, with an analogous lower tail bound for 0 < c < 2, where h(u) = (1+u) ln(1+u) - u is the Bennett rate function. Furthermore, we establish that this logarithmic scaling is robust: for arbitrary or uniformly random start-target pairs, the expected routing complexity remains E[S_{s,t}] = 2 log n + O(1), closely mirroring decentralized routing scenarios in real-world networks where endpoints are chosen dynamically rather than fixed a priori.

Authors: Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert, Paweł Gawrychowski, Tatiana Starikovskaya

Many string processing problems can be phrased in the streaming setting, where the input arrives symbol by symbol and we have sublinear working space. The area of streaming algorithms for string processing has flourished since the seminal work of Porat and Porat [FOCS 2009]. Unfortunately, problems with efficient solutions in the classical setting often do not admit efficient solutions in the streaming setting. As a bridge between these two settings, Saks and Seshadhri [SODA 2013] introduced the asymmetric streaming model. Here, one is given read-only access to a (typically short) reference string $R$ of length $m$, while a text $T$ arrives as a stream. We provide a generic technique to reduce fundamental string problems in the asymmetric streaming model to the online read-only model, lifting several existing algorithms and generally improving upon the state of the art. Most notably, we obtain asymmetric streaming algorithms for exact and approximate pattern matching (under both the Hamming and edit distances), and for relative Lempel-Ziv compression. At the heart of our approach lies a novel tool that facilitates efficient computation in the asymmetric streaming model: the suffix random access data structure. In its simplest variant, it maintains constant-time random access to the longest suffix of (the seen prefix of) $T$ that occurs in $R$. We show a bidirectional reduction between suffix random access and function inversion, a central problem in cryptography. On the way to our upper bound, we propose a variant of the string synchronizing sets ([Kempa and Kociumaka; STOC 2019]) with a local sparsity condition that, as we show, admits an efficient streaming construction algorithm. We believe that our framework and techniques will find broad applications in the development of small-space string algorithms.

Authors: Jan Eube, Kelin Luo, Aneta Neumann, Frank Neumann, Heiko Röglin

The Traveling Thief Problem (TTP) is a multi-component optimization problem that captures the interplay between routing and packing decisions by combining the classical Traveling Salesperson Problem (TSP) and the Knapsack Problem (KP). The TTP has gained significant attention in the evolutionary computation literature and a wide range of approaches have been developed over the last 10 years. Judging the performance of these algorithms in particular in terms of how close the get to optimal solutions is a very challenging task as effective exact methods are not available due to the highly challenging traveling component. In this paper, we study the tour-optimization component of TTP under a fixed packing plan. We formulate this task as a weighted variant of the TSP, where travel costs depend on the cumulative weight of collected items, and investigate how different distance metrics and cost functions affect computational complexity. We present an $(O(n^2))$-time dynamic programming algorithm for the path metric with general cost functions, prove that the problem is NP-hard even on a star metric, and develop constant-factor approximation algorithms for star metrics. Finally, we also develop an approximation algorithm for the problem under a general metric with a linear cost function. We complement our theoretical results with experimental evaluations on standard TTP instances adjusted to a path metric. Our experimental results demonstrate the practical effectiveness of our approaches by comparing it to solutions produced by popular iterative search algorithms. The results show that our methods are able to significantly improve the quality of solutions for some benchmark instances by optimizing the traveling part while pointing out the optimality of the travel component for other solutions obtained by iterative search methods.

Authors: Édouard Bonnet, Yeonsu Chang, Julien Duron, Colin Geniet, O-joung Kwon

Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operatorname{cml}^\downarrow$, where component max-leaf is the maximum number of leaves in any spanning tree of any connected component. Reduced component max-leaf is strictly sandwiched between clique-width and reduced bandwidth, it is bounded in unit interval graphs, and unbounded in planar graphs. We design polynomial-time algorithms for problems such as \textsc{Maximum Induced $d$-Regular Subgraph} and \textsc{Induced Disjoint Paths} in graphs given with a contraction sequence witnessing low $\operatorname{cml}^\downarrow$, unifying and extending tractability results for classes of bounded clique-width and unit interval graphs. We get the following collapses in sparse classes of bounded $\operatorname{cml}^\downarrow$: bounded maximum degree implies bounded treewidth, whereas $K_{t,t}$-subgraph-freeness implies strongly sublinear treewidth; we show the latter, more generally, for classes of bounded reduced cutwidth. We establish the former result by showing that graphs with bounded $\operatorname{cml}^\downarrow$ admit balanced separators dominated by a bounded number of vertices. We then showcase an application of the reduced parameters to establishing non-transducibility results. We prove that for most reduced parameters $p^\downarrow$ (including reduced bandwidth), the family of classes of bounded $p^\downarrow$ is closed under first-order transductions. We then answer a question of [BKW '26] by showing that the 3-dimensional grids have unbounded reduced bandwidth. As the class of planar graphs (or any class of bounded genus) has bounded reduced bandwidth [BKW '26], this reproves a recent result [GPP, LICS '25] that planar graphs do not first-order transduce the 3-dimensional grids.

Authors: Aaron R. Flouro, Shawn P. Chadwick

Computing Fourier transforms of k-sparse signals, where only k of N frequencies are non-zero, is fundamental in compressed sensing, radar, and medical imaging. While the Fast Fourier Transform (FFT) evaluates all N frequencies in $O(N \log N)$ time, sufficiently sparse signals should admit sub-linear complexity in N. Existing sparse FFT algorithms using Chinese Remainder Theorem (CRT) reconstruction rely on moduli selection choices whose worst-case implications have not been fully characterized. This paper makes two contributions. First, we establish an $Ω(k^2)$ adversarial lower bound on candidate growth for CRT-based sparse FFT when moduli are not pairwise coprime (specifically when $m_3 \mid m_1 m_2$), implying an $O(k^2 N)$ worst-case validation cost that can exceed dense FFT time. This vulnerability is practically relevant, since moduli must often divide N to avoid spectral leakage, in which case non-pairwise-coprime configurations can be unavoidable. Pairwise coprime moduli avoid the proven attack; whether analogous constructions exist for such moduli remains an open question. Second, we present a robustness framework that wraps a 3-view CRT sparse front end with lightweight certificates (bucket occupancy, candidate count) and an adaptive dense FFT fallback. For signals passing the certificates, the sparse path achieves $O(\sqrt{N} \log N + k N)$ complexity; when certificates detect collision risk, the algorithm reverts to $O(N \log N)$ dense FFT, guaranteeing worst-case performance matching the classical bound.

Authors: Alex McAvoy

The expected meeting time of two random walkers on an undirected graph of size $N$, where at each time step one walker moves and the process stops when they collide, satisfies a system of $\binom{N}{2}$ linear equations. Naïvely, solving this system takes $O\left(N^{6}\right)$ operations. However, this system of linear equations has nice structure in that it is almost a Sylvester equation, with the obstruction being a diagonal absorption constraint. We give a simple algorithm for solving this system that exploits this structure, leading to $O\left(N^{4}\right)$ operations and $Θ\left(N^{2}\right)$ space for exact computation of all $\binom{N}{2}$ meeting times. While this practical method uses only standard dense linear algebra, it can be improved (in theory) to $O\left(N^{3}\log^{2}N\right)$ operations by exploiting the Cauchy structure of the diagonal correction. We generalize this result slightly to cover the Poisson equation for the absorbing "lazy" pair walk with an arbitrary source, which can be solved at the same cost, with $O\left(N^{3}\right)$ per additional source on the same graph. We conclude with applications to evolutionary dynamics, giving improved algorithms for calculating fixation probabilities and mean trait frequencies.

The Theory Group in Brown University’s Computer Science Department invites applications for a postdoctoral position in graph algorithms and/or theoretical machine learning. The postdoc will have the opportunity to work closely with Professors Ellis Hershkowitz, Yu Cheng, and Eli Upfal. The appointment begins Fall 2026 for one year, with possible renewal.

Website: https://dhershko.github.io/postdocAd
Email: delhersh@brown.edu

By shacharlovett

Authors: Alonso Botero, Matthias Christandl, Thomas C. Fraser, Itai Leigh, Harold Nieuwboer

Upper and lower quantum functionals, introduced by Christandl, Vrana and Zuiddam (STOC 2018, J. Amer. Math. Soc. 2023), are families of monotone functions of tensors indexed by a weighting on the set of subsets of the tensor legs. Inspired by quantum information theory, they were crafted as obstructions to asymptotic tensor transformations, relevant in algebraic complexity theory. For tensors of order three, and more generally for weightings on singletons for higher-order tensors, the upper and lower quantum functionals coincide and are spectral points in Strassen's asymptotic spectrum. Moreover, the singleton quantum functionals characterize the asymptotic slice rank, whereas general weightings provide upper bounds on asymptotic partition rank. It has been an open question whether the upper and lower quantum functionals also coincide for other cases, or more generally, how to construct further spectral points, especially for higher-order tensors. In this work, we show that upper and lower quantum functionals generally do not coincide, but that they anchor new spectral points. With this we mean that there exist new spectral points, which equal the quantum functionals on the set of tensors on which upper and lower coincide. The set is shown to include embedded three-tensors and W-like states and concerns all laminar weightings, significantly extending the singleton case.

Authors: Xiao Wang

The key-value (KV) cache is the dominant memory bottleneck during Transformer inference, yet little is known theoretically about how aggressively it can be compressed before multi-step reasoning degrades. We study this through $k$-hop pointer chasing on $n$ tokens under a shared KV cache of size $s$, attention dimension $m$, $H$ heads, $p$-bit precision, and a locality-respecting cache controller (satisfied by all standard KV-compression methods). We give three results. (1) Product depth lower bound (conjectured). We conjecture that any such Transformer ($n \geq 4k$, $s \leq \sqrt{n}/4$) requires depth $L = Ω(\lceil k/s \rceil \cdot \lceil \log_2 n/(Hmp) \rceil)$, and isolate the sole remaining gap as a probabilistic step on the joint distribution of cache trace and pointer chain. Unconditionally, we prove a matching upper bound $L = O(\min(k, \lceil k/s \rceil \log s) \cdot \log n/(mp))$ via windowed pointer doubling, and a max-bound $L = Ω(\max(\lceil k/s \rceil, \log n/(Hmp)))$. Closing the conjecture amounts to upgrading max to product. (2) Bandwidth barrier. The product bound binds only when $Hmp \lesssim \log n$. Any lower bound provable via per-window distinguishability counting -- including reachability, bandwidth, and combinations -- cannot exceed $\lceil k/s \rceil$ once $Hmp \geq \log_2 n$. Breaking this requires lifting unconditional communication-complexity bounds for pointer chasing to Cache-Transformer depth. (3) Adaptive vs oblivious error scaling. Under random cache over $T = \lceil \log_2 k \rceil$ doubling stages, oblivious caches give $\Pr[\mathcal{E}] \leq (s/(n-T))^T + 2T^3/n$ (exponential in $T$), while adaptive locality-respecting caches achieve $\Pr[\mathcal{E}] = s/n$ exactly, independent of $T$. The $Ω((n/s)^{T-1})$ separation explains why heavy-hitter eviction empirically dominates random eviction for multi-hop reasoning.

Authors: Divya Bajaj, Bin Fu, Ryan Knobel, Austin Luchsinger, Aiden Massie, Pablo Santos, Ramiro Santos, Robert Schweller, Evan Tomai, Tim Wylie

Chemical Reaction Networks (CRNs) are a well-established model of distributed computing characterized by quantities of molecular species that can transform or change through applications of reactions. A fundamental problem in CRNs is the reachability problem, which asks if an initial configuration of species can transition to a target configuration through an applicable sequence of reactions. It is well-known that the reachability problem in general CRNs was recently proven to be Ackermann-complete. However, if the CRN's reactions are restricted in both power, such as only deleting species (deletion-only rules) or consuming and producing an equal number of species (volume-preserving rules), and size (unimolecular or bimolecular rules), then reachability falls below Ackermann-completeness, and is even solvable in polynomial time for deletion-only systems. In this paper, we investigate reachability under this set of restricted unimolecular and bimolecular reactions, but in the Priority-Inhibitory CRN and Inhibitory CRN models. These models extend a traditional CRN by allowing some reactions to be inhibited from firing in a configuration if certain species are present; the exact inhibition behavior varies between the models. We first show that reachability with Priority iCRNs mostly remains in P for deletion-only systems, but becomes NP-complete for one case. We then show that reachability with deletion-only reactions for iCRNs is mostly NP-complete, and PSPACE-complete even for (1,1)-size (general) reactions. We also provide FPT algorithms for solving most of the reachability problems for the iCRN model. Finally, we show reachability for CRNs with states is already NP-hard for the simplest deletion-only systems, and is PSPACE-complete even for (general) (1,1)-size reactions.

Authors: Johannes Bund, Amir Leshem, Moti Medina

Metastability is a spurious mode of operation in digital signals, where an electrical signal fails to settle into a stable state within a specified time, leading to uncertainty and potentially failing downstream hardware. A system that computes the closure over all possibilities, given an uncertain input, is called a Metastability-containing system. While prior work has addressed metastability-containing systems in the context of combinational and clocked circuits, state machines, and logic formulas, its implications for general-purpose computation remain largely unexplored. In this work, we study the metastability-containing systems within an abstract computational model: The Turing Machine. This approach allows us to investigate the computational limits and capabilities of Turing Machines operating under uncertain inputs. Specifically, we prove that in general the metastable closure of a Turing Machine is non-computable. Then we discuss cases where the meta-stable closure is computable: For EXPTIME problems, we prove that resolving even a single uncertain bit is EXPTIME-complete. In contrast, we prove that for polynomial time problems, the meta-stable closure is polynomial time computable for a logarithmic number of uncertain bits, but coNP-complete, when the number of undefined inputs is arbitrary. Finally, we describe a hardware-realizable Universal Turning Machine that computes the metastable closure of any given bounded-time Turing Machine with at most an exponential blowup in time.