Theory of Computing Report

Authors: Demian Banakh, Katzper Michno

We develop an analytical framework for Boolean Promise Constraint Satisfaction Problems (PCSPs) that studies polymorphisms through the notion of influence from Fourier analysis of Boolean functions. Extending the work of Brakensiek, Guruswami, and Sandeep [ICALP'21] on Ordered PCSPs, we identify two general phenomena in Boolean minions indicative of hardness or tractability: (1) preservation of coordinate influence under random 2-to-1 minors and (2) the presence of sharp thresholds. We demonstrate that these phenomena occur in broader settings than previously established, yielding new hardness/tractability results for minions consisting of unate or polynomial threshold functions.

Authors: Shuai Zeng

Joint measurements on multiple copies of a quantum state provide access to nonlinear observables such as $\operatorname{tr}(ρ^t)$, but whether replica number marks a sharp information-theoretic resource boundary has remained unclear. For every fixed order $t\ge 3$, existing protocols show that $\lceil t/2\rceil$ replicas already suffice for polynomial-sample estimation of $\operatorname{tr}(ρ^t)$, yet it has remained open whether one fewer replica must necessarily incur a sample-complexity barrier growing with the dimension. We prove that this is indeed the case in the sample/copy-access model with replica-limited joint measurements: any protocol restricted to $\lceil t/2\rceil-1$ replicas requires dimension-growing sample complexity, while $\lceil t/2\rceil$ replicas suffice by prior work. Thus the exact replica threshold for fixed-order pure moments is $\lceil t/2\rceil$. Equivalently, for fixed-order pure moments, one additional coherent replica is not merely useful but marks the exact threshold between polynomial-sample estimation and a dimension-growing regime in the replica-limited model. We further show that the same threshold law extends to a broad family of observable-weighted moments $\operatorname{tr}(Oρ^t)$, including Pauli observables and other observables with bounded operator norm and macroscopic trace norm. Coherent replica number therefore acts as a genuinely discrete resource for nonlinear quantum-state estimation.

Authors: Samir Datta, Asif Khan, Felix Tschirbs, Nils Vortmeier, Thomas Zeume

Consider two planar graphs which are subject to edge insertions and deletions. We show that whether the two graphs are isomorphic can be maintained with first-order logic formulas and auxiliary data of polynomial size. This places the dynamic planar graph isomorphism problem into the dynamic descriptive complexity class DynFO. As a consequence, there is a dynamic constant-time parallel algorithm with polynomial-size auxiliary data which maintains whether two dynamic planar graphs are isomorphic.

Authors: Ran Raz

We prove a lower bound of $Ω\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 $Ω\left(n^{1.5}\right)$ multiplications. More generally, for any $d\geq 2$ and sufficiently large $n$, we obtain a lower bound of $Ω\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\}$: $Ω\left(n\log d\right)$ by Baur and Strassen, and $Ω\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).

Authors: Dmitry Babichev, Sergey Babichev

We study the exact counting problem for all lattice rectangles contained in the square $[0,n)\times[0,n)$, including non-axis-parallel ones. Starting from the standard parametrization by a primitive direction $(u,v)$ and two side lengths, we derive a sequence of exact algorithms of complexity $O(n^2)$, $O(n^{3/2}\log n)$, $O(n^{4/3}\log n)$, and finally $O(n\log^3 n)$. The main idea behind the near-linear algorithm is to reduce the geometric summation to a constant-size family of weighted floor sums closed under Euclidean-style affine and reciprocal transformations, and hence evaluable in $O(\log n)$ time per query. Besides the exact algorithmic result, we also derive a two-term asymptotic expansion, $F(n)=\frac{4\log 2-1}{π^2}n^4\log n+B\,n^4+o(n^4)$ with the explicit formula for $B$, which provides an independent consistency check for the large-$n$ numerical data produced by the algorithms.

Authors: Cheng Jiang, Yinchen Liu, Huacheng Yu

A fundamental question in streaming complexity is whether every space-efficient turnstile algorithm is implicitly a linear sketch. The landmark work of Li, Nguyen, and Woodruff [LNW14] established an equivalence between the two, but their reduction requires a stream length that is at least doubly exponential in the dimension $n$. In the opposite direction, results by Kallaugher and Price [KP20] demonstrate a separation for streams of linear length, showing that the equivalence does not hold in general. The most natural and practically relevant regime -- polynomial-length streams -- has therefore remained open. We show that polynomial-length turnstile algorithms admit linear-sketch simulations. More precisely, if a turnstile algorithm uses $S$ bits of space and succeeds on all streams of length $\mathrm{poly}(D, n)$, then on final vectors $x$ with $\|x\|_2 \le D$, its output can be recovered from $O(S)$ linear measurements of $x$, using $O(S \log S)$ bits overall. For smooth problems under appropriate input distributions, a mollified version of the reduction yields a bounded-entry sketch with $O(S / \log D)$ measurements and optimal $O(S)$ total space. Our results extend to strict turnstile streams and non-uniform Read-Once Branching Programs (ROBPs). Our proof departs from prior transition-graph based machinery, relying instead on a Fourier-analytic framework and tools from additive combinatorics to extract discrete linear measurements. Our analysis shows that any $S$-bit algorithm can only be sensitive to a low-dimensional lattice of heavy Fourier frequencies, which we then use to construct the rows of the sketching matrix. Consequently, we obtain new lower bounds for polynomial-length streams via existing real sketching and communication lower bounds.

