Theory of Computing Report

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.

Authors: Enoch Hyunwook Kang

Iterative alignment methods based on purely greedy updates are remarkably effective in practice, yet existing theoretical guarantees of \(O(\log T)\) KL-regularized regret can seem pessimistic relative to their empirical performance. In this paper, we argue that this mismatch arises from the regret criterion itself: KL-regularized regret conflates the statistical cost of learning with the exploratory randomization induced by the softened training policy. To separate these effects, we study the traditional temperature-zero regret criterion, which evaluates only the top-ranked response at inference time. Under this decision-centric notion of performance, we prove that standard greedy online alignment methods, including online RLHF and online DPO, achieve constant \((O(1))\) cumulative regret. By isolating the cost of identifying the best response from the stochasticity induced by regularization, our results provide a sharper theoretical explanation for the practical superb efficiency of greedy alignment.

Authors: Angshul Majumdar

We study the computational complexity of singularity for multilinear maps. While the determinant characterizes singularity for matrices, its multilinear analogue -- the hyperdeterminant -- is defined only in boundary format and quickly becomes algebraically unwieldy. We show that the intrinsic notion of tensor singularity, namely degeneracy, is complete for the existential theory of the reals. The reduction is exact and entirely algebraic: homogeneous quadratic feasibility is reduced to projective bilinear feasibility, then to singular matrix-pencil feasibility, and finally encoded directly as tensor degeneracy. No combinatorial gadgets are used. In boundary format, degeneracy coincides with hyperdeterminant vanishing. We therefore isolate the exact gap between intrinsic tensor singularity and its classical polynomial certificate. We show that deterministic hardness transfer to the hyperdeterminant reduces to selecting a point outside the zero set of a completion polynomial, yielding a structured instance of polynomial identity testing. We further formalize the failure of several natural deterministic embedding strategies. This identifies a sharp frontier: real 3-tensor degeneracy is fully characterized at the level of \(\ER\)-completeness, while the deterministic complexity of hyperdeterminant vanishing remains tied to a derandomization problem in algebraic complexity.

Authors: Michael T. M. Emmerich

We investigate \emph{magnitude} as a new unary and strictly Pareto-compliant quality indicator for finite approximation sets to the Pareto front in multiobjective optimization. Magnitude originates in enriched category theory and metric geometry, where it is a notion of size or point content for compact metric spaces and a generalization of cardinality. For dominated regions in the \(\ell_1\) box setting, magnitude is close to hypervolume but not identical: it contains the top-dimensional hypervolume term together with positive lower-dimensional projection and boundary contributions. This paper gives a first theoretical study of magnitude as an indicator. We consider multiobjective maximization with a common anchor point. For dominated sets generated by finite approximation sets, we derive an all-dimensional projection formula, prove weak and strict set monotonicity on finite unions of anchored boxes, and thereby obtain weak and strict Pareto compliance. Unlike hypervolume, magnitude assigns positive value to boundary points sharing one or more coordinates with the anchor point, even when their top-dimensional hypervolume contribution vanishes. We then formulate projected set-gradient methods and compare hypervolume and magnitude on biobjective and three-dimensional simplex examples. Numerically, magnitude favors boundary-including populations and, for suitable cardinalities, complete Das--Dennis grids, whereas hypervolume prefers more interior-filling configurations. Computationally, magnitude reduces to hypervolume on coordinate projections; for fixed dimension this yields the same asymptotic complexity up to a factor \(2^d-1\), and in dimensions two and three \(Θ(n\log n)\) time. These results identify magnitude as a mathematically natural and computationally viable alternative to hypervolume for finite Pareto front approximations.

Authors: Omrit Filtser, Tzalik Maimon, Ofir Yomtovyan

The minimum convex cover problem seeks to cover a polygon $P$ with the fewest convex polygons that lie within $P$. This problem is $\exists\mathbb R$-complete, and the best previously known algorithm, due to Eidenbenz and Widmayer (2001), achieves an $O(\log n)$-approximation in $O(n^{29} \log n)$ time, where $n$ is the complexity of $P$. In this work we present a novel approach that preserves the $O(\log n)$ approximation guarantee while significantly reducing the running time. By discretizing the problem and formulating it as a set cover problem, we focus on efficiently finding a convex polygon that covers the largest number of uncovered regions, in each iteration of the greedy algorithm. This core subproblem, which we call the rotten potato peeling problem, is a variant of the classic potato peeling problem. We solve it by finding maximum weighted paths in Directed Acyclic Graphs (DAGs) that correspond to visibility polygons, with the DAG construction carefully constrained to manage complexity. Our approach yields a substantial improvement in the overall running time and introduces techniques that may be of independent interest for other geometric covering problems.

