Theory of Computing Report

Here is a quick overview of my intuitions on where we are with AI safety in early 2026:

1. So far, we continue to see exponential improvements in capabilities. This is most visible in the famous “METR graph”, but the trend is clear in many other metrics, including revenue. If you squint, you can even see a potential recent “bending upward” of the curve, as we are starting to use AI to accelerate the development of AI.
   
   
2. We see some good news in alignment – as models become more capable, they are also more aligned, across multiple measures, including spec compliance. However, the improvement is not sufficient to match the higher stakes that come up with improved capabilities. We still have not fully solved challenges like adversarial robustness, dishonesty, and reward hacking, and we are still far from the standards of reliability and security that are required in high stake applications. (See slide below from Nicholas Carlini’s lecture in my AI safety course.) We also need to extend alignment beyond its traditional focus on the behavior of a model in an isolated conversation and in particular monitoring and aligning systems with a vast number of agents. Increasing the slope of the “alignment line” is the main focus of my technical research– working on building machines of faithful obedience that have good values but do not “legislate from the bench”.
   One might argue that current alignment is “good enough” for an automated alignment researcher, and the AIs can take it from here.  I disagree. I do not believe that all alignment is missing is one clever idea. Rather, we need ways to productively scale up compute into improving intent-following, honesty, monitoring, multi-agent alignment. This work will require multiple iterations of empirical experiments. AI can assist us in these, but it will not be a magic bullet. Also, we cannot afford to wait for AI to solve alignment for us, since in the meantime it will keep getting deployed in higher and higher stakes (including capability research).
   
    
3. One piece of good news is that we have arguably gone past the level where we can achieve safety via reliable and scalable human supervision, but are still able to improve alignment. Hence we avoided what could have been a plateauing of alignment as RLHF runs out of steam. This is related to the fact that we do not see very significant scheming or collusion in models, and so we are able to use models to monitor other models! (e.g., see this). This is perhaps the most important piece of good news on AI safety we have seen so far. We need to keep tracking this! (In particular, if models become schemers, then since they are already quite situationally aware, it will be hard to even measure their alignment, let alone improve it.) But there is reason to hope this trend will persist.
   
   
4. The worst news is that society is not ready for AI, and is not showing signs of getting ready. Whether it is facing increasing capabilities in areas like bio and cyber (including increasing capabilities of open source models), preparing for economic disruptions, enacting regulations and laws to protect democracy and individual empowerment (e.g., avoid scenarios like a country of IRS agents in a datacenter), or international collaborations on AI safety, our governments and institutions are not rising up to the challenge. This is perhaps the best argument for an “AI pause,” but (a) I do not think such a pause is feasible or practical, and (b) I am not confident that governments will use this time wisely— experience shows that it is hard to overestimate government’s capability for inaction.