Authors: Prashanti Anderson, Ainesh Bakshi, Samuel Hopkins

Given a matrix $A$, the goal of the entrywise low-rank approximation problem is to find $\operatorname{argmin} \|A-B\|_p$ over all rank-$k$ matrices $B$, where $\| \cdot \|_p$ is the entrywise $\ell_p$ norm. When $p = 2$ this well-studied problem is solved by the singular value decomposition, but for $p \neq 2$ the problem becomes computationally challenging. For every even $p > 2$ and every fixed $k$, we give the first polynomial-time approximation scheme for this problem, improving on the $(3 + \varepsilon)$ approximation of Ban, Bhattiprolu, Bringmann, Kolev, Lee, and Woodruff, the bi-criteria approximation of Woodruff and Yasuda, and the additive approximation scheme of Anderson, Bakshi, and Hopkins. Prior algorithmic approaches based on sketching and column selection, which yielded a polynomial-time approximation scheme in the $p < 2$ setting, face concrete barriers when $p > 2$. Instead, we use the Sherali-Adams hierarchy of convex programs, and in so doing establish a blueprint for how to use convex hierarchies to design polynomial-time approximation schemes for continuous optimization problems. We use the same algorithmic strategy to give a new family of additive approximation algorithms for matrix $p \rightarrow q$ norms, which are intimately related to small-set expansion and quantum information. In particular, we give the first nontrivial additive approximation algorithms in the regime $p < 2 < q$.

Authors: Matthias Lanzinger

Submodular width is a central structural measure governing the complexity of conjunctive query evaluation. In this paper we recast submodular width in geometric terms. We how that submodular width can be approximated, up to a factor $3/2$, by a new branchwidth parameter defined in terms of edge separations in the hypergraph and the costs induced on them by admissible submodular functions. This reformulation turns lower bounds on submodular width into the problem of constructing well-balanced edge separations whose induced cost remains small. We then express this connection through a variational characterisation in terms of a convex body. Using these tools, we relate submodular width to more familiar graph-theoretic notions, including line-graph treewidth and multicommodity flow, and obtain general conditions under which submodular width is tightly linked to generalised hypertree width. In particular, under various natural conditions we show that \[ subw(H) \in Ω\left(\frac{ghw(H)}{\log ghw(H)} \right). \]

A few months ago in Oxford, Bernard Sufrin, an emeritus fellow, said he's looking to hire a student to implement LEAP (Logic Engine for Argument by Pointing), a way to teach logic by proving basic logic theorems via pointing and clicking. Rahul Santhanam said why not give it to AI. Bernard said AI can't handle this task. I thought why not give it a try.

I gave Claude a single prompt that Bernard helped me formulate:

Architecture of a system to support proof by pointing in first order logic using LEAP

About an hour later, without giving additional details, we had a working prototype. Give it a try. I put the code and some more details on GitHub.

Watching Claude work was amazing. Claude created an architecture based on the paper Proof by Pointing by Yves Bertot, Gilles Kahn and Laurent Théry.

Claude then asked me:

Would you like me to proceed with implementing any of these layers?

Why not? So I told Claude to go ahead.

It started coding and it created 78 test cases and kept debugging itself until all those test cases worked out. It took me longer to get the program working on the web than Claude took to program it. I sent the link to Bernard who responded "Wow! I take it back if the program was all synthesized from the prompt." 

When I asked Bernard a month later if I could post about this program, he agreed, though he had some additional comments.

The consolation for me is that the outcome, though surprising and I suppose delightful (though it didn't manage rules for quantifiers), didn't refute my conjecture that Claude et al cannot do "architecture". The architecture (MVC) is stock; the "proof by pointing" hint led it to a paper of the same name which gave details of how to derive terms/formulae/goals in the (unfinished) proof from screen coordinates. Maybe you could give a substantively different prompt.

It may be of interest to know that the Bornat/Sufrin JAPE program, still on GitHub, was eventually a lot more ambitious when it came to selecting things: terms, subterms, goals. But it took more than 2 hours to build!

Bernard has a point. It wasn't just the fifteen-word prompt alone. Claude leaned on the Bertot et al. paper to guide its design and implementation. Still, that Claude did architect, build and debug the system from the prompt and the paper is truly impressive. We've truly crossed a threshold for coding, far beyond what would have been possible just a few months earlier.

By Lance Fortnow

Tendermint and Simplex are both leader-based BFT protocols for partial synchrony with optimal resilience and $3\delta$ good-case latency. There is a subtle tradeoff between them: In the optimistic responsive model, Simplex obtains a worst-case view latency of $3\Delta+\delta$ while Tendermint obtains a worst-case view latency of $4\Delta+\delta$. On the other hand, Tendermint requires only a bounded number of certificates to make progress in each view, while in Simplex the number...

By Ittai Abraham

June 29 – July 3, 2026 San Diego, USA https://learningtheory.org/colt2026/workshops.html#cfp Submission deadline: May 7, 2026 The Conference on Learning Theory (COLT 2026) will dedicate the first day of the main conference program (June 29 – July 3) to contributed and invited workshops, tutorials, and community events (e.g., affinity workshops, mentoring activities, socials). We invite proposals … Continue reading Workshops, Tutorials, and Community Events at COLT 2026

By shacharlovett

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 partial synchrony BFT protocol, the leader has two roles: (1) It constructs the input; and (2) It proposes the input. The natural validity property: Validity: if the leader is honest and the network is synchronous (GST=0), its input value is eventually decided by all honest parties. Moreover, it is natural to optimize for...

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