Authors: David Avis, Luc Devroye

In this paper, we investigate the relationships between the volumes of four convex bodies: the cut polytope, metric polytope, rooted metric polytope, and elliptope, defined on graphs with $n$ vertices. The cut polytope is contained in each of the other three, which, for optimization purposes, provide polynomial-time relaxations. It is therefore of interest to see how tight these relaxations are. Worst-case ratio bounds are well known, but these are limited to objective functions with non-negative coefficients. Volume ratios, pioneered by Jon Lee with several co-authors, give global bounds and are the subject of this paper. For the rooted metric polytope over the complete graph, we show that its volume is much greater than that of the elliptope. For the metric polytope, for small values of $n$, we show that its volume is smaller than that of the elliptope; however, for large values, volume estimates suggest the converse is true. We also give exact formulae for the volume of the cut polytope for some families of sparse graphs.

Authors: József Pintér, Regina Stangl

Network caching asks how to place contents in distributed caches so that future requests are served close to their users. Ganian, Mc Inerney and Tsigkari recently initiated the parameterized-complexity study of the problem and, for the homogeneous unit-size variant (HomNC), isolated an unresolved family of six parameterizations: by the number of caches $C$, the number of users $U$, $U+K$, $C+U$, $C+λ$, and the vertex-cover number $\text{vc}(G)$, where $K$ is the maximum cache capacity and $λ$ is the maximum number of contents requested with nonzero probability by any user. Their interreducibility theorem showed that these six cases stand or fall together under parameterized reductions, and they conjectured the family to be W[1]-hard. We resolve this conjecture in the opposite direction. We prove that HomNC is fixed-parameter tractable parameterized by $C$ alone, and therefore fixed-parameter tractable for all six parameterizations. Our algorithm is based on an exact $n$-fold integer programming formulation that reveals a nontrivial block structure in homogeneous network caching, with the repeated part depending only on $C$. Standard algorithms for $n$-fold integer programming then yield a running time of the form $f(C)\lvert I\rvert^{O(1)}$.

Authors: Seongbin Park, Eunjin Oh

In this paper, we study the many-to-many matching problem on planar point sets with integer coordinates: Given two disjoint sets $R,B \subset [Δ]^2$ with $|R|+|B|=n$, the goal is to select a set of edges between $R$ and $B$ so that every point is incident to at least one edge and the total Euclidean length is minimized. In the general case that $R$ and $B$ are point sets in the plane, the best-known algorithm for the many-to-many matching problem takes $\tilde{O}(n^2)$ time. We present an exact $\tilde{O}(n^{1.5} \log Δ)$ time algorithm for point sets in $[Δ]^2$. To the best of our knowledge, this is the first subquadratic exact algorithm for planar many-to-many matching under bounded integer coordinates.

Authors: Maximilian von Aspern, Felix Buld, Michael Pinedo

We study flow shop scheduling with stochastic reentry, where jobs must complete multiple passes through the entire shop, and the number of passes that a job requires for completion is drawn from a discrete probability distribution. The goal is to find policies that minimize performance measures in expectation. Our main contribution is a reduction to a classical parallel machine scheduling problem augmented with machine arrivals. This reduction preserves expected objective values and enables transferring structural results and performance guarantees from the auxiliary problems to the reentrant flow shop setting. We demonstrate the usefulness of this reduction by proving the optimality of simple priority policies for minimizing the makespan and the total completion time in expectation under geometric and, more generally, monotone hazard rate distributions. For minimizing the total weighted completion time, we derive an approximation guarantee that depends only on the squared coefficient of variation of the underlying distributions for a simple priority policy. Our results constitute the first optimality and approximation guarantees for flow shops with stochastic reentry and demonstrate that established scheduling policies naturally extend to this setting through the proposed reduction.

Authors: Lloyd Allison

Conway's surreal numbers were aptly named by Knuth. This note examines how far one can get towards implementing surreals and the arithmetic operations on them so that they execute efficiently. Lazy evaluation and recursive data structures yield a considerable speed up.

Authors: Jianming Tong, Jingtian Dang, Simon Langowski, Tianhao Huang, Asra Ali, Jeremy Kun, Jevin Jiang, Srinivas Devadas, Tushar Krishna