`

By Boaz Barak

Generous funding at PhD and postdoc level is available for candidates willing to join the Centre for Credible AI at Warsaw University of Technology. The topical focus is to advance mathematically grounded theory of AI/ML with a general purpose of making AI more reliable.

Website: https://credibleai.github.io/join-us
Email: tsteifer@ippt.pan.pl

By shacharlovett

Authors: Lilith Zschetzsche, Refik Mansuroğlu, Norbert Schuch

The computational complexity of simulating the dynamics of physical quantum systems is a central question at the interface of quantum physics and computer science. In this work, we address this question for the simulation of exponentially large bosonic Hamiltonians with quadratic interactions. We present two results: First, we introduce a broad class of quadratic bosonic problems for which we prove that they are $\mathsf{BQP}$-complete. Importantly, this class includes two known $\mathsf{BQP}$-complete problems as special cases: Classical oscillator networks and continuous-time quantum walks. Second, we show that extending the aforementioned class to even more general quadratic Hamiltonians results in a $\mathsf{PostBQP}$-hard problem. This reveals a sharp transition in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers.

Authors: Sunidhi Singh, Vincent Liew, Marc Vinyals, Vijay Ganesh

We propose a new parameter called proofdoor in an attempt to explain the efficiency of CDCL SAT solvers over formulas derived from circuit (esp., arithmetic) verification applications. Informally, given an unsatisfiable CNF formula F over n variables, a proofdoor decomposition consists of a chunking of the clauses into A1, . . . , Ak together with a sequence of interpolants connecting these chunks. Intuitively, a proofdoor captures the idea that an unsatisfiable formula can be refuted by reasoning chunk by chunk, while maintaining only a summary of the information (i.e., interpolants) gained so far for subsequent reasoning steps. We prove several theorems in support of the proposition that proofdoors can explain the efficiency of CDCL solvers for some class of circuit verification problems. First, we show that formulas with small proofdoors (i.e., where each interpolant is O(n) sized, each chunk Ai has small pathwidth, and each interpolant clause has at most O(log(n)) backward dependency on the previous interpolant) have short resolution (Res) proofs. Second, we show that certain configurations of CDCL solvers can compute such proofs in time polynomial in n. Third, we show that commutativity (miter) formulas over floating-point addition have small proofdoors and hence short Res proofs, even though they have large pathwidth. Fourth, we characterize the limits of the proofdoor framework by connecting proofdoors to the partially ordered resolution proof system: we show that a poor decomposition of arithmetic miter instances can force exponentially large partially ordered resolution proofs, even when a different decomposition (i.e., small proofdoors) permits short proofs.

Authors: James Davies

We construct a complete Riemannian surface $Σ$ that admits no triangulation $G\subset Σ$ such that the inclusion $G^{(1)} \hookrightarrow Σ$ is a quasi-isometry, where $G^{(1)}$ is the simplicial 1-skeleton of $G$. Our construction is without boundary, has arbitrarily large systole, and furthermore, there is no embedded graph $G\subsetΣ$ such that $G^{(1)} \hookrightarrow Σ$ is a quasi-isometry. This answers a question of Georgakopoulos.

Authors: Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir

Let $K$ be a compact, centrally-symmetric, strictly-convex region in ${\mathbb R}^3$, which is a semi-algebraic set of constant complexity, i.e. the unit ball of a corresponding metric, denoted as $\|\cdot\|_K$. Let ${\mathcal{K}}$ be a set of $n$ homothetic copies of $K$. This paper contains two main sets of results: (i) For a storage parameter $s\in[n,n^3]$, ${\mathcal{K}}$ can be preprocessed in $O^*(s)$ expected time into a data structure of size $O^*(s)$, so that for a query homothet $K_0$ of $K$, an intersection-detection query (determine whether $K_0$ intersects any member of ${\mathcal{K}}$, and if so, report such a member) or a nearest-neighbor query (return the member of ${\mathcal{K}}$ whose $\|\cdot\|_K$-distance from $K_0$ is smallest) can be answered in $O^*(n/s^{1/3})$ time; all $k$ homothets of ${\mathcal{K}}$ intersecting $K_0$ can be reported in additional $O(k)$ time. In addition, the data structure supports insertions/deletions in $O^*(s/n)$ amortized expected time per operation. Here the $O^*(\cdot)$ notation hides factors of the form $n^\varepsilon$, where $\varepsilon>0$ is an arbitrarily small constant, and the constant of proportionality depends on $\varepsilon$. (ii) Let $\mathcal{G}(\mathcal{K})$ denote the intersection graph of ${\mathcal{K}}$. Using the above data structure, breadth-first or depth-first search on $\mathcal{G}(\mathcal{K})$ can be performed in $O^*(n^{3/2})$ expected time. Combining this result with the so-called shrink-and-bifurcate technique, the reverse-shortest-path problem in a suitably defined proximity graph of ${\mathcal{K}}$ can be solved in $O^*(n^{62/39})$ expected time. Dijkstra's shortest-path algorithm, as well as Prim's MST algorithm, on a $\|\cdot\|_K$-proximity graph on $n$ points in ${\mathbb R}^3$, with edges weighted by $\|\cdot\|_K$, can also be performed in $O^*(n^{3/2})$ time.

Authors: Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, David Manlove, Fabricio Mendoza, Daniël Paulusma

In a colouring of a graph, a vertex is b-chromatic if it is adjacent to a vertex of every other colour. We consider four well-studied colouring problems: b-Chromatic Number, Tight b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number, which fit into a framework based on whether every colour class has (i) at least one b-chromatic vertex, (ii) exactly one b-chromatic vertex, or (iii) all of its vertices being b-chromatic. By combining known and new results, we fully classify the computational complexity of b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number in $H$-free graphs. For Tight b-Chromatic Number in $H$-free graphs, we develop a general technique to determine new graphs $H$, for which the problem is polynomial-time solvable, and we also determine new graphs $H$, for which the problem is still NP-complete. We show, for the first time, the existence of a graph $H$ such that in $H$-free graphs, b-Chromatic Number is NP-hard, while Tight b-Chromatic Number is polynomial-time solvable.

Authors: Young Kun Ko

We resolve the long-standing open problem of Boolean dynamic data structure hardness, proving an unconditional lower bound of $Ω((\log n / \log\log n)^2)$ for the Multiphase Problem of Patrascu [STOC 2010] (instantiated with Inner Product over $\mathbb{F}_2$). This matches the celebrated barrier for weighted problems established by Larsen [STOC 2012] and closes the gap left by the $Ω(\log^{1.5} n)$ Boolean bound of Larsen, Weinstein, and Yu [STOC 2018]. The previous barrier was methodological: all prior works relied on ``one-way'' communication games, where the inability to verify query simulations necessitated complex machinery (such as the Peak-to-Average Lemma) that hit a hard ceiling at $\log^{1.5} n$. Our key contribution is conceptual: We introduce a 2.5-round Multiphase Communication Game that augments the standard one-way model with a verification round, where Bob confirms the consistency of Alice's simulation against the actual memory. This simple, qualitative change allows us to bypass technical barriers and obtain the optimal bound directly. As a consequence, our analysis naturally extends to other hard Boolean functions, offering a general recipe for translating discrepancy lower bounds into $Ω((\log n / \log\log n)^2)$ dynamic Boolean data structure lower bounds. We also argue that this result likely represents the structural ceiling of the Chronogram framework initiated by Fredman and Saks [STOC 1989]: any $ω(\log^2 n)$ lower bound would require either fundamentally new techniques or major circuit complexity breakthroughs.

Authors: Sándor Kisfaludi-Bak, Dániel Marx

We give approximation schemes for Subset TSP and Steiner Tree on unit disk graphs, and more generally, on intersection graphs of similarly sized connected fat (not necessarily convex) polygons in the plane. As a first step towards this goal, we prove spanner-type results: finding an induced subgraph of bounded size that is $(1+\varepsilon)$-equivalent to the original instance in the sense that the optimum value increases only by a factor of at most $(1+\varepsilon)$ when the solution can use only the edges in this subgraph. - For Subset TSP, our algorithms find a $(1+\varepsilon)$-equivalent induced subgraph of size $\mathrm{poly}(1/\varepsilon)\cdot\mathrm{OPT}$ in polynomial time, and use it to find a $(1+\varepsilon)$-approximate solution in time $2^{\mathrm{poly}(1/\varepsilon)}\cdot n^{O(1)}$. - For Steiner Tree, our algorithms find a $(1+\varepsilon)$-equivalent induced subgraph of size $2^{\mathrm{poly}(1/\varepsilon)}\cdot\mathrm{OPT}$ in time $2^{\mathrm{poly}(1/\varepsilon)}\cdot n^{O(1)}$, and use it to find a $(1+\varepsilon)$-approximate solution in time $2^{2^{\mathrm{poly}(1/\varepsilon)}}\cdot n^{O(1)}$. - An improved algorithm finds a $(1+\varepsilon)$-approximate solution for Steiner Tree in time $2^{\mathrm{poly}(1/\varepsilon)}\cdot n^{O(1)}$. An easy reduction shows that approximation schemes for unit disks imply approximation schemes for planar graphs. Thus our results are far-reaching generalizations of analogous results of Klein [STOC'06] and Borradaile, Klein, and Mathieu [ACM TALG'09] for Subset TSP and Steiner Tree in planar graphs. We show that our results are best possible in the sense that dropping any of (i) similarly sized, (ii) connected, or (iii) fat makes both problems APX-hard.

Authors: Hector Buffière, Yuquan Lin, Jaroslav Nešet{ř}il, Patrice {Ossona de Mendez}, Sebastian Siebertz

Tree-ordered weakly sparse models have recently emerged as a robust framework for representing structures in an ``almost sparse'' way, while allowing the structure to be reconstructed through a simple first-order interpretation. A prominent example is given by twin-models, which are bounded twin-width tree-ordered weakly sparse representations of structures with bounded twin-width derived from contraction sequences. In this paper, we develop this perspective further. First, we show that twin-models can be chosen such that they preserve linear clique-width or clique-width up to a constant factor. Then, we introduce \emph{merge-models}, a natural analog of twin-models for merge-width. Merge-models represent binary relational structures by tree-ordered weakly sparse structures. The original structures can then be recovered by a fixed first-order interpretation. A merge-model can be constructed from a merge sequence. Then, its radius-$r$ merge-width will be, up to a constant factor, bounded by the radius-$r$ width of the merge sequence from which it is derived. Finally, we show that twin-models arise naturally as special cases of merge-models, and that binary structures with bounded twin-width are exactly those having a loopless merge-model with bounded radius-$r_0$ merge-width (for some sufficiently large constant $r_0$).

Authors: Shay Mozes, Daniel Prigan

We prove that, up to subpolynomial or polylogarithmic factors, there is no tradeoff between preprocessing time, query time, and size of exact distance oracles for planar graphs. Namely, we show how given an $n$-vertex weighted directed planar graph $G$, one can compute in $n^{1+o(1)}$ time and space a representation of $G$ from which one can extract the exact distance between any two vertices of $G$ in $\log^{2+o(1)}(n)$ time. Previously, it was only known how to construct oracles with these space and query time in $n^{3/2+o(1)}$ time [STOC 2019, SODA 2021, JACM 2023]. We show how to construct these oracles in $n^{1+o(1)}$ time.

Authors: Ryosuke Yamano, Tetsuo Shibuya

The Shortest Common Superstring (SCS) problem is a fundamental task in sequence analysis. In genome assembly, however, the double-stranded nature of DNA implies that each fragment may occur either in its original orientation or as its reverse complement. This motivates the Shortest Common Superstring with Reverse Complements (SCS-RC) problem, which asks for a shortest string that contains, for each input string, either the string itself or its reverse complement as a substring. The previously best-known approximation ratio for SCS-RC was $\frac{23}{8}$. In this paper, we present a new approximation algorithm achieving an improved ratio of $\frac{8}{3}$. Our approach computes an optimal constrained cycle cover by reducing the problem, via a novel gadget construction, to a maximum-weight perfect matching in a general graph. We also investigate the computational hardness of SCS-RC. While the decision version is known to be NP-complete, no explicit inapproximability results were previously established. We show that the hardness of SCS carries over to SCS-RC through a polynomial-time reduction, implying that it is NP-hard to approximate SCS-RC within a factor better than $\frac{333}{332}$. Notably, this hardness result holds even for the DNA alphabet.

Authors: Chi-Yeh Chen

This paper addresses the scheduling problem for unrelated crowd workers in mobile social networks, where the required service time for each task varies among the assigned crowd workers. The goal is to minimize the total weighted completion time of all tasks. First, in an environment with identical crowd workers, we improve the approximation ratio of the Largest-Ratio-First (LRF) scheduling algorithm and provide an updated competitive ratio for its online version. Next, for the unrelated crowd workers environment, we introduce a randomized approximation algorithm that achieves an expected approximation ratio of 1.45. This result improves upon the 1.5-approximation ratio reported in our previous work. We also present a derandomization method for this algorithm. Furthermore, to improve computational efficiency, we propose an algorithm that leverages the property that the optimal schedule on a single crowd worker arranges tasks in non-increasing order by their Smith ratios. Experimental results demonstrate that our proposed method outperforms three variants of the LRF algorithm.

Yesterday Dana, the kids, and I went to the theater to watch The AI Doc: Or How I Became An Apocaloptimist, the well-reviewed new documentary about whether AGI will destroy the world. This was surely the weirdest family movie night we’ve ever done. Firstly, because I personally know probably half of the many people interviewed in the film, from Eliezer Yudkowsky to Ajeya Cotra to Liv Boeree to Daniel Kokotajlo to Ilya Sutskever to Jan Leike to Yoshua Bengio to Shane Legg to Sam Altman and Dario Amodei. But more importantly, because this is a documentary that repeatedly, explicitly, earnestly raises the question of whether children now alive will make it to adulthood, before unaligned AI kills them and everyone else. So pass the popcorn, kiddos!

(We did have popcorn. And if the kids were scared — well, I figured we can’t shield them forever from the great questions of the world they’re entering. But actually they didn’t seem especially scared.)

I thought that the filmmaker, Daniel Roher, did about as good a job as can be done, in fitting into a 100-minute film a question that honestly seems too gargantuan for any film — the question of the future of life on earth. He tries to hear out every faction: first the AI existential risk people, then the AI optimists and accelerationists like “Beff Jezos,” then the “stochastic parrot” / “current harms” people like Emily Bender and Timnit Gebru, and finally the AI company CEOs (Altman, Amodei, and Hassabis were the three who agreed to be interviewed), with Yuval Noah Harari showing up from time to time to insert deepities.

Roher plays the part of an anxious, curious, uninformed everyman, who finds each stance to be plausible enough while he’s listening to it, and who mostly just wants to know what kind of world his soon-to-be-born son (about whom we get regular updates) will grow up in.

I didn’t think all the interviewees were equally cogent or equally deserved a hearing. But if any viewers were actually new to AI discourse, rather than marinated in it like me, the film would serve for them as an excellent introduction to the parameters of current debate (for better or worse) and to some of the leading representatives of each camp.

If I had to summarize Roher’s conclusion, it would be something like: go ahead, enjoy your life, have children if you want, but understand that now is a time of world-historical promise and peril much like the early nuclear age, so pay attention, and demand of your elected leaders that they ensure that AGI is developed in a pro-human direction, because tech leaders (even the relatively well-intentioned ones) are trapped in a race to the bottom and can’t get out on their own. Honestly, I’d have a pretty hard time improving on that message.

The main thing that gave me pause about the film was not on the screen but in the theater, which was nearly empty. For the film to serve its purpose, a significant fraction of the world will need to see and discuss it, either in the theater or on streaming. So, y’know, it’s still playing.

For whatever it’s worth, here were my wife Dana’s comments: “The biggest flaw of this movie is that Daniel Roher never breaks out of his ‘clueless everyman’ character, even when he’s talking to the most important people in AI. He wastes an opportunity to ask them non-superficial questions, questions deeper than ‘so, uh, are we all gonna die or not?'”

And here were my 13-year-old daughter’s comments: “So many of the people they interviewed seemed like hippies, who don’t know what AI will do any more than I know!” Also, after Daniel Roher wishes Sam Altman mazel tov on his forthcoming baby: “Sam Altman is Jewish?!”

And here were my 9-year-old son’s comments: “I thought this would be a movie, where AI would try to take over and the humans would fight back! I had no idea it would just be people talking about it. The documentary kind of movie is so, so, so boring.”

By Scott

Occasionally I run into what I consider fun problems in complexity, that require just a little bit of out of the box thinking. They require some background in theory, but nothing too deep. Some of these problems have been mentioned before on my blog or social media.

By Lance Fortnow

We establish tight connections between entanglement entropy and the approximation error in Trotter–Suzuki product formulas for Hamiltonian simulation. Product formulas remain the workhorse of quantum simulation on near-term devices, yet standard error analyses yield worst-case bounds that can vastly overestimate the resources required for structured problems. For systems governed by geometrically local Hamiltonians with maximum entanglement entropy $S_{max}$ across all bipartitions, we prove that the first-order Trotter error scales as $O(t^2 S_{max} polylog(n) / r)$ rather than the worst-case $O(t^2 n / r)$, where $n$ is the system size and $r$ is the number of Trotter steps. This yields improvements of order $n^2$ for one-dimensional area-law systems and order $n^{3/2}$ for two-dimensional systems, up to logarithmic factors. We extend these bounds to higher-order Suzuki formulas, where the improvement factor involves $2^{p S^* / 2}$ for the $p$-th order formula. We further establish a separation result demonstrating that volume-law entangled systems fundamentally require order $n$ more Trotter steps than area-law systems to achieve the same precision, up to logarithmic factors. Our analysis combines Lieb–Robinson bounds for locality, tensor network representations for entanglement structure, and new commutator–entropy inequalities that bound the expectation value of nested commutators by the Schmidt rank of the state. These results have immediate applications to quantum chemistry, condensed matter simulation, and resource estimation for fault-tolerant quantum computing.

Recently, together with Kulikov, Mihajlin, and Smirnova (STACS 2026), we gave conditional constructions of functions with large monotone circuit complexity, matrices with high rigidity, and $3$-dimensional tensors of strongly superlinear rank. In this note, I strengthen the rigidity construction under the same assumption and, as a direct consequence, immediately obtain a slightly improved trade-off theorem for tensor rank.

Last summer, I was privileged to teach a two-week course on theoretical computer science to exceptional 11- and 12-year-olds at Epsilon Camp, held at Washington University in St. Louis. The course was basically a shorter version of the 6.045 course that I used to teach to undergrads at MIT.

I was at Epsilon Camp to accompany my son Daniel, who attended a different course there, for the 7- and 8-year-olds. So they got me to teach while I was there.

Teaching at Epsilon was some of the hardest work I’ve done in years: I taught two classes, held office hours, and interacted with or supervised students for 6-7 hours per day (compared to ~4 hours per week as a professor), on top of being Daniel’s sole caregiver, on top of email and all my other normal responsibilities. But it was also perhaps the most extraordinary teaching I’ve ever done: during “lecture,” the kids were throwing paper planes, talking over and interrupting me every ten seconds, and sometimes getting in physical fights with each other. In my ~20 years as a professor, this was the first time that I ever needed to worry about classroom discipline (!). It gave me newfound respect for what elementary school teachers handle every day.

But then, when I did have the kids’ attention, they would often ask questions or make observations that I would’ve been thrilled to hear from undergrads at UT Austin or MIT. Some of these kids, I felt certain, can grow up if they want to be world-leading mathematicians and physicists and computer scientists, Terry Taos and Ed Wittens of their generation. Or at least, that’ll be true if AI isn’t soon going to outperform the top human scientists at their own game, a prospect that of course casts a giant shadow not only over Epsilon Camp but over our entire enterprise. But enough about the future. For now I can say: it was a privilege of a lifetime to teach these kids, to be the one who first introduced them to theoretical computer science.

Or at least, the one who first systematically introduced them. As I soon realized, there was no topic I could mention—not the halting problem or the Busy Beaver function, not NP-completeness or Diffie-Hellman encryption—that some of these 11-year-olds hadn’t previously seen, and that they didn’t want to interrupt me to share everything they already knew about. Rather than fighting that tendency, I smiled and let them do this. While their knowledge was stunningly precocious, it was also fragmentary and disjointed and weirdly overindexed on examples rather than general principles. So fine, I still had something to teach them!

Coming to Epsilon Camp was also an emotional experience for me. When I was 15, I attended Canada/USA Mathcamp 1996, the first year that that camp operated. I might not have gone into research otherwise. Coming from a public high school—from the world of English teachers who mainly cared whether you adhered to the Five Paragraph Format, and chemistry teachers who’d give 0 on right answers if you didn’t write “1 mol / 1 mol” and then cross off both of the moles—I was suddenly thrust, sink or swim, into a course on elliptic curves taught by Ken Ribet, who’d played a major role in the proof of Fermat’s Last Theorem that had just been completed, and a talk on algorithms and complexity by Richard Karp himself, and lectures on number theory by Richard Guy, who had stories from when he knew G. H. Hardy.

Back when I was 15, I got to know George Rubin Thomas, the founding director of Mathcamp … and then, after 29 years, there he was again at Epsilon Camp—the patriarch of a whole ecosystem of math camps—and not only there, but sitting in on my course. Also at Epsilon Camp, unexpectedly, was a woman who I knew well back when we were undergrads at Cornell, both of took taking the theoretical computer science graduate sequence, but who I’d barely seen since. She, as it turned out, was accompanying her 8-year-old son, who got to know my 8-year-old. They played together every day and traded math facts.

---

It occurred to me that the course I taught, on theoretical computer science, was one of the most accessible I’ve ever done, and therefore more people might be interested. So I advertised on this blog for someone to help me LaTeX up the notes for wider distribution. I was thrilled to find a talented student to volunteer. Alas, because of where that student lives, he needs to stay anonymous for now. I thank him, pray for his safety, and hope to be able to reveal his name in the future. I’m also thrilled to have gotten three great high school students—Ian Ko, Tzak Lau, and Sunetra Rao—to help with the figures. Thanks to them as well.

You can read the notes here [59 pages, PDF]

If you’re curious, here’s the table of contents:

• Lecture 1: Bits
• Lecture 2: Gates
• Lecture 3: Finite Automata
• Lecture 4: Turing Machines
• Lecture 5: Big Numbers
• Lecture 6: Complexity, or Number of Operations
• Lecture 7: Polynomial vs. Exponential
• Lecture 8: The P vs. NP Problem
• Lecture 9: NP-completeness
• Lecture 10: Foundations of Cryptography
• Lecture 11: Public-Key Cryptography and Quantum Computing

Happy as always to receive comments and corrections. Enjoy!

By Scott

The Seventeenth International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2026) will be held in Aalborg, Denmark, in the period 15-17 September 2026. See

https://gandalfsymposium.github.io/2026/

for more information and the call for papers. The PC is co-chaired by Giorgio Bacci (Aalborg University, Denmark) and Mickaël Randour (Université de Mons, Belgium) and the event will be co-organised by Giorgio and Elli Anastasiadi.

Spread the news and submit to the event!

By Luca Aceto

We’re looking for an indepependent and motivated Postdoctoral Researcher to lead high-impact work in lattices and lattice-based cryptography. The candidate should have a strong publication record (STOC, FOCS, CRYPTO, EUROCRYPT, ASIACRYPT), and is expected to define their own research agenda. Competitive salary and a generous travel budget.

Website: https://sites.google.com/site/diveshhomepage/
Email: dcsdiva@nus.edu.sg

By shacharlovett

Authors: Don Yin

What substrate features allow life? We exhaustively classify all 262,144 outer-totalistic binary cellular automata rules with Moore neighbourhood for self-replication and produce phase diagrams in the $(λ, F)$ plane, where $λ$ is Langton's rule density and $F$ is a background-stability parameter. Of these rules, 20,152 (7.69%) support pattern proliferation, concentrated at low rule density ($λ\approx 0.15$--$0.25$) and low-to-moderate background stability ($F \approx 0.2$--$0.3$), in the weakly supercritical regime (Derrida coefficient $μ= 1.81$ for replicators vs. $1.39$ for non-replicators). Self-replicating rules are more approximately mass-conserving (mass-balance 0.21 vs. 0.34), and this generalises to $k{=}3$ Moore rules. A three-tier detection hierarchy (pattern proliferation, extended-length confirmation, and causal perturbation) yields an estimated 1.56% causal self-replication rate. Self-replication rate increases monotonically with neighbourhood size under equalised detection: von Neumann 4.79%, Moore 7.69%, extended Moore 16.69%. These results identify background stability and approximate mass conservation as the primary axes of the self-replication phase boundary.

Authors: P. Horak, I. Semaev

Let n denote the number of variables and m the number of equations in a sparse polynomial system over the binary field. We study the inconsistency probability of randomly generated sparse polynomial systems over the binary field, where each equation depends on at most k variables and the number of variables grows. Associating the system with a hypergraph, we show that the inconsistency probability depends strongly on structural properties of this hypergraph, not only on n,m, and k. Using inclusion--exclusion, we derive general bounds and obtain tight asymptotics for complete k-uniform hypergraphs. In the 2-sparse case, we provide explicit formulas for paths and stars, characterize extremal trees and forests, and conjecture a formula for cycles. These results have implications for SAT solving and cryptanalysis.

Authors: Geri Gokaj, Marvin Künnemann, Sabine Storandt, Carina Truschel

The Pareto sum of two-dimensional point sets $P$ and $Q$ in $\mathbb{R}^2$ is defined as the skyline of the points in their Minkowski sum. The problem of efficiently computing the Pareto sum arises frequently in bi-criteria optimization algorithms. Prior work establishes that computing the Pareto sum of sets $P$ and $Q$ of size $n$ suffers from conditional lower bounds that rule out strongly subquadratic $O(n^{2-ε})$-time algorithms, even when the output size is $Θ(n)$. Naturally, we ask: How efficiently can we \emph{approximate} Pareto sums, both in theory and practice? Can we beat the near-quadratic-time state of the art for exact algorithms? On the theoretical side, we formulate a notion of additively approximate Pareto sets and show that computing an approximate Pareto set is \emph{fine-grained equivalent} to Bounded Monotone Min-Plus Convolution. Leveraging a remarkable $\tilde{O}(n^{1.5})$-time algorithm for the latter problem (Chi, Duan, Xie, Zhang; STOC '22), we thus obtain a strongly subquadratic (and conditionally optimal) approximation algorithm for computing Pareto sums. On the practical side, we engineer different algorithmic approaches for approximating Pareto sets on realistic instances. Our implementations enable a granular trade-off between approximation quality and running time/output size compared to the state of the art for exact algorithms established in (Funke, Hespe, Sanders, Storandt, Truschel; Algorithmica '25). Perhaps surprisingly, the (theoretical) connection to Bounded Monotone Min-Plus Convolution remains beneficial even for our implementations: in particular, we implement a simplified, yet still subquadratic version of an algorithm due to Chi, Duan, Xie and Zhang, which on some sufficiently large instances outperforms the competing quadratic-time approaches.

Authors: Bruce W. Brewer, Haitao Wang

Let $S$ be a set of $n$ points in a polygon $P$ with $m$ vertices. The geodesic unit-disk graph $G(S)$ induced by $S$ has vertex set $S$ and contains an edge between two vertices whenever their geodesic distance in $P$ is at most one. In the weighted version, each edge is assigned weight equal to the geodesic distance between its endpoints; in the unweighted version, every edge has weight $1$. Given a source point $s \in S$, we study the problem of computing shortest paths from $s$ to all vertices of $G(S)$. To the best of our knowledge, this problem has not been investigated previously. A naive approach constructs $G(S)$ explicitly and then applies a standard shortest path algorithm for general graphs, but this requires quadratic time in the worst case, since $G(S)$ may contain $Ω(n^2)$ edges. In this paper, we give the first subquadratic-time algorithms for this problem. For the weighted case, when $P$ is a simple polygon, we obtain an $O(m + n \log^{2} n \log^{2} m)$-time algorithm. For the unweighted case, we provide an $O(m + n \log n \log^{2} m)$-time algorithm for simple polygons, and an $O(\sqrt{n} (n+m)\log(n+m))$-time algorithm for polygons with holes. To achieve these results, we develop a data structure for deletion-only geodesic unit-disk range emptiness queries, as well as a data structure for constructing implicit additively weighted geodesic Voronoi diagrams in simple polygons. In addition, we propose a dynamic data structure that extends Bentley's logarithmic method from insertions to priority-queue updates, namely insertion and delete-min operations. These results may be of independent interest.

Authors: Aaron Putterman, Salil Vadhan, Vadim Zaripov

Random subsampling of edges is a commonly employed technique in graph algorithms, underlying a vast array of modern algorithmic breakthroughs. Unfortunately, using this technique often leads to randomized algorithms with no clear path to derandomization because the analyses rely on a union bound on exponentially many events. In this work, we revisit this goal of derandomizing randomized sampling in graphs. We give several results related to bounded-independence edge subsampling, and in the process of doing so, generalize several of the results of Alon and Nussboim (FOCS 2008), who studied bounded-independence analogues of random graphs (which can be viewed as edge subsamples of the complete graph). Most notably, we show: 1. $O(\log(m))$-wise independence suffices for preserving connectivity when sampling at rate $1/2$ in a graph with minimum cut $\geq κ\log(m)$ with probability $1 - \frac{1}{\mathrm{poly}(m)}$ (for a sufficiently large constant $κ$). 2. $O(\log(m))$-wise $\frac{1}{\mathrm{poly}(m)}$-almost independence suffices for ensuring cycle-freeness when sampling at rate $1/2$ in a graph with minimum cycle length $\geq κ\log(m)$ with probability $1 - \frac{1}{\mathrm{poly}(m)}$ (for a sufficiently large constant $κ$). To demonstrate the utility of our results, we revisit the classic problem of using parallel algorithms to find graphic matroid bases, first studied in the work of Karp, Upfal, and Wigderson (FOCS 1985). In this regime, we show that the optimal algorithms of Khanna, Putterman, and Song (arxiv 2025) can be explicitly derandomized while maintaining near-optimality.

Authors: Christian Schulz, Jakob Ternes, Henning Woydt

In the NP-hard \textsc{Group Closeness Centrality Maximization} problem, the input is a graph $G = (V,E)$ and a positive integer $k$, and the task is to find a set $S \subseteq V$ of size $k$ that maximizes the reciprocal of group farness $f(S) = \sum_{v \in V} \min_{s \in S} \text{dist}(v,s)$. A widely used greedy algorithm with previously unknown approximation guarantee may produce arbitrarily poor approximations. To efficiently obtain solutions with quality guarantees, known exact and approximation algorithms are revised. The state-of-the-art exact algorithm iteratively solves ILPs of increasing size until the ILP at hand can represent an optimal solution. In this work, we propose two new techniques to further improve the algorithm. The first technique reduces the size of the ILPs while the second technique aims to minimize the number of needed iterations. Our improvements yield a speedup by a factor of $3.6$ over the next best exact algorithm and can achieve speedups by up to a factor of $22.3$. Furthermore, we add reduction techniques to a $1/5$-approximation algorithm, and show that these adaptations do not compromise its approximation guarantee. The improved algorithm achieves mean speedups of $1.4$ and a maximum speedup of up to $2.9$ times.

Authors: Santosh S. Vempala, Andre Wibisono

We present an efficient algorithm for uniformly sampling from an arbitrary compact body $\mathcal{X} \subset \mathbb{R}^n$ from a warm start under isoperimetry and a natural volume growth condition. Our result provides a substantial common generalization of known results for convex bodies and star-shaped bodies. The complexity of the algorithm is polynomial in the dimension, the Poincaré constant of the uniform distribution on $\mathcal{X}$ and the volume growth constant of the set $\mathcal{X}$.

Authors: Lucas Czech

We present efficient approaches for extracting spaced k-mers from nucleotide sequences. They are based on bit manipulation instructions at CPU level, making them both simpler to implement and up to an order of magnitude faster than existing methods. We further evaluate common pitfalls in k-mer processing, which can cause major inefficiencies. Combined, our approaches allow the utilization of spaced k-mers in high-performance bioinformatics applications without major performance degradation, offering a throughput of up to 750MB of sequence data per second per core. Availability: The implementation in C++20 is published under the MIT license, and freely available at https://github.com/lczech/fisk

Authors: Nima Anari, Alireza Haqi

We present the first polylogarithmic-round algorithm for sampling a random spanning tree in the (Broadcast) Congested Clique model. For any constant $c > 0$, our algorithm outputs a sample from a distribution whose total variation distance from the uniform spanning tree distribution is at most $O(n^{-c})$ in at most $c \cdot \log^{O(1)}(n)$ rounds. The exponent hidden in $\log^{O(1)}(n)$ is an absolute constant independent of $c$ and $n$. This is an exponential improvement over the previous best algorithm of Pemmaraju, Roy, and Sobel (PODC 2025) for the Congested Clique model.

Authors: David Torres Ramos, Vihan Lakshman, Chen Luo, Todd Treangen, Benjamin Coleman

We study the problem of building space-efficient, in-memory indexes for massive key-value datasets with highly skewed value distributions. This challenge arises in many data-intensive domains and is particularly acute in computational genomics, where $k$-mer count tables can contain billions of entries dominated by a single frequent value. While recent work has proposed to address this problem by augmenting compressed static functions (CSFs) with pre-filters, existing approaches rely on complex heuristics and lack formal guarantees. In this paper, we introduce a principled algorithm, called AutoCSF, for combining CSFs with pre-filtering to provably handle skewed distributions with near-optimal space usage. We improve upon prior CSF pre-filtering constructions by (1) deriving a mathematically rigorous decision criterion for when filter augmentation is beneficial; (2) presenting a general algorithmic framework for integrating CSFs with modern set membership data structures beyond the classic Bloom filter; and (3) establishing theoretical guarantees on the overall space usage of the resulting indexes. Our open-source implementation of AutoCSF demonstrates space savings over baseline methods while maintaining low query latency.

Authors: Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup

We give a near-linear time 4-coloring algorithm for planar graphs, improving on the previous quadratic time algorithm by Robertson et al. from 1996. Such an algorithm cannot be achieved by the known proofs of the Four Color Theorem (4CT). Technically speaking, we show the following significant generalization of the 4CT: every planar triangulation contains linearly many pairwise non-touching reducible configurations or pairwise non-crossing obstructing cycles of length at most 5 (which all allow for making effective 4-coloring reductions). The known proofs of the 4CT only show the existence of a single reducible configuration or obstructing cycle in the above statement. The existence is proved using the discharging method based on combinatorial curvature. It identifies reducible configurations in parts where the local neighborhood has positive combinatorial curvature. Our result significantly strengthens the known proofs of 4CT, showing that we can also find reductions in large ``flat" parts where the curvature is zero, and moreover, we can make reductions almost anywhere in a given planar graph. An interesting aspect of this is that such large flat parts are also found in large triangulations of any fixed surface. From a computational perspective, the old proofs allowed us to apply induction on a problem that is smaller by some additive constant. The inductive step took linear time, resulting in a quadratic total time. With our linear number of reducible configurations or obstructing cycles, we can reduce the problem size by a constant factor. Our inductive step takes $O(n\log n)$ time, yielding a 4-coloring in $O(n\log n)$ total time. In order to efficiently handle a linear number of reducible configurations, we need them to have certain robustness that could also be useful in other applications. All our reducible configurations are what is known as D-reducible.

No conference taking a broad view of contemporary culture can escape the bureaucracy sickos (laudatory). Bureaucracy, with the complex social relations it codifies and entails, is one of the most salient aspects of our culture. Bureaucracies box in massively complex bodies of information through standardization, measurement, and policies. Computers are amazing. They are also the physical embodiment of mass bureaucracy. And no computing technology is more bureaucratic than the large language model.

Several talks at the Cultural AI conference threaded together the complexities of language models and bureaucracy. Henry Farrell kicked things off with a characteristically fantastic talk, describing his evolving view of AI as cultural and social technology. He introduced the notion of “coarse graining,” a new angle he’s working on with Cosma Shalizi.

In physics, coarse graining means “averaging out” a lot of complexity to leave you with bulk behavior that describes useful things. Arguably, it’s how you go from quantum field theory to atomic theory to the ideal gas law.1 There are levels of approximations, and details are lost in the transitions between layers. However, this loss of detail is often worth it because stacking abstractions lets us think simply inside clean layers. Moreover, surfacing coarse graining helps us understand what to look for when one level of description doesn’t suffice to describe observed phenomena.

For Farrell, bureaucracies, democracies, and markets are cultural coarse grainings. Bureaucracy establishes relations between parts such that management at one particular location in an organizational web can make decisions without having to understand the fine details at all other locations. It creates a distribution of decision making, simultaneously bound and freed by rules. We can see LLMs as coarse grainings that allow us to access mediated linguistic relationships between end users and the cultural material on which they were trained.

Good bureaucracy should provide constraints that deconstrain.2 However, so often bureaucracy, in its taming of complexity, obscures sources of power in cultural relationships and the human agency behind decision making. Lily Chumley and Abbie Jacobs both spoke to different angles of this concealment.

Through the lens of linguistic anthropology, Chumley described how language models obscure contractual relationships underlying enterprise software. The primary interaction with language models is through the chat box. When we squeeze our demands into prompts and skill files that use the institutional language of management, we are mimicking the casual nature of Irving Goffman’s “open-state of talk” with a computer. The interaction feels personal rather than transactional. However, your interactions with all of the work software are contingent on inscrutable vendor contracts with complex webs of accountabilities, restrictions, and obligations. The employee is left with only a chat interface that has been RLHFed into a servile caricature of a 1950s secretary. This erases the heavily surveilled, legally bound, hyper monetized relationships between corporate behemoths.

Chumley illustrated this through the SAAS web on the academic campus. Though we feel like we’re working with LLMs like they are other co-workers:

Every interaction with an LLM or web interface portal or training is mediated by a complex contract with giant corporations, be they Elsevier (who own Interfolio), Salesforce, SLATE Technolutions, Google, Microsoft, NVIDIA, OpenAI, or Anthropic. It is a move of power away from people to a fabric of capital. Gideon Lewis-Kraus commented that these power shifts from engineering to capital have been symptomatic of post-Cold War America and have had dire consequences, as in the example of Boeing.

Chumley extended her contractual analysis to the bureaucratic war machine that Kevin Baker has been so eloquently writing about. Big Tech owns AI, so this poses complex risks to the financial order as these companies are too big to fail. And yet, Big Tech is really small compared to the state. The relationships between the tech companies and the government established through military contracting are geopolitical. This means that even if we had a functioning Congress,3 the regulation of military AI would be ensnared in transnational agreements. Not only is the use of AI in warfare a smokescreen to avoid talking about the people who control decisions of violence, but it further entangles geopolitics in a big contractual mess.

From the perspective of measurement theory, Abbie Jacobs discussed how the language of governance, when coarse-grained into AI, creates new meaning. Jacobs argued that operationalizing language always in the context of governance requires conceptualizing how to measure those concepts. And this measurement and quantization are often not talked about by those doing the coding. We see this sort of talk about computing systems all the time. Words like “high-quality,” “relevant,” “toxic,” “harmful,” “age-appropriate,” “safe,” “responsible,” “fair,” “intelligence” are turned into rigid measurements by communities of coders, researchers, and policymakers. This operationalization through bureaucratic technology creates a new kind of coarse graining in which words gain meaning through their institutionalization. Arguments at this operationalized level themselves become exclusionary. Jacobs leans on measurement theory from the quantitative social sciences, arguing that “Measurement is the (usually hidden, implicit, diffuse) process through which these concepts are instantiated and made real.”

Measurement itself is governance. I associate this assertion with Theodore Porter, though he’d probably credit Horkheimer and Adorno’s Dialectic of Enlightenment. Jacobs argues that we have to bring such measurement to the surface of social technology before we go about asking our coding agents to coarse-grain it. If we can uncover the measurement process itself, then these hidden webs of governance perhaps become more legible to all of us caught in the middle. By fighting about operationalization, you are implicitly fighting about values. You are fighting about how the state sees you.

This will be my last dispatch on the Cultural AI conference for now. I don’t think I fully did justice to the speakers’ arguments or to the discussion at the conference, but the talks will be available on YouTube soon.

I’ll close with a few thoughts about “conferences” more generally. We use the same word to describe an academic gathering of ten people as fifty thousand, but those meetings couldn’t be more different. The one thing I wish we were better at was marking the proceedings of these small workshops in some non-empheral state. There is value in simply getting people in a room and then seeing influential intellectual artifacts manifest in later work. Some conversations are better when everyone knows there will be no permanent record. Not every conversation needs to become an Overleaf. Still, capturing something about the moment has value, too. I guess Max and I are blogging a bit, and that’s not nothing. There will be YouTube videos, as I have mentioned. But I’ve been thinking a lot about what it would mean to organize, archive, and coarse grain these small moments of intellectual discourse. To be continued.

Subscribe now

By Ben Recht

Authors: Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, Charalampos Kokkalis

We study the complexity of computing Bayes-Nash equilibria in single-item first-price auctions. We present the first efficient algorithms for the problem, when the bidders' values for the item are independently drawn from the same continuous distribution, under both established variants of continuous and finite bidding sets. More precisely, we design polynomial-time algorithms for the white-box model, where the distribution is provided directly as part of the input, and query-efficient algorithms for the black-box model, where the distribution is accessed via oracle calls. Our results settle the computational complexity of the problem for bidders with i.i.d. values.

Authors: Stefan Friedl, Tobias Hirsch, Marc Kegel

In this short expository note, we give a detailed proof of Markov's theorem on the unsolvability of the homeomorphism problem and of the existence of unrecognizable manifolds in all dimensions larger than 3.

Authors: Jinho Bok, Shuangping Li, Sophie H. Yu

We study the problem of detecting local geometry in random graphs. We introduce a model $\mathcal{G}(n, p, d, k)$, where a hidden community of average size $k$ has edges drawn as a random geometric graph on $\mathbb{S}^{d-1}$, while all remaining edges follow the Erdős--Rényi model $\mathcal{G}(n, p)$. The random geometric graph is generated by thresholding inner products of latent vectors on $\mathbb{S}^{d-1}$, with each edge having marginal probability equal to $p$. This implies that $\mathcal{G}(n, p, d, k)$ and $\mathcal{G}(n, p)$ are indistinguishable at the level of the marginals, and the signal lies entirely in the edge dependencies induced by the local geometry. We investigate both the information-theoretic and computational limits of detection. On the information-theoretic side, our upper bounds follow from three tests based on signed triangle counts: a global test, a scan test, and a constrained scan test; our lower bounds follow from two complementary methods: truncated second moment via Wishart--GOE comparison, and tensorization of KL divergence. These results together settle the detection threshold at $d = \widetildeΘ(k^2 \vee k^6/n^3)$ for fixed $p$, and extend the state-of-the-art bounds from the full model (i.e., $k = n$) for vanishing $p$. On the computational side, we identify a computational--statistical gap and provide evidence via the low-degree polynomial framework, as well as the suboptimality of signed cycle counts of length $\ell \geq 4$.

Authors: Philip Kaminsky, Rachitesh Kumar, Roger Lederman

The freight industry is undergoing a digital revolution, with an ever-growing volume of transactions being facilitated by digital marketplaces. A core capability of these marketplaces is the fulfillment of demand for truckload movements (loads) by procuring the services of carriers who execute them. Notably, these services are procured both through long-term contracts, where carriers commit capacity to execute loads (e.g., contracted fleet of drivers or lane-level commitments), and through short-term spot marketplaces, where carriers can agree to move individual loads for the offered price. This naturally couples two canonical problems of the transportation industry: contract assignment and spot pricing. In this work, we model and analyze the problem of coordinating long-term contract supply and short-term spot supply to minimize total procurement costs. We develop a Dual Frank Wolfe algorithm to compute shadow prices which allow the spot pricing policy to account for the committed contract capacity. We show that our algorithm achieves small relative regret against the optimal -- but intractable -- dynamic programming benchmark when the size of the market is large. Importantly, our Dual Frank Wolfe algorithm is computationally efficient, modular, and only requires oracle access to spot-pricing protocols, making it ideal for large-scale markets. Finally, we evaluate our algorithm on semi-synthetic data from a major Digital Freight Marketplace, and find that it yields significant savings ($\approx 10\%$) compared to a popular status-quo method.

Authors: Sanjeev Khanna, Christian Konrad, Aaron Putterman

Fault-tolerant spanners are fundamental objects that preserve distances in graphs even under edge failures. A long line of work culminating in Bodwin, Dinitz, Robelle (SODA 2022) gives $(2k-1)$-stretch, $f$-fault-tolerant spanners with $O(k^2 f^{\frac{1}{2}-\frac{1}{2k}} n^{1+\frac{1}{k}} + k f n)$ edges for any odd $k$. For any $k = \tilde{O}(1)$, this bound is essentially optimal for deterministic spanners in part due to a known folklore lower bound that \emph{any} $f$-fault-tolerant spanner requires $Ω(nf)$ edges in the worst case. For $f \geq n$, this $Ω(nf)$ barrier means that any $f$-fault tolerant spanners are trivial in size. Crucially however, this folklore lower bound exploits that the spanner \emph{is itself a subgraph}. It does not rule out distance-reporting data structures that may not be subgraphs. This leads to our central question: can one beat the $n \cdot f$ barrier with fault-tolerant distance oracles? We give a strong affirmative answer to this question. As our first contribution, we construct $f$-fault-tolerant distance oracles with stretch $O(\log(n)\log\log(n))$ that require only $\widetilde{O}(n\sqrt{f})$ bits of space; substantially below the spanner barrier of $n \cdot f$. Beyond this, in the regime $n \leq f \leq n^{3/2}$ we show that by using our new \emph{high-degree, low-diameter} decomposition in combination with tools from sparse recovery, we can even obtain stretch $7$ distance oracles in space $\widetilde{O}(n^{3/2}f^{1/3})$ bits. We also show that our techniques are sufficiently general to yield randomized sketches for fault-tolerant ``oblivious'' spanners and fault-tolerant deterministic distance oracles in bounded-deletion streams, with space below the $nf$ barrier in both settings.

Authors: Stefan Kratsch

A large number of NP-hard graph problems can be solved in $f(w)n^{O(1)}$ time and space when the input graph is provided together with a tree decomposition of width $w$, in many cases with a modest exponential dependence $f(w)$ on $w$. Moreover, assuming the Strong Exponential-Time Hypothesis (SETH) we have essentially matching lower bounds for many such problems. They main drawback of these results is that the corresponding dynamic programming algorithms use exponential space, which makes them infeasible for larger $w$, and there is some evidence that this cannot be avoided. This motivates using somewhat more restrictive structure/decompositions of the graph to also get good (exponential) dependence on the corresponding parameter but use only polynomial space. A number of papers have contributed to this quest by studying problems relative to treedepth, and have obtained fast polynomial space algorithms, often matching the dependence on treewidth in the time bound. E.g., a number of connectivity problems could be solved by adapting the cut-and-count technique of Cygan et al. (FOCS 2011, TALG 2022) to treedepth, but this excluded well-known path and cycle problems such as Hamiltonian Cycle (Hegerfeld and Kratsch, STACS 2020). Recently, Nederlof et al. (SIDMA 2023) showed how to solve Hamiltonian Cycle, and several related problems, in $5^τn^{O(1)}$ randomized time and polynomial space when provided with an elimination forest of depth $τ$. We present a faster (also randomized) algorithm, running in $4^τn^{O(1)}$ time and polynomial space, for the same set of problems. We use ordered pairs of what we call consistent matchings, rather than perfect matchings in an auxiliary graph, to get the improved time bound.

Authors: Anne Driemel, Jan Höckendorff, Ioannis Psarros, Christian Sohler, Di Yue

Given a finite metric space $(X\cup Y, \mathbf{d})$ the $k$-median problem is to find a set of $k$ centers $C\subseteq Y$ that minimizes $\sum_{p\in X} \min_{c\in C} \mathbf{d}(p,c)$. In general metrics, the best polynomial time algorithm computes a $(2+ε)$-approximation for arbitrary $ε>0$ (Cohen-Addad et al. STOC 2025). However, if the metric is doubling, a near linear time $(1+ε)$-approximation algorithm is known (Cohen-Addad et al. J. ACM 2021). We show that the $(1+ε)$-approximation algorithm can be generalized to the case when either $X$ or $Y$ has bounded doubling dimension (but the other set not). The case when $X$ is doubling is motivated by the assumption that even though $X$ is part of a high-dimensional space, it may be that it is close to a low-dimensional structure. The case when $Y$ is doubling is motivated by specific clustering problems where the centers are low-dimensional. Specifically, our work in this setting implies the first near linear time approximation algorithm for the $(k,\ell)$-median problem under discrete Fréchet distance when $\ell$ is constant. We further introduce a novel complexity reduction for time series of real values that leads to a similar result for the case of discrete Fréchet distance. In order to solve the case when $Y$ has a bounded doubling dimension, we introduce a dimension reduction that replaces points from $X$ by sets of points in $Y$. To solve the case when $X$ has a bounded doubling dimension, we generalize Talwar's decomposition (Talwar STOC 2004) to our setting. The running time of our algorithms is $2^{2^t} \tilde O(n+m)$ where $t=O(\mathrm{ddim} \log \frac{\mathrm{ddim}}ε)$ and where $\mathrm{ddim}$ is the doubling dimension of $X$ (resp.\ $Y$). The results also extend to the metric facility location problem.

Authors: Igor S. Sergeev

This article provides a survey of circuit complexity bounds for basic boolean transforms exploited in digital circuit design and efficient methods for synthesizing such circuits. The exposition covers structurally simple functions and operators, such as counters, adders, encoders, and multiplexors, and excludes more complex algebraic operations with numbers, polynomials, and matrices. Several applications to implementing more specific operations are also discussed.

Authors: Slobodan Mitrović, Srikkanth Ramachandran, Ronitt Rubinfeld, Mihir Singhal

In this work, we focus on designing an efficient Local Computation Algorithm (LCA) for the set cover problem, which is a core optimization task. The state-of-the-art LCA for computing $O(\log Δ)$-approximate set cover, developed by Grunau, Mitrović, Rubinfeld, and Vakilian [SODA '20], achieves query complexity of $Δ^{O(\log Δ)} \cdot f^{O(\log Δ\cdot (\log \log Δ+ \log \log f))}$, where $Δ$ is the maximum set size, and $f$ is the maximum frequency of any element in sets. We present a new LCA that solves this problem using $f^{O(\log Δ)}$ queries. Specifically, for instances where $f = \text{poly} \log Δ$, our algorithm improves the query complexity from $Δ^{O(\log Δ)}$ to $Δ^{O(\log \log Δ)}$. Our central technical contribution in designing LCAs is to aggressively sparsify the input instance but to allow for \emph{retroactive updates}. Namely, our main LCA sometimes ``corrects'' decisions it made in the previous recursive LCA calls. It enables us to achieve stronger concentration guarantees, which in turn allows for more efficient and ``sparser'' LCA execution. We believe that this technique will be of independent interest.

Authors: Rayen Tan, Viswanath Nagarajan

The $k$-of-$n$ testing problem involves performing $n$ independent tests sequentially, in order to determine whether/not at least $k$ tests pass. The objective is to minimize the expected cost of testing. This is a fundamental and well-studied stochastic optimization problem. However, a key limitation of this model is that the success/failure probability of each test is assumed to be known precisely. In this paper, we relax this assumption and study a distributionally-robust model for $k$-of-$n$ testing. In our setting, each test is associated with an interval that contains its (unknown) failure probability. The goal is to find a solution that minimizes the worst-case expected cost, where each test's probability is chosen from its interval. We focus on non-adaptive solutions, that are specified by a fixed permutation of the tests. When all test costs are unit, we obtain a $2$-approximation algorithm for distributionally-robust $k$-of-$n$ testing. For general costs, we obtain an $O(\frac{1}{\sqrt ε})$-approximation algorithm on $ε$-bounded instances where each uncertainty interval is contained in $[ε, 1-ε]$. We also consider the inner maximization problem for distributionally-robust $k$-of-$n$: this involves finding the worst-case probabilities from the uncertainty intervals for a given solution. For this problem, in addition to the above approximation ratios, we obtain a quasi-polynomial time approximation scheme under the assumption that all costs are polynomially bounded.

Authors: Arlen Dean, Zijin Zhang, Stefanus Jasin, Yuqing Liu

Deploying multiple large language models (LLMs) in parallel to classify an unknown ground-truth label is a common practice, yet the problem of optimally allocating queries across heterogeneous models remains poorly understood. In this paper, we formulate a robust, offline query-planning problem that minimizes total query cost subject to statewise error constraints which guarantee reliability for every possible ground-truth label. We first establish that this problem is NP-hard via a reduction from the minimum-weight set cover problem. To overcome this intractability, we develop a surrogate by combining a union bound decomposition of the multi-class error into pairwise comparisons with Chernoff-type concentration bounds. The resulting surrogate admits a closed-form, multiplicatively separable expression in the query counts and is guaranteed to be feasibility-preserving. We further show that the surrogate is asymptotically tight at the optimization level: the ratio of surrogate-optimal cost to true optimal cost converges to one as error tolerances shrink, with an explicit rate of $O\left(\log\log(1/α_{\min}) / \log(1/α_{\min})\right)$. Finally, we design an asymptotic fully polynomial-time approximation scheme (AFPTAS) that returns a surrogate-feasible query plan within a $(1+\varepsilon)$ factor of the surrogate optimum.

April 23-24, 2026 University of Warwick https://qcow.cs.ox.ac.uk/ QCOW is a new series of meetings dedicated to advancing the understanding of fundamental questions and open problems in quantum complexity theory. The meetings will rotate between universities of Cambridge, Oxford, and Warwick, with each event focusing on a specific theme within the theoretical foundations of quantum computation. … Continue reading 2nd Quantum Cambridge-Oxford-Warwick Colloquium (QCOW)

By shacharlovett

High table dinner at Magdalen

My time in Oxford has come to an end and I head back to Chicago this week. I was a visiting Fellow at Magdalen (pronounced "maudlin") College for the Hilary Term.

By Lance Fortnow

Authors: Guangxu Yang, Jiapeng Zhang

Numbers-on-Forehead (NOF) communication model is a central model in communication complexity. As a restricted variant, one-way NOF model is of particular interest. Establishing strong one-way NOF lower bounds would imply circuit lower bounds, resolve well-known problems in additive combinatorics, and yield wide-ranging applications in areas such as cryptography and distributed computing. However, proving strong lower bounds in one-way NOF communication remains highly challenging; many fundamental questions in one-way NOF communication remain wide open. One of the fundamental questions, proposed by Gavinsky and Pudlák (CCC 2008), is to establish an explicit exponential separation between quantum and classical one-way NOF communication. In this paper, we resolve this open problem by establishing the first exponential separation between quantum and randomized communication complexity in one-way NOF model. Specifically, we define a lifted variant of the Hidden Matching problem of Bar-Yossef, Jayram, and Kerenidis (STOC 2004) and show that it admits an ($O(\log n)$)-cost quantum protocol in the one-way NOF setting. By contrast, we prove that any $k$-party one-way randomized protocol for this problem requires communication $Ω(\frac{n^{1/3}}{2^{k/3}})$. Notably, our separation applies even to a generalization of $k$-player one-way communication, where the first player speaks once, and all other $k-1$ players can communicate freely.

Authors: Anders Aamand, Mikkel Abrahamsen, Reilly Browne, Mayank Goswami, Prahlad Narasimhan Kasthurirangan, Linda Kleist, Joseph S. B. Mitchell, Valentin Polishchuk, Jack Stade

We study the problems of covering or partitioning a polygon $P$ (possibly with holes) using a minimum number of small pieces, where a small piece is a connected sub-polygon contained in an axis-aligned unit square. For covering, we seek to write $P$ as a union of small pieces, and in partitioning, we furthermore require the pieces to be pairwise interior-disjoint. We show that these problems are in fact equivalent: Optimum covers and partitions have the same number of pieces. For covering, a natural local search algorithm repeatedly attempts to replace $k$ pieces from a candidate cover with $k-1$ pieces. In two dimensions and for sufficiently large $k$, we show that when no such swap is possible, the cover is a $1+O(1/\sqrt k)$-approximation, hence obtaining the first PTAS for the problem. Prior to our work, the only known algorithm was a $13$-approximation that only works for polygons without holes [Abrahamsen and Rasmussen, SODA 2025]. In contrast, in the three dimensional version of the problem, for a polyhedron $P$ of complexity $n$, we show that it is NP-hard to approximate an optimal cover or partition to within a factor that is logarithmic in $n$, even if $P$ is simple, i.e., has genus $0$ and no holes.

Authors: Joachim Gudmundsson, Yuan Sha, Sampson Wong

In the celebrated paper of Henzinger, Klein, Rao and Subramanian (1997), it was shown that planar graphs admit a linear time single-source shortest path algorithm. Their algorithm unfortunately does not extend to Euclidean graph classes. We give criteria and prove that any Euclidean graph class satisfying the criteria admits a linear time single-source shortest path algorithm. As a main ingredient, we show that the contracted graphs of these Euclidean graph classes admit sublinear separators.

Authors: Dariush Amirkhani, Junfeng Zhang

We propose a novel iterative process to establish the minimum separation between two ellipsoids. The method maintains one point on each surface and updates their locations in the theta-phi parametric space. The tension along the connecting segment between the two surface points serves as the guidance for the sliding direction, and the distance between them decreases gradually. The minimum distance is established when the connecting segment becomes perpendicular to the ellipsoid surfaces, at which point the net effect of the segment tension disappears and the surface points no longer move. Demonstration examples are carefully designed, and excellent numerical performance is observed, including accuracy, consistency, stability, and robustness. Furthermore, compared to other existing techniques, this surface-sliding approach has several attractive features, such as clear geometric representation, concise formulation, a simple algorithm, and the potential to be extended straightforwardly to other situations. This method is expected to be useful for future studies in computer graphics, engineering design, material modeling, and scientific simulations.

Authors: Oliver Chubet, Niyathi Kukkapalli, Anvi Kudaraya, Don Sheehy

Given a metric space, a standard metric range search, given a query $(q,r)$, finds all points within distance $r$ of the point $q$. Suppose now we have two different metrics $d_1$ and $d_2$. A product range query $(q, r_1, r_2)$ is a point $q$ and two radii $r_1$ and $r_2$. The output is all points within distance $r_1$ of $q$ with respect to $d_1$ and all points within $r_2$ of $q$ with respect to $d_2$. In other words, it is the intersection of two searches. We present two data structures for approximate product range search in doubling metrics. Both data structures use a net-tree variant, the greedy tree. The greedy tree is a data structure that can efficiently answer approximate range searches in doubling metrics. The first data structure is a generalization of the range tree from computational geometry using greedy trees rather than binary trees. The second data structure is a single greedy tree constructed on the product induced by the two metrics.