Zero-knowledge proof (ZKP) provers remain costly because multi-scalar multiplication (MSM) and number-theoretic transforms (NTTs) dominate runtime as they need significant computation. AI ASICs such as TPUs provide massive matrix throughput and SotA energy efficiency. We present MORPH, the first framework that reformulates ZKP kernels to match AI-ASIC execution. We introduce Big-T complexity, a hardware-aware complexity model that exposes heterogeneous bottlenecks and layout-transformation costs ignored by Big-O. Guided by this analysis, (1) at arithmetic level, MORPH develops an MXU-centric extended-RNS lazy reduction that converts high-precision modular arithmetic into dense low-precision GEMMs, eliminating all carry chains, and (2) at dataflow level, MORPH constructs a unified-sharding layout-stationary TPU Pippenger MSM and optimized 3/5-step NTT that avoid on-TPU shuffles to minimize costly memory reorganization. Implemented in JAX, MORPH enables TPUv6e8 to achieve up-to 10x higher throughput on NTT and comparable throughput on MSM than GZKP. Our code: https://github.com/EfficientPPML/MORPH.

Authors: Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, Konstantin Makarychev

Quartet Reconstruction, the task of recovering a phylogenetic tree from smaller trees on four species called \textit{quartets}, is a well-studied problem in theoretical computer science with far-reaching connections to statistics, graph theory and biology. Given a random sample containing $m$ noisy quartets, labeled by an unknown ground-truth tree $T$ on $n$ taxa, we want to output a tree $\widehat T$ that is \textit{close} to $T$ in terms of quartet distance and can predict unseen quartets. Unfortunately, the empirical risk minimizer corresponds to the $\mathsf{NP}$-hard problem of finding a tree that maximizes agreements with the sampled quartets, and earlier works in approximation algorithms gave $(1-\eps)$-approximation schemes (PTAS) for dense instances with $m=Θ(n^4)$ quartets, or for $m=Θ(n^2\log n)$ quartets \textit{randomly} sampled from $T$. Prior to our work, it was unknown how many samples are information-theoretically required to learn the tree, and whether there is an efficient reconstruction algorithm. We present optimal results for reconstructing an unknown phylogenetic tree $T$ from a random sample of $m=Θ(n)$ quartets, corrupted under the Random Classification Noise (RCN) model. This matches the $Ω(n)$ lower bound required for any meaningful tree reconstruction. Our contribution is twofold: first, we give a tree reconstruction algorithm that, not only achieves a $(1-\eps)$-approximation, but most importantly \textit{recovers} a tree close to $T$ in quartet distance; second, we show a new $Θ(n)$ bound on the Natarajan dimension of phylogenies (an analog of VC dimension in multiclass classification). Our analysis relies on a new \textit{Quartet-based Embedding and Detection} procedure that identifies and removes well-clustered subtrees from the (unknown) ground-truth $T$ via semidefinite programming.

Authors: Zhangsong Li

The low-degree polynomial framework has emerged as a powerful tool for providing evidence of statistical-computational gaps in high-dimensional inference. For detection problems, the standard approach bounds the low-degree advantage through an explicit orthonormal basis. However, this method does not extend naturally to estimation tasks, and thus fails to capture the \emph{detection-recovery gap phenomenon} that arises in many high-dimensional problems. Although several important advances have been made to overcome this limitation \cite{SW22, SW25, CGGV25+}, the existing approaches often rely on delicate, model-specific combinatorial arguments. In this work, we develop a general approach for obtaining \emph{conditional computational lower bounds} for recovery problems from mild bounds on low-degree testing advantage. Our method combines the notion of algorithmic contiguity in \cite{Li25} with a cross-validation reduction in \cite{DHSS25} that converts successful recovery into a hypothesis test with lopsided success probabilities. In contrast to prior unconditional lower bounds, our argument is conceptually simple, flexible, and largely model-independent. We apply this framework to several canonical inference problems, including planted submatrix, planted dense subgraph, stochastic block model, multi-frequency angular synchronization, orthogonal group synchronization, and multi-layer stochastic block model. In the first three settings, our method recovers existing low-degree lower bounds for recovery in \cite{SW22, SW25} via a substantially simpler argument. In the latter three, it gives new evidence for conjectured computational thresholds including the persistence of detection-recovery gaps. Together, these results suggest that mild control of low-degree advantage is often sufficient to explain computational barriers for recovery in high-dimensional statistical models.