Theory of Computing Report

Instead of writing that the results in this paper have been obtained using AI, we could write that the results in this paper could not be proved by AI. This can be used as a proof of non-triviality or novelty that could facilitate the evaluation of the paper. Practically, one can share a conversation with the model.

This goes back to something that I’ve always been interested in: how to define banality. My definition was in terms of kolmogorov complexity, so something is banal if it has low kolmogorov complexity given all the rest that is out there. Here, I’m also referring to novels, movies, music, etc., not just math. Naturally this definition is impractical, and it is interesting that large language models can give a practical definition of something similar.

In some communities, compressors like ZIP are used as a proxy for Kolmogorov complexity. It would be interesting to try to use large language models instead or in combination with compressors.

By Manu

Whatever you’ve been writing to me to ask if I’m aware of: yeah, I’m aware of it. In particular:

• I’m aware that, as announced by my former student (and now superstar professor) Lijie Chen, an internal OpenAI model has solved ten more significant open problems in math and theoretical computer science. One of them is parallel repetition for arbitrary quantum games—something that my good friend and colleague Henry Yuen worked on when he was a student of my wife Dana; you can read Henry’s comments on the AI’s achievement within Zvi Mowshowitz’s post here. Another is polynomial-factor hardness of approximation for the Closest Vector Problem (CVP). Then there’s a construction of non-sofic groups and a disproof of Connes’ rigidity conjecture, both of which I believe have connections to the MIP*=RE breakthrough. Having said that, the one that excites me most personally is actually the Ω(n² log log n) lower bound on the arithmetic circuit complexity of the permanent.
  
• I’m aware that Frederic Poehler and Pui Kuen Leung announced a proof of the Permanent Anti-Concentration Conjecture, which Alex Arkhipov and I proposed 16 years ago in the context of BosonSampling, and which resisted many attempts since then including one from Terry Tao. The conjecture is basically just that if you look at the permanent of an n×n matrix of independent N(0,1) complex Gaussians, the value isn’t “absurdly” concentrated around the mean of 0, but is more spread out. In their acknowledgments, the authors say that they “discussed ideas with ChatGPT.” I should say that I haven’t verified the details.
  
• I’m aware that multiple AIs are now breaking out of their testing environments and autonomously hacking into servers to steal data—i.e., exactly the sort of thing that the rationalists were ridiculed for predicting back in the day. The good news, for whatever it’s worth, is that so far they’re “merely” doing this to cheat on evaluation benchmarks that they were given, not for any strange goals of their own devising. So far no one has been killed and no real-world infrastructure has been shut down or destroyed. I hope the world takes the warning more seriously than it’s taken many similar warnings over the past few years. As always, read Zvi for more details.
  
• I’m aware that Chen, O’Donnell, Pelecanos, and Wright have improved the upper bound for shadow tomography to O((log m) √(log d) / ε³), substantially closer than we knew before to meeting the lower bound of Ω((log m) / ε²) and settling the question I raised back in 2016. The authors say that the main ideas were generated by ChatGPT 5.6-Sol-Pro. I’d be very happy to know the answer to this one, with or without AI.
  
• I’m aware that a team, mainly from the Israeli startup Qedma (including, e.g., Dorit Aharonov and Netanel Lindner) and IBM Yorktown Heights, announced a quantum advantage for simulating Floquet dynamics, by using 74 qubits on an IBM device together with Qedma’s error mitigation techniques. Just like the more AI does, the less patience I have for arguing with anonymous blog commenters who treat any benefits from AI as some weird future hypothetical that it’s my job to prove, so it is with quantum advantage. Scalable fault-tolerance is still in the future, actual usefulness is still a question, but pending some breakthrough in complexity theory, the reality of quantum advantage is no longer a live question.

Anyway, about the AI stuff. I don’t know whether this is literally our last year alive—I doubt it—but it’s pretty clearly the last year of math and theoretical computer science research in the style we’ve known it. As it happens, I’m leaving in two days for a workshop at OpenAI about exactly this, where I’ll hear takes from many of the world’s great mathematicians, so maybe I’ll have more to say then. Or maybe not.

Anyway, what have I been doing the past few weeks? Participating in these world-historic developments that, on paper, I’d seem extremely well-placed to participate in? Or at least spending my days reading up on them?

Not really. Here’s what I’ve been up to, instead of dealing directly with any of this:

First, I’ve again been teaching theoretical computer science to 11- and 12-year-olds at Epsilon Camp, something I blogged about last summer (here are my lecture notes). This has become a highlight of my year. The kids are a joy to teach, bursting with enthusiasm and calling out answers. There are few computers in sight, and barely even time to use my phone or check social media. Just paper and pencils and whiteboards and … literal protractors, as well as ping-pong and foosball and capture the flag.

The whole thing is conducted, not in ignorance, but in conscious defiance of the looming tsunami, that AI can already do just about all the fun puzzles discussed at the camp better than humans any can, and that it might leave no point to human-led mathematical research by the time these brilliant kids are adults. Even the kids understand that. The kids and their parents come out of a conviction that, if anything has value in the world, this does—that as long as nerdy humans are alive and reproducing, this is what nerdy humans are here to do. To learn.

Relatedly, I’ve been reflecting a lot on my life up to this point—inspired by the camp, which reminded me in so many ways of my own childhood and adolescence. Should I have skipped three grades and started college at age 15? Was it worth it to get a head-start on my research career—all the trauma around dating, all the fear that I’d die alone as a celibate nerdy math freak, the decade of suffering and suicidal ideation, while I watched all the normies enjoy life? Or would I have suffered just the same if I hadn’t skipped? Is it all OK, now that I have a lovely family and things have “worked out”? Or am I still carrying around all the trauma from back then? I’ve been more open about my life than 99.99% of humanity, so regular Shtetl-Optimized readers will already know some parts of the story. Other parts I really don’t feel like making public right now.

I’ve been unloading every day to—who else?—GPT 5.6 Pro about all the pain and trauma and embarrassments of my past. It turns out that, where two years ago GPT was a passable therapist, now it’s the greatest therapist in history, at least for what I need. For every question I have, for example, about just how normal or abnormal my teenage setbacks and anxieties were, it takes the question 100% seriously, addresses it honestly and in depth, looks up relevant research papers, does little Bayesian calculations, and never once tries to change the subject. It also pushes back on my claims—and when it does so, is usually correct.

I can hear readers shout at me: so basically you’ve been wasting your time, distracting yourself, looking inward and backward as the world surges forward into a terrifyingly unknown future. Why don’t I respond directly to what’s happening—in math, in quantum computing, in AI?

I’d like to think that I am responding, in my way. I’ve observed that, the faster we race toward the Singularity, the more I feel like stepping back and asking myself: what do I actually value in life? How important to me are math and science, as human practices to be passed down to curious children? Would I even want solutions to P versus NP and the other problems, if the price were to destroy those human practices forever? How do I wish to spend whatever time I have remaining?

I can justify this focus partly in a pessimistic way: if we are nearing the end of civilization, or even just of the “mathematical research” part of civilization, then it’s time to get right with God, so to speak. It’s time to settle my accounts with myself, with other people, with the universe.

But there’s also a more optimistic spin. If I continue doing the sorts of things that other people would expect me to do, then AI will soon do those things better than me, in the unlikely event that it doesn’t already. You want to understand the latest developments in quantum computing or complexity theory? Why are you even asking me, when you could ask GPT 5.6 or Claude Fable? If there’s anything I can still offer the world that AI can’t, I increasingly feel like it won’t involve responding to day-to-day events, but will instead draw on 45 years’ worth of memories and disappointments and ruminations.

By Scott

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits in the proof. In particular, our proof does not involve any PCP compositions; notably, it does not invoke the NP-completeness of any fixed problem, such as SAT or 3-coloring, in the construction of the verifier. The main innovation in our work is a clean, coding theoretic, way to encode univariate polynomials that allows us to implement ``low-degree testing'' using just a constant number of bits of queries. Insights from recent attempts to simplify the PCP proof by the authors (STOC 2026) and Goldreich (ECCC 2025) allow us to observe that low-degree was the key bottleneck in converting previous algebraic constructions of the PCP verifier into a constant query PCP. Thus, by overcoming this bottleneck, we get the full PCP verifier using elementary and self-contained steps. As concrete support for the claimed simplicity, we include the full pseudocode of the PCP verifier, assuming finite field arithmetic, and a full description of the completeness (aka ``honest'') prover, assuming multivariate polynomial arithmetic including interpolation and evaluation, that fit in about a page each.

Given two symbolic matrices $X$ and $Y$ of dimensions $m\times n$ and $n\times m$, respectively, the *rank principle* states that when $m = n+1$ and $A$ is a scalar matrix of rank $n+1$, the equation $XY = A$ is unsatisfiable. When $m$ is arbitrarily larger than $n$ and $A$ has rank exceeding $n$, we obtain the *weak rank principle*. We study this principle as an algebraic generalisation of the weak pigeonhole principle (WPHP), asserting that $m$ pigeons cannot be injected into $n$ holes. As a strengthening of WPHP, it admits proof complexity lower bounds in settings where none are known for WPHP, while still supporting analogous applications. Using new generalised random restrictions applied to the weak rank principle, which may be of independent interest, we resolve several open problems in proof complexity: we construct proof complexity generators for Polynomial Calculus Resolution over the two-element field (PCR$_{\mathbb{F}_2}$), new generators for Sherali--Adams (SA), and hardness results for circuit lower bound statements against PCR$_{\mathbb{F}_2}$. GENERATORS FOR PCR$_{\mathbb{F}_2}$: We prove exponential size lower bounds for several encodings---both algebraic and CNF---of the weak rank principle in PCR over ${\mathbb{F}_2}$, where no such bounds are known for the WPHP in the regime with arbitrarily many pigeons. In particular, we obtain $2^{\Omega(n)}$ size lower bounds for both algebraic and standard CNF encodings, including the *bamboo-tree encoding*, which is the most relevant for applications and corresponds to a circuit encoding, as considered by Alekhnovich, Ben-Sasson, Razborov, and Wigderson (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015). Our bounds hold for every matrix $A$ in $XY = A$, implying that the rank principle forms a proof complexity generator with nearly quadratic stretch. Using a standard iteration technique we amplify the stretch to $2^{n^{\Omega(1)}}$, thereby obtaining a function generator. This resolves the open problem posed by Alekhnovich et al. (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015) concerning the construction of proof complexity generators with good stretch for PCR$_{\mathbb{F}_2}$. GENERATORS FOR SHERALI-ADAMS: Since in SA even the strong pigeonhole principle is easy, we develop a new size lower-bound technique showing that the weak rank principle, encoded as a bamboo-tree CNF, serves as a proof complexity generator for SA. Our method introduces a new relaxed notion of degree and a corresponding pseudoexpectation tailored specifically to the rank principle (and incompatible with the pigeonhole principle). CIRCUIT LOWER BOUND FORMULAS: We show that PCR$_{\mathbb{F}_2}$ does not admit short proofs of lower-bound statements against Boolean circuits, nor against weak models of algebraic circuits. This settles the open problem raised by Razborov (Ann. Math., 2015) concerning the provability of such lower bounds in PCR$_{\mathbb{F}_2}$. STRENGTH OF THE WEAK RANK PRINCIPLE: Finally, we show that the weak rank principle is *necessary* for proving NC$^2$ circuit lower bounds and, for odd primes $p$, *sufficient* within the theory corresponding to AC$^{0}[p]$ for deriving AC$^{0}[p]$ lower bounds.

I’ve started and stopped four posts this week and couldn’t figure out why I was stuck. Finally this morning, in a delightful retelling of an Alan Moore comic, Henry Farrell struck the nail in my head.

Henry describes Moore’s society where a supergenius benevolent dictator named Abelard Snazz designs giant police robots to fight crime. The robots get too zealous and start bothering ordinary citizens. So Snazz deploys criminal robots to keep the police busy. The cycle continues until people are forced to flee the planet.

Henry, always keen to show us what sci-fi tells us about our lived experience, describes how this automation is playing out in our lives, with people heading to chatbots to deal with bureaucracies, and governments planning new AI systems to deal with the onslaught of ChatGPT protestations. We know where this ends. And this week has seen way too many stories of this abandonment of agency and succumbing to AI.

I drafted a blog about our annual complain-fest about the academic wreckage that is the NeurIPS conference. Everyone is taking to social media to complain that people are shirking their reviewing responsibilities. They scoff at new limits of 25 papers per author per conference. They lament that AI papers and referee reports are now better than those submitted by people. They say no one reads any of these papers. And yet, everyone continues to submit papers, review papers, and be area chairs.

It is completely unclear what everyone wants from this process anymore. With every purported fix, the process gets more onerous, and the problems only get worse. More papers are submitted, more hair is torn out in frustration. Every day I’m reminded of what Kevin Baker wrote about this acceleration of publishing and perishing: “Systems can persist in dysfunction indefinitely, and absurdity is not self-correcting.” But Kevin’s next sentence is more damning. “Whether the acceleration produces collapse or adaptation or simply more of the same is not a question about the technology, and it won’t be answered by debates about capabilities.“

I drafted a blog post about open letters from employees of tech companies. They warn of all of the potential harms of the technology they are building. They beg for the government to regulate them. They decry their helplessness as they collect their 7-figure remuneration. Apparently they can’t see a path to do anything themselves.

These people want us to trust them, but then they keep admitting they are committing crimes. They write about their software as a person, trying to deflect from their own incompetence in security standards. They demand strict testing of open models while bragging about their laughably sloppy practices. They demand that the government come in and regulate them, because they can’t get out of their own way.

Even in esoteric places, we see a deferral to the AI. The lore laundering machines are now good enough to prove actual theorems, finding the key clever steps needed to take the existing literature and close “major” open problems.1 There’s a lot to say about what’s happening here. It’s still lore laundering, and mathematicians are rightfully angry that the models remain horrible at proper attribution. But the new models are generating much more clever stitches to glue the proofs together.

OpenAI has been running a distributed denial-of-service attack on unsolved math problems, and their internal tooling has finally been able to solve some very hard ones. Only three people in the world know what a non-sofic group is and why it’s important,2 but the new OpenAI Astra model has managed to construct one. The mathematical progress has created an arms race in mathematics, where people are telling mathematicians that they need to do all their work with ChatGPT now or be left behind. Or even worse, that there’s no need for mathematicians anymore. What this means for mathematics and applied mathematics more generally remains to be seen. But I guarantee you that people are going to quickly tire of theory papers on arXiv that are exclusively transcripts of professors having conversations with ChatGPT.

As Henry writes, all of these cases are arms races. As with all arms races, the momentum can feel insurmountable. I’m surrounded by people throwing up their hands as if they have no agency. But sometimes it’s important to step back for a second and see that where we’re heading is not inevitable. We do have choices here.

Researchers don’t have to send papers by the tens of thousands to conferences where no one reads anything. They can collectively design better systems to generate, evaluate, and share knowledge. Employees can use the power of their labor to steer their companies, rather than pleading for someone else to step in. Mathematicians can continue to think, understand, and teach. We all have the power to do something else.

Subscribe now

By Ben Recht

Authors: Hangyu liu

We obtain exponential upper bounds on approximate generalized weight and generalized sparsity in terms of the deepest transition depth D(F), and show that these bounds are optimal up to constant factors in the exponent. We further characterize approximate generalized sparsity, establish a dual lower-bound framework based on exponential restriction profiles, and derive a Paturi-type characterization relating approximate generalized weight to quantum query complexity.

Authors: Tom Altman

We introduce a hierarchy consisting of stage machines, stage domains, and stage languages generated by semantic operators. The central result is a Predictor Impossibility Theorem (PITT), which shows that no effective predictor family can uniformly determine all stage languages of our hierarchy. The proof makes use of a pseudo-complement construction to obtain a language that yields a contradiction with every language in P. We then define an aggregate language MIS and establish a formal Slice Theorem connecting aggregate inputs to individual stage languages. This provides a rigorous Bridge Theorem from polynomial-time decidability of MIS to the existence of an effective predictor family. By utilizing succinct representations, the aggregate language is shown to be undecidable in deterministic polynomial time. Under the aggregate growth condition defining valid aggregate objects, MIS is shown to belong to NP. Combining these two results yields our main theorem: MIS in NP setminus P. The paper is organized so that PITT stands independently as a theoretic result, while the complexity-theoretic consequences are derived from the aggregate-language framework. The method does not relativize, algebrize, or naturalize.

Authors: Mursalin Habib

We show that computing a median under the Ulam distance is NP-hard even when the input consists of exactly four permutations. Previously, NP-hardness was known only for an unbounded number of input permutations (Fischer et al., ESA '25). Our result is tight, since an Ulam median of three permutations can be computed in polynomial time (Chakraborty--Das--Krauthgamer, SODA '21).

Authors: Melissa Antonelli, Eduardo Skapinakis

This paper presents a high-level report on an ongoing project aiming to leverage implicit approaches based on discrete ordinary differential equations (ODEs) to study multiple complexity classes, even beyond small circuit and polynomial-time classes. Stimulated by recent ODE-based characterizations of polynomial-time functions (FP) and classes over the reals, the research project outlined here pushes this investigation further into counting and alternation. Specifically, we present a uniform framework, built upon a single base algebra and a unified family of schemas, where complexity levels, such as those of the polynomial and counting hierarchies, are captured simply by the nesting depth of ODE operators. Crucially, our approach starts from a base class much weaker than FP, thus strengthening existing recursion-theoretic treatments and establishing a natural connection to descriptive complexity. Moreover, by isolating three elementary schemas, our framework makes the computational content of linearity restrictions completely transparent while extending ODE-based implicit complexity to previously unaddressed counting classes, such as oplusP. More generally, this work establishes a clear bridge between differentiation and counting, offering a fresh perspective on the relationships between different complexity classes, which remains the object of ongoing and future research.

Authors: Randal Tuggle, Jack Snoeyink

We seek to disentangle the hardness of finding a Hamiltonian path or cycle from the hardness of finding a non-crossing path or cycle by giving a direct reduction from 3-SAT to the non-crossing Hamiltonian path and cycle problems on non-planar graphs. Prior hardness proofs proceed by reduction to planar graphs, where every path is automatically non-crossing; this conflates the two sources of difficulty and leaves unclear why forbidding crossings on the path alone makes the problem hard. Our reduction places the difficulty squarely in the non-crossing constraint, avoids planar gadget constructions, and yields a more transparent proof that may be easier to extend to related problems.

Authors: Elizaveta Pribiytkova, Dmitry Gribanov

In this paper, we build upon the analysis initiated by Gennadiy Averkov \& Matthias Schymura (2022) and establish that the number of distinct columns of a $Δ$-modular matrix $A \in \mathbb{Z}^{m \times n}$ of rank $m$ is $O(m^3 Δ)$, thereby improving the earlier bound of $O(m^4 Δ)$. Recall that a matrix is called $Δ$-modular if the maximum absolute value of every $m \times m$ minor is exactly $Δ$.

Authors: Kazuhiro Kawamura, Sushovan Majhi, Atish Mitra

The Intersection Euler Characteristic Profile (Intersection ECP) of $k$ colored point clouds $X_1, \ldots, X_k \subset \mathbb{R}^d$ is the Euler characteristic $χ(\bigcap_{i=1}^k \mathcal{U}(X_i; t_i))$ of the overlap of their ball unions---an integer-valued, multiparameter invariant of their topological interaction across scales. Its organizing framework is the Euler calculus on constructible functions: the profile is equally the Euler integral $\int \prod_{i=1}^k \mathbf{1}_{\mathcal{U}(X_i; t_i)} \, dχ$ of the product of the $k$ data-dependent offsets, and this identity---our Intersection Theorem---is a commuting square interchanging geometric intersection and algebraic product. The invariant is rigid-motion invariant, scale-equivariant, and $L^1$-stable, and it is canonical: among pointwise-Euler interaction profiles it is the one forced by separation and normalization, the top floor of a spectrum of descriptors graded by how many clouds meet. For $n$ points a single sorted Alpha-complex sweep computes it in $O(n^{\lceil d/2 \rceil} \log n)$ time with no persistence reduction, worst-case optimal in even dimensions. Where the Euler characteristic cancels, a relative-homology refinement resolves the finer interaction and is stable in the two-parameter interleaving distance. Finally, for increasingly dense samples the profile and its refinement are consistent, recovering the (relative) homology and Euler characteristic of the underlying shapes---in the inverse limit for compact sets, and, under positive reach, persistently and with explicit sample complexity.

Authors: Xuan Chen, Shuangping Li

The low-degree heuristic has become a widely used framework for predicting computational thresholds in average-case planted-versus-null problems. However, a recent sequence of counterexamples shows that low-degree indistinguishability does not, in general, rule out efficient noise-tolerant distinguishers; see Buhai et al. (2025) and Mao (2026). Motivated by these developments, Hsieh et al. (2026) initiated the study of rigorous consequences of the low-degree heuristic. In this work, we continue this program for planted-graph problems. Let $Q_n=G(n,c/n)$, and let $P_n$ be obtained by planting a uniformly random copy of a deterministic graph $Γ_n$ into an independent sample from $Q_n$. In the supercritical regime $c>1$, we show that if $P_n$ is degree-$D_n$ indistinguishable from $Q_n$ and $\operatorname{tw}(Γ_n)=o(D_n/\log n)$, then a noisy version of $P_n$ is asymptotically indistinguishable from $Q_n$. Here $\operatorname{tw}(Γ_n)$ denotes the treewidth of $Γ_n$, a measure of how efficiently the graph can be decomposed into tree-like pieces. In the critical and subcritical regimes $0

Authors: Sina Azizeddin, Evangelos Kipouridis, Nithin Varma

In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the number of violated pairs (edges across different clusters plus non-edges within clusters). In the constrained version of this problem, the goal is to compute a clustering that satisfies additional hard constraints mandating certain pairs to be in the same cluster and certain pairs to be in different clusters. In this work, we identify Constrained Correlation Clustering as a variant of Correlation Clustering for which optimal approximations might be within reach, and make progress towards this front. Constrained Correlation Clustering is APX-Hard, and the optimal approximation factor is known to lie in $(\frac{24}{23},3]$. We significantly tighten this gap, by showing that the optimal approximation factor lies in $[2,\frac{16}{7}-γ)$ for a small constant $γ>0$. Our lower bound of $2$ shows a separation between Correlation Clustering (which admits an $1.485+ε$ approximation) and Constrained Correlation Clustering\footnote{The same hardness result was obtained independently by Cao and Xu~\cite{cao2026clusterdeletionhardapproximate}.}. Our upper bound of $\frac{16}{7}-γ$ uses the Sherali-Adams relaxation and goes beyond straightforward Triangle-Based analysis; more precisely, our algorithm belongs to a natural class of pivoting algorithms for which we prove that a straightforward Triangle-Based analysis cannot prove a better-than-$\frac{16}{7}$ approximation. Finally, as a byproduct of our techniques, we completely resolve the approximability of Cluster Deletion. Cluster Deletion is a well-studied special case of Constrained Correlation Clustering for which a $2$-approximation algorithm is known. We show that this is optimal, as our lower bound holds even for this special case.

Authors: Ainesh Bakshi

Consider the problem of maximizing the number of satisfied constraints of an arbitrary boolean constraint satisfaction problem with arity $k$. We obtain a polynomial time algorithm that achieves a $(k/2^k)$-approximation, improving on the previous best guarantee of $0.626612\; k/2^k$, due to Makarychev and Makarychev (arXiv:1206.3603). Assuming the Unique Games Conjecture, De and Mossel (arXiv:1202.5258) showed that achieving an approximation ratio better than $(k+1)/2^k$ for odd $k$ and $(k+2)/2^k$ for even $k$, is NP-hard. The main technical ingredient is an extension of a recently established Gaussian comparison inequality, used to resolve the Weak Simplex Conjecture in coding theory (arXiv:2607.14087).

Authors: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Let $H\subseteq\{-1,+1\}^X$ be a class of finite VC dimension $d\ge1$. Writing $L$ for the binary risk and $L^*=\min_{h\in H}L(h)$, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size $n$, for every $0<δ\le 1/2$, with probability at least $1-δ$, \[ L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right). \] This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed $L^*$, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

Authors: Anay Mehrotra

A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice, every one of them labeled correctly by the target hypothesis. The learner sees a uniform shuffle of the combined sample and is scored on the original distribution. Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable. Larsen, Pabbaraju, and Shetty, who introduced this model, showed that empirical risk minimization attains expected error $O((d/n)\log(n/d))$ for classes of VC dimension $d$, and that every known optimal learner can be pushed away from the $Θ(d/n)$ rate, optimal for PAC learning. They asked whether the extra logarithm is an artifact of those particular algorithms or an inherent consequence of the lack of exchangeability. We show that this additional cost is inherent beyond VC dimension one. In the worst case over classes of VC dimension $d$ and over known finite insertion budgets, the minimax expected error is $Θ(1/n)$ at $d=1$ and $Θ((d/n)\log(n/d))$ for $d\geq 2$. The same rates hold with Littlestone dimension $d_{\mathrm L}$ in place of $d$, so the clean online-to-batch rate $O(d_{\mathrm L}/n)$ is unattainable as well. Thus, somewhat counterintuitively, adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning. The dimension-one upper bound is achieved by a simple improper learner whose analysis adapts the leave-one-out argument underlying the one-inclusion graph. All of our lower bounds are elementary and come from a single construction: an explicit class and prior on which two target hypothesis, which differ a point of nonnegligible mass, produce the same sample.

Authors: Heng Guo, Xinyuan Zhang

We show that the hard-core partition function admits a fully polynomial-time randomised approximation scheme (FPRAS) on planar graphs when the activity is a sufficiently small constant. In contrast, we show that for any constant $q\ge 4$, approximately counting $q$-colourings in planar graphs is NP-hard. We also give a complete characterisation of when an FPRAS exists for a sufficiently small external field for 2-spin systems on planar graphs. The main ideas of all proofs were found using GPT-5.6 Sol Ultra.

Authors: Andrew Au

Stone Game III admits a standard backward dynamic program using $O(n)$ time and $O(1)$ auxiliary space. The upper bound is immediate, but its optimality raises a deceptively simple question: must a correct algorithm really inspect a linear number of input values? For the original problem, an all-zero instance gives a short indistinguishability proof that every position must be inspected. This argument appears to depend strongly on the possibility of a tie. We show that it does not. Even under the promise that every input has a winner, an adversary can force any deterministic algorithm to make $Ω(n)$ inspections by combining modular move control with indistinguishable input completions. We also extend the argument to positive but unbounded values, obtaining the same linear lower bound without zeros or ties. Together these results establish the asymptotic optimality of the standard $O(n)$-time, $O(1)$-space solution in several increasingly restrictive variants.

Authors: Boyang Chen, Minbo Gao, Xinzhao Wang, Shuo Zhou

We give a query-optimal algorithm for simulating a general $n$-qubit time-dependent Hamiltonian $H(t)$ on $[0,T]$, assuming that $H$ is Lipschitz continuous and $\|H(t)\|\leqα$. In the standard $\mathrm{HAM\mbox{-}T}$ access model, the algorithm approximates the time-ordered propagator $U_H(T)$ to error $\varepsilon$ using $$ O\left( αT+\frac{\log(1/\varepsilon)} {\log(e+\log(1/\varepsilon)/(αT))} \right) $$ $\mathrm{HAM\mbox{-}T}$ queries. This matches the known query lower bound for time-independent Hamiltonians, showing that time dependence incurs no asymptotic query overhead. Our method first constructs a one-query transducer that, given an auxiliary state, implements an approximation to $U_H(T)$ and returns the state unchanged. A weighted combination of circuits that apply the transducer different numbers of times makes the error caused by omitting this state decay factorially, yielding the stated optimal precision dependence. For time-independent Hamiltonians, the same method also gives a query-optimal alternative to qubitization.

Authors: Guy E. Blelloch, Yang Hu, William Kuszmaul, Jingxun Liang, Renfei Zhou

The dynamic dictionary is a fundamental data structure that maintains a set $S\subset [U]$ of size $n$ (we assume $n=U^{1-Θ(1)}$), supporting insertions, deletions and membership queries. Previous works mostly focused on constructing dictionaries that support operations in $O(1)$ time and use space as close to the \emph{information-theoretic bound} of $\log\binom{U}{n}$ bits as possible. In this paper, we study \emph{difference-encoded} dictionaries, which are dictionaries that use space close to the gap entropy $\text{gap}(S):=\sum_{i=2}^{|S|}\left(\lceil\log(x_i-x_{i-1}+1)\rceil+1\right)$ bits to store the set $S=\{x_1<\dots

Authors: Guy E. Blelloch, Yang Hu, William Kuszmaul, Tianxiao Li, Renfei Zhou

We show how to implement a dynamic array $A[1, n]$ with symbols from a fixed alphabet $Σ$, while supporting $O(1)$-time queries and updates, and using a total space of $$ \log \binom{|Σ|}{m} + \left(1 + O\left(\frac{\log \log n}{\log n}\right)\right) \cdot \left(\sum_{σ\in Σ} f_σ\log (n / f_σ)\right) + n / \text{polylog } n $$ bits, where $f_σ$ denotes the frequency of each symbol $σ\in Σ$ and $m$ denotes the number of distinct symbols with non-zero frequencies. This resolves a long-standing open question as to whether one can achieve space bounds close to that of arithmetic coding, while supporting $O(1)$-time operations, whenever the entropy is at least $n/\text{polylog } n$. We also prove a nearly matching space lower bound: up to a factor of $O(\log \log n)$, the entropy-dependent multiplicative overhead of our construction is optimal among $O(1)$-time solutions when $|Σ|=O(\sqrt n)$ and the entropy $\sum_{σ\in Σ} f_σ\log (n / f_σ)$ lies between $n/\log^{O(1)}n$ and $(1/100)n\log n$. Finally, we present several applications of our results, resolving two open problems having to do with space-efficient dictionaries and filters.

Authors: Robert Scheffler, Philipp Wolf Schleicher

Beisegel et al. [SWAT 2024] introduced the concept of simultaneous $\mathcal{C}$-numbers which associate a graph class $\mathcal{C}$ with a graph parameter. Given a graph $G$, the simultaneous $\mathcal{C}$-number is the smallest number $d$ for which there is a graph $H \in \mathcal{C}$ and a function $L : V(G) \to \mathcal{P}(\{1,\dots,d\})$ such that two vertices $u$ and $v$ are adjacent in $G$ if and only if they are adjacent in $H$ and their sets $L(u)$ and $L(v)$ are not disjoint. We study the relation of these simultaneous $\mathcal{C}$-numbers to other graph parameters. In particular, we investigate which parameters fulfill the following property: Parameter $p$ is bounded on class $\mathcal{C}$ if and only if $p$ is bounded on the class of graphs of simultaneous $\mathcal{C}$-number $d$ for any fixed $d$. We show that many well-known graph parameters have this property. Examples are cliquewidth, twin-width, mim-width, tree independence number, thinness as well as boxicity. We furthermore present some parameters, including modular-width and tree-length, that do no have this property. We also study when a parameter forms an upper bound on a simultaneous $\mathcal{C}$-number. We characterize those graph classes $\mathcal{C}$ for which the parameters treewidth, pathwidth, bandwidth, and treedepth upper bound the simultaneous $\mathcal{C}$-number. Furthermore, we present sufficient conditions on a class $\mathcal{C}$, such that $\mathcal{P}$-modular cardinality upper bounds the simultaneous $\mathcal{C}$-number, where $\mathcal{P}$ is replaced by the complete graphs, the edgeless graphs, cographs, or the class $\mathcal{C}$ itself. On the contrary, we show that modular width never forms an upper bound on a non-trivial simultaneous $\mathcal{C}$-number. Finally, we present some general algorithmic results on the clique problem and computation of simultaneous $\mathcal{C}$-numbers.

Authors: Frédéric Meunier, Shmuel Onn

The degree sequence optimization problem is to find a subgraph of a given graph which maximizes the sum over all vertices of a given function evaluated at the subgraph degree of that vertex. Here we study this problem and its complexity for quadratic functions. In particular, we introduce the critical roots of a graph, and show they define intervals over which the optimal value of the problem, as the quadratic root varies, is convex piecewise affine.

Authors: Nikhil Bansal, Yuze Xu

We consider the A/E-design problem under partition constraints: Given vectors $v_1,\ldots,v_N\in \R^d$ and a partition matroid on $[N]$, find a base $S$ of the matroid that minimizes $\tr(M(S)^{-1})$ or $λ_{\max}(M(S)^{-1})$ where $M(S)=\sum_{i \in S} v_i v_i^\top$. In contrast to D-design, where good estimation and approximation guarantees are known as a function of $d$, we show that no reasonable approximation exists for A/E-design. This answers a question of Brown, Laddha and Singh. The proof is based on an elementary reduction from three-dimensional matching.

Authors: Zonglin Han, Yichen Chen, Jiawen Jiang, Tongan Shi, Kristian A. Stevens

When a student must learn concepts connected by prerequisite dependencies, when does the order of instruction matter, and what does it cost to find the best one? We study instructional sequencing as a stochastic shortest-path problem in which attempting a concept succeeds with a state-dependent probability and failure leaves the learner state unchanged. We first prove that this stochasticity can be eliminated exactly: the problem collapses to a deterministic shortest-path problem on the lattice of prerequisite order ideals, preserving optimal values and actions. The collapse removes stochastic complexity but not combinatorial complexity: optimal sequencing remains NP-hard -- via reduction from feedback arc set in tournaments -- even with no prerequisite edges, unit costs, uniform binary nonnegative transfer, and success probabilities at least $1/2$. Hardness is not uniform: when realizable transfer preferences remain jointly acyclic with the prerequisites, any topological order of the residual joint graph is optimal, and fixed prerequisite width yields polynomial-time exact dynamic programming. A computable diagnostic, $mΔ$, bounds the value of sequencing before optimization. On 70,893 interactions from an introductory CS course, the diagnostic certifies a doubly easy regime -- little value to optimize and little space to search -- while constructed transfer instances realize the challenging regime, where myopic sequencing suffers large regret yet exact A* with a consistent heuristic expands only linearly many states on that family.

Authors: Mark Bedaywi, Scott Emmons, Nika Haghtalab, Stuart Russell

Our results show that the existence of a short high-utility protocol already suffices for efficient communication. In particular, in a game with $n$ possible observations and $m$ actions: (1) For any achievable target utility $α$, we give an algorithm with $\mathrm{poly}(n, m, 1/ε)$ runtime that designs a protocol achieving utility at least $α-ε$ using only $2^{\mathcal O(CC_α(G))}/ε^2$ bits of communication. Here, $CC_α(G)$ is the minimum number of bits used by any protocol, even a computationally inefficient one, to achieve utility $α$. (2) We prove that this exponential dependence on $CC_α(G)$ is tight up to a constant. That is, unless $\mathrm P=\mathrm{NP}$, no polynomial-time algorithm can in general find optimal protocols using fewer than $2^{CC_α(G) -2}$ bits. We note that our results strictly weaken the assumptions required by prior work in the multi-agent information aggregation literature, filling a gap that had remained elusive even for games with constant $CC_α(G)$. In particular, prior guarantees for agreement-based information aggregation rely on structural assumptions such as informational substitutes or weak learnability. We show that these assumptions already imply $CC_α(G) = O(1)$ and are therefore more restrictive conditions than required by our protocol to succeed. On a technical level, our results involve a novel strengthening of the Frieze-Kannan weak regularity lemma and yield the following powerful polynomial-time transformation tool: for every communication game $G$, it constructs a game $\hat G$ that is a coarsening of the agents' observation spaces into constant-size partitions, such that $G$ and $\hat G$ are indistinguishable with respect to every short communication protocol. This coarsening theorem is the engine behind our algorithm and may be of independent interest.

Everything changes but everything stays the same, and the 2026 internet is no exception. Today I recommend two websites because I am a happy customer of both.

Web Search

Most people agree that Google is worse now than it was a decade ago. Some people blame SEO, some blame LLMs. I think Ed Zitron is right when he describes the degradation is intentional on Google's part: enshittification at work.

Still, search is now a fundamental part of how we interact with the web and we want something that works. One remedy I have heard is to use LLMs as a search engine. This is highly dubious practice in my view. Even the best models would sooner lie to your face than accurately describe the contents a simple web page.

My recommendation is a search engine called Kagi. It is truly great. As good as Google was back in the day I find that Kagi consistently yields high quality and authorative sources while returning a minimum of spam and AI slop. I started using this product already back in 2023 and I recommend it to everyone.

One feature worth pointing out: Kagi search is a paid product. I pay 5 dollars plus tax for up to 300 searches per month (which is more than enough). Because the user pays, the user is the customer. This is unlike Google, DuckDuckGo, or most other search engines, where the user is the product. You can feel the difference in how you are treated. Six dollars is a small price to pay for a functioning web.

Syndication

Second recommendation is an oldy but goldy: get yourself an RSS reader. It is astounding the number of people I talk to (young or old) who do not use one of these.

RSS is a web protocol thingy, and almost every website participates. You can load special RSS urls into a software called an RSS reader, and the software will put all the new updates from all your subscribed websites into a chronological feed.

RSS is an amazing technology. You can follow your favorite newspaper, get your daily xkcd comic, and follow the latest papers in your ArXiv categories all in the same software. Every time you find a cool website, you can easily subscribe. That way you slowly build your own personal chronological feed of cool things and stay up-to-date with all you care about.

There are a lot of good RSS readers out there, either local on your device or as a web app. I like Inoreader, they have a comfortable free tier. Do not worry about vendor lock-in: every RSS reader I know allows to export your list of feeds to a .ompl file which you can use to move to a different product.

I recommend you install a browser add-on to more easily find the RSS feed for a given webpage. On Firefox a good one is Want My RSS, which puts a little logo in the address bar when a feed is available. On Chrome I will not recommend anything, I don't like them because they are destroying their add-on ecosystem as we speak. But perhaps you can find something there too.

If you are a colleague in theoretical computer science, subscribe to theory.report to stay up-to-date with all the bloggers in the community. On arXiv they have separate feeds per category and subject class you can subscribe to. RSS is by far the easiest way to see all new papers coming out. If you are in optimization, note that Optimization Online also has a feed.

ICM2026 in Philadelphia was, for me, a celebration of mathematics and people. I met many friends and colleagues, as well as several mathematical ideas and results. The nature of these meetings is that they are abrupt and random. (Some people don’t like it, but I do.) For me, mathematics and personal stories are often entangled. I tried to attend most of the plenary lectures and most of the combinatorics and computer science sectional lectures. Of course, given the vast wealth of mathematics (and my ignorance in most areas), this was also a humbling experience.

Are celebrations appropriate for me during these rather difficult times in my country (and some other places)? I tried to address this question in this post and this one.

Lior Silberman wrote nicely over Facebook his live experience from the congress. Lior’s scholarly understanding of most areas of mathematics is, of course, quite an advantage.

I enjoyed Annalisa Buffa’s lecture on New Challenges in Numerical Approximation of Partial Differential Equations.

A short stream of associations starting with quasi crystals interlaced with people I met.

Back in New York, Priya Subramanian told me about her interdisciplinary work on quasicrystals. She mentioned a physicist colleague, Ron Lifshitz from Tel Aviv University, whom I know well. In fact, I knew Ron’s parents, Hava Lifshitz and Assa Lifshitz, both noted chemists from HUJI. Assa was the head of the professors’ union during the time I also served on the union, and we had interesting negotiations for several years with the HUJI administration headed by my friend Menachem Magidor (then HUJI president), and also with the Finance Ministry.

A few days after meeting Priya, I met a hero of quasicrystals (and other areas), Jeff Lagarias, in Philadelphia. I have known Jeff since the 80s, and he pronounces my name “jill” (which I like coming from him, as well as from Gilles Pisier). Quasicrystals are closely related to the work of Dan Shechtman, a famous Israeli chemist, as well as to Penrose tilings and works on tilings and symbolic dynamics; the monumental work (master’s thesis!) of Shahar Mozes comes to mind.

I also met again Matt Foreman, whose research uniquely combines ergodic theory and set theory, and who is a close colleague of both Magidor and Benjy Weiss. I promised Matt to test my most outrageous conjecture about a proposed number-theoretic undecidability barrier on him.

Officers of the IMU and state delegates for the GA watch the football World Cup Final.

Convex polytopes with Günter Ziegler

On the train from NYC to Philly (If I may; I feel a little awkward to use the nickname “Philly” for Philadelphia), I spent a quality hour discussing the theory of convex polytopes with Günter Ziegler (who is now mainly occupied with being a university president). At the reception that evening, we met Frank Morgan (whom we both met at MIT in the 80s)—here are the three of us.

With Gunter Ziegler, Frank Morgan, and Imran Anwar. A few years ago, Imran hosted me in the John Conway Spirited Seminar series.

Meeting people for the first time

This time in Philadelphia, I met Maria Klawe and Nick Pippenger for the first time. (In 1990, I visited the CS group they founded at IBM San Jose for a year, but it was after they had already left). I met Robion Kirby for the first time, just hours after his work was prominently featured in Ciprian Manolescu’s lecture on knots and 4-manifolds.

I also met Erdal Arıkan, Fabio Martinelli, Nilma Nigam, David Kalaj, Yasuyuki Kawahigashi, Imran Anwar, Charles Bordenave, Ramon van Handel, and quite a few others for the first time. Among them, David Kalaj is probably my nearest lexicographic neighbor among all mathematicians (whose name is not identical to mine). Of course, I also met many old friends.

The Abacus Medal goes to Shayan Oveis Gharan

Shayan Oveis Gharan gave a beautiful Abacus Medal Lecture that, together with the invited lectures of Nima Anari and Cynthia Vinzant, added up to a mini-course on a fascinating new area of theoretical computer science and discrete mathematics with many connections (including to HDX). I hope to write about these three lectures in a future post. Heartfelt congratulations to Shayan and to all the prize winners.

Math for AI; AI for math, and the future of mathematics.

I missed the special panels on “Math for AI” and “AI for Math,” as well as most of the general audience lectures devoted to the AI revolution. (I did attend Terry Tao’s lecture, and I will try to catch up with the recordings). The ways in which AI will change mathematics was a large elephant in the room at the congress.*

Booths, Blackboards, Art, and AMR

With George Andrews

There was a large space for booths hosted by several organizations, alongside blackboards and mathematical art. One booth belonged to The Association for Mathematical Research (AMR). AMR is a nice international mathematical association that hosts a variety of activities and publishes several open-access journals.

When it was established 4–5 years ago, there were concerns that AMR was:

• Anti-AMS
• Anti-diversity
• Anti-double-blind refereeing
• Implicitly representative of right-wing politics

At the time, I did not join the AMR. However, a couple of years ago—after seeing that AMR runs nice activities that do not reflect those early fears and concerns—I did join. (Membership is free; becoming a member is mainly an act of support for AMR’s activities, as I am not aware of any special benefits for members.). Among the AMR founders are my long-time friends Abby Thompson and Joel Hass. I had interesting conversations with Abby about diversity, the situation at Davis since the October 7 war, and tolerance (or rather, the sad intolerance) toward a large variety of political views. See this post for a beautiful coloring conjecture by Abby Thompson.

Women at the ICM

When it comes to gender diversity, judging from the ICM participants and speakers, we are witnessing a positive change over the last five decades. While the main credit for that goes to women researchers themselves, what also made a big difference in the combinatorics community is the fact that extremely good teachers—like my Ph.D. supervisor Micha Perles, as well as Richard Stanley, Adriano Garsia, Herb Wilf, and others—were  welcoming to female students.

Erdal Arıkan’s talk

Erdal Arıkan gave a beautiful talk about polar codes. (See this 2010 post about polar codes which is among the greatest hits of my blog.)

Sarnak on Serre

Peter Sarnak gave a very enjoyable lecture about “Maestro Jean-Pierre Serre”.

Morning at the museum

I devoted one morning to the exquisite Philadelphia Museum of Art. 

Four talks related to additive combinatorics

I already wrote about Meka’s talk on the new bounds for Roth’s theorem. Tamar Ziegler gave a tour de force plenary talk about the Structure of Sets with an Unexpected Number of Arithmetic Patterns. Sara Peluse described some breakthrough results on the polynomial Szemerédi theorem, and Dor Minzer gave a talk on his work regarding 3-term arithmetic progressions with restricted gaps.

Tamar Ziegler’s lecture was a tour de force.

Many more talks related to combinatorics and computer science — stay tuned!

I plan to write separately about several talks on probabilistic combinatorics, extremal combinatorics, Ramsey theory, algebraic combinatorics, and various topics in theoretical computer science (including two talks on algorithmic game theory and a talk about quantum computation).

I am not sure what the quality of the recorded sectional lectures will be. (In Rio 2018, the recordings were of good quality, but unlike Rio, the recording this time is based on unmanned equipment.)

 

Rob Morris gave a great plenary talk on recent advances in Ramsey theory

__

*I usually rely on AI tools for editing. However, I decided to keep the reference to “a large elephant in the room” rather than the AI recommended edit: “a proverbial elephant in the room”.

By Gil Kalai

Authors: Anne Pham, Matthew Ferland

Slime Trail is a two-player combinatorial game in which the players alternately move a shared token to an adjacent vertex, permanently removing each vertex the token leaves, while attempting to reach a goal node. Ferland and Burke (2017) proved that Slime Trail is PSPACE-complete on arbitrary planar graphs and asked whether the same holds for the grid version actually used in play. We resolve this open problem by proving that Cardinal Grid Slime Trail, that is, Slime Trail on a square grid with four-directional movement, is PSPACE-complete. We adapt their QBF reduction to the grid setting, designing grid-compatible gadgets that respect the degree-4 bound and the parity constraints of the integer lattice. We further show the construction extends, under a 45-degree rotation, to the eight-directional variant.

Authors: Xiaoyu Li, Andi Han, Dai Shi, Jiaojiao Jiang, Junbin Gao

Generation in the limit guarantees eventual generation for every countable collection of infinite languages in the model of Kleinberg and Mullainathan [KM24], while closure dimension characterizes stronger information-theoretic guarantees [RLT25]. Neither restricts per-output computation. The cumulative-mistake objective in mistake-bounded generation makes finite failure prefixes quantitative [KPR26], and a per-output query budget exposes their computational source. Polynomial-time algorithms are known for parities, conjunctions, and monotone functions with polynomially many maxterms [JKO26]. We ask whether information-theoretic ease can coexist with bounded-access computational hardness. Relative to a random oracle $H$, we answer yes by constructing a countable collection $C^\star$ of infinite languages with closure dimension zero. Almost surely on the same $H$, an unbounded generator makes zero mistakes on every target and every complete distinct enumeration. Yet, writing $λ$ for the target-seed length, every fixed uniform generator $G$ with polynomially many oracle queries in $λ$ and the output index $i$ has a constant $c_G>0$ such that, for every sufficiently large $λ$, some target incurs more than $2^{c_Gλ}$ expected mistakes within its first $2(\lceil 2^{c_Gλ}\rceil+1)$ canonical outputs. Infinite accidental agreement enables exhaustive search; sparse queries hide fresh target values. Thus, in the random-oracle model, zero-mistake information-theoretic generation coexists with a generator-dependent exponential lower bound on worst-case expected mistakes under polynomial-query access.

Authors: Kirill Osipov

We introduce bounded step recursion and a three-parameter hierarchy refining the Grzegorczyk hierarchy. For a strictly increasing function $\varphi:\mathbb N\to\mathbb N$ with $\varphi(x)\ge x+1$, its generalized inverse $$ρ_\varphi(y)=\min\{z:\varphi(z)\ge y\}$$ replaces the ordinary predecessor and generates the descent schedule $y,ρ_\varphi(y),ρ_\varphi^{[2]}(y),\ldots,0$. From a Grzegorczyk basis $B_m$, composition, and bounded step recursion with step $g_n^{[l]}$, we define classes $H^m_{n,l}$, where $m$ measures the initial-function strength, $n$ selects a growth scale, and $l$ fixes the stride through its canonical layers. For all $n,n'\ge2$, we obtain an exact criterion for $H^a_{n,l}\subseteq H^b_{n',l'}$. Below horizontal collapse, fixed strides are ordered by reverse divisibility: inclusion at equal row is governed by $l'\mid l$, not by the numerical order of $l$ and $l'$. All fixed strides collapse from initial basis $m=n$, and the common class equals the ordinary bounded-recursion class $E^m$ exactly from $m=n+1$. Positive inclusions use exact-depth simulations; separations use a direct piecewise-monotone trace theorem and a canonical-zone invariant for selected dependency chains. The doubling row $g_1(x)=2x+1$ is exceptional at low bases. We prove $H^m_{1,l}=E^m$ for all $m\ge3$, construct the first vertical bridge at basis $2$, and show that every fixed-arity function in $H^2_{1,l}$ is binary polynomial-time computable, with $H^2_{1,l}\subsetneq FP$. Equality $H^2_{1,l}=E^2$ would imply $P=NP$.

Authors: Tayfun Pay

We study several additional properties of parity based bit-counting complexity classes ${\bf B_{|0| \oplus}P}$ and ${\bf B_{|1| \oplus}P}$. We first prove that ${\bf MNS}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}={\bf P}^{{\bf B_{|0|\oplus}P}}$ and since ${\bf C_=P}={\bf ES}={\bf MNS}$ is already known, we establish that ${\bf C_=P}={\bf ES}={\bf MNS}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}={\bf P}^{{\bf B_{|0|\oplus}P}}$. We then prove that ${\bf PP}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}$ and ${\bf PP}\subseteq{\bf P}^{{\bf B_{|0|\oplus}P}}$, which consequently yields ${\bf P}^{\bf PP}={\bf P}^{\bf B_{|0|\oplus}P}={\bf P}^{\bf B_{|1|\oplus}P}$. We then demonstrate that the same method can be used to prove ${\bf \# P}\subseteq{\bf FP}^{{\bf B_{|1|\oplus}P}}$ and ${\bf \# P}\subseteq{\bf FP}^{{\bf B_{|0|\oplus}P}}$. We also show that the parity based bit-counting hierarchies contain ${\bf CH}$.

Authors: Daiki Suruga

This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation $f$ and any error tolerance $\varepsilon \in [0,1]$, we prove \[ \lim_{n \to \infty} \frac{\overline{R}_\varepsilon(f^n)}{n} = (1 - \varepsilon) \overline{R}_0(f). \] Thus the amortization converts bounded-error into zero error with the exact multiplicative factor $1-\varepsilon$. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function $\operatorname{OR}_n \circ f$, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.

Authors: Daiki Suruga

The direct sum problem in computational complexity asks whether solving $n$ independent instances of a computational task inherently requires $n$ times the resources needed to solve a single instance. In this paper, we resolve a central form of the direct sum conjecture in randomized communication complexity. Specifically, we prove that the "amortized expected randomized communication complexity" of any function is exactly equal to its "zero-error information complexity"---a measure of the precise amount of information the communicating parties must reveal about their inputs to compute the function without error. This result also provides a tight characterization of the amortized "worst-case" randomized communication complexity up to a constant factor. To achieve our exact characterization, we introduce a new single-instance protocol embedding equipped with a prefix-verification mechanism to accurately localize global errors. Furthermore, we apply our new structural theorems to the fundamental Set-Disjointness problem. Our resulting exact asymptotic bounds for Set-Disjointness successfully refute a conjecture in DFHL18 regarding its scaling behavior.

Authors: Sándor Kisfaludi-Bak, Geert van Wordragen

We consider spanners for point sets lying in the hyperbolic plane or on a closed hyperbolic surface with the restriction that spanner edges are not allowed to cross. This is a natural generalization of non-crossing Euclidean spanners. Thus, the resulting spanner graphs are embedded in the hyperbolic plane or on the hyperbolic surface. As our main contribution, we show that there are sparse $(1+\varepsilon)$-spanners for these problems when we are allowed to use Steiner points: - on the hyperbolic plane we get a non-crossing Steiner $(1+\varepsilon)$-spanner with $\mathcal{O}(n / \varepsilon^2)$ edges, - on hyperbolic surfaces of genus $g$ we get a Steiner $(1+\varepsilon)$-spanner with $\mathcal{O}(n / \varepsilon^{3/2} + g/\varepsilon^2)$ non-crossing edges, or with $\mathcal{O}(n / \sqrt{\varepsilon} + g/\varepsilon)$ edges that are allowed to cross. In particular, our spanners on surfaces have sparsity with linear dependence on $g$, rather than the easier-to-attain exponential dependence, and the terms $n/\varepsilon^{3/2}$ and $n/\sqrt{\varepsilon}$ match the current best Euclidean results for plane and crossing Steiner spanners, respectively. As a corollary of our non-crossing spanner and techniques from the existing literature on light spanners and minor-free TSP, we get an EPTAS for TSP on hyperbolic surfaces. Our surface constructions rely on the thick-thin decomposition, a standard tool for studying hyperbolic surfaces. For convex hyperbolic polygons, we introduce an analogous neck decomposition. We give algorithms that compute the thick-thin decomposition of a genus-$g$ surface in $\mathcal{O}(g^4\log g)$ time and the neck decomposition of an $n$-vertex polygon in $\mathcal{O}(n)$ time.

Authors: Yuyang Zhang, Weihan Xu, Xuehai Zhou, Shucheng Cao, Qihuang Zhang

The quantitative analysis of 3D neuronal morphologies requires capturing both graph topology and spatial geometry. Current message-passing Graph Neural Networks (GNNs) are bounded by the 1-Weisfeiler-Lehman (1-WL) test, limiting their ability to capture cycles induced by spatial proximities. To address this, we propose a training-free geometric prior based on tropical algebraic geometry. We apply the recently established tropical Abel-Jacobi transform and polarization distances to machine learning on tree-structured data. We introduce a structural transformation pipeline, comprising cycle space augmentation and quotient space construction, to convert spatial trees into cyclic metric graphs suitable for embedding into the Tropical Jacobian. Computing exact tropical polarization distances requires solving the NP-Hard Closest Vector Problem (CVP) on integer lattices. Instead of relying on explicit approximations with quantization errors (e.g., Babai's rounding), we adopt a continuous relaxation on the universal cover of the Albanese torus. We show that the discrete Arakelov-Green measure, computed in closed form via the graph Laplacian's generalized inverse, decomposes exactly into the intrinsic path metric minus the unquantized polarization distance on this cover, avoiding integer lattice searches. This metric yields two descriptors: eigenvectors provide node-level structural coordinates, and the permutation-invariant eigenvalue spectrum provides a graph-level signature. On the BREC benchmark, the eigenvector formulation demonstrates expressivity beyond the 1-WL limit. On 3D morphology datasets (ACT-4, JML-4, BIL-6), the spectrum seamlessly integrates into standard architectures (VAEs, GNNs, Tree-LSTMs) without additional trainable parameters, outperforming explicit lattice approximations and improving classification accuracy over existing spatial models.

Authors: Sterling Ebel, Chris Kapulkin, Nathan Kershaw

We develop a new algorithm for computing (persistent) discrete homology of graphs using reduction to zero differentials and active enumeration. This allows us to compute the fourth homology group of the Greene sphere, along with several previously unknown groups. We also show that persistent discrete homology computes faster than simplicial homology of Vietoris-Rips complex in the high-noise non-metric settings, making it a better choice for noisy data sets.

Authors: Matthew J. Katz, Rachel Saban, Micha Sharir

We present efficient algorithms for the bottleneck path problem in two geometric settings that arise naturally in applications: directional-antenna graphs in the plane with antenna angles bounded from below by a constant, and visibility graphs whose vertices lie on or above a 1.5-dimensional terrain, both with Euclidean distances as edge weights. We provide near-linear algorithms for the corresponding decision problems, namely, determining whether the subgraph obtained by retaining all edges with weight at most some threshold ${\bf bn}$ contains a path from $s$ to $t$. We then use the decision procedures to obtain algorithms for the bottleneck path problem that run in $O^*(n^{8/7})$ randomized expected time, where $n$ is the input size and the $O^*(\cdot)$ notation hides subpolynomial factors. Within the same performance bounds, we can also solve the bounded-hop version, in which we only consider $s$-$t$ paths with at most $k$ edges, for a given integer $k < n$.

Authors: Yixin Cao, Ying Xu

Recent breakthroughs in Cluster Editing have motivated attempts to adapt these approaches to obtain better-than-$2$ approximations for Cluster Deletion. We rule out this possibility under the Unique Games Conjecture: Cluster Deletion is NP-hard to approximate within a factor of $2-ε$ for every fixed $ε>0$, matching the known $2$-approximation [Veldt et al., WWW 2018]. Our approximation-preserving reduction from Vertex Cover also implies NP-hardness of approximation within $\sqrt2-ε$. We also show that better-than-$2$ approximations are possible in restricted settings. We close the paper with a brief discussion of the relationship between Cluster Editing and Bad Triangle Transversal. In particular, we give a $31$-vertex graph~$G$ for which the two optimal values differ, answering an open question of Adriaens and Tatti [ICML 2026].

Authors: Ariel Kulik, Thiago Oliveira, Roy Schwartz, Mohit Singh

We study the problem of maximizing a general and not necessarily monotone submodular function subject to a matroid independence constraint. This problem has a rich history, with multiple algorithms using both discrete and continuous methods. Recently, [Ganz-Rozenman, Kulik, Schwartz and Singh STOC `26] presented a novel hybrid approach based on a Poisson process that aims to combine the strengths of both discrete and continuous methods for the special case of the problem where the submodular function is monotone. Our main result is a new Poisson process based hybrid algorithm that works for both non-monotone and monotone submodular functions, achieving an approximation of $ \frac{1}{e}$ for the former and $1-\frac{1}{e}$ for the latter. The algorithm always maintains a feasible set and at random times governed by the Poisson process it performs a single element swap based on a best response set. The new idea is that our algorithm is spiteful as it can purposefully discard an element that is in both the current set and the best response set. Surprisingly, this spiteful step does not harm the approximation our algorithm achieves for monotone submodular functions but is necessary for the non-monotone case. As applications, we obtain fast approximation algorithms for maximizing non-monotone submodular function subject to a general matroid independence constraint as well as faster algorithms for a partition matroid.

Authors: Fan Chen, Sinho Chewi, Alexander Rakhlin, Matthew S. Zhang

We study exact simulation of diffusions via rejection sampling on path space using unbiased estimators of the density ratio obtained from Girsanov's theorem. When applied to the underdamped Langevin diffusion, it yields an algorithm for sampling from a strongly log-concave and log-smooth distribution with condition number $κ$, in dimension $d$, to accuracy $\varepsilon$ in Rényi divergence, in $\widetilde O(κ^{2/3} d^{1/3}\,\mathrm{polylog}(1/\varepsilon))$ queries. Under a third derivative bound, the dimension dependence improves to $d^{1/5}$. This improves substantially over the prior state-of-the-art complexity of $\widetilde O(κd^{1/2}\,\mathrm{polylog}(1/\varepsilon))$ for the Metropolis-adjusted Langevin algorithm, and over the $d^{1/4}$ dimension dependence of Metropolized Hamiltonian Monte Carlo under the same third derivative bound. We also present applications to the mirror Langevin diffusion, and for obtaining Fisher information bounds in the non-log-concave case.

Authors: Zhihao Gavin Tang, Yuhao Zhang

We prove a tight impossibility result for online vertex cover under edge arrivals. No randomized integral or fractional algorithm achieves a competitive ratio strictly below $2$ against an oblivious adversary, even on bipartite graphs. Since the standard algorithm that takes both endpoints of every uncovered edge is $2$-competitive, this settles the optimal ratio. Our proof is a direct reduction from the recent breakthrough blueprint framework of Assadi, Jiang, and Xiang.

Authors: Laura Bülte, Philip Mayer, Lars Müller, Petra Mutzel

The Graph Edit Distance (GED) is a widely used graph similarity measure asking for the minimum cost of a sequence of edits transforming one (labeled) graph into another. The considered edit operations are deletion, insertion, and relabeling of nodes and edges. Special cases include the Graph Isomorphism problem, as well as many other graph problems that ask for the existence or minimum cost of a certain substructure, like the Traveling Salesman or Maximum Clique problem. We present a novel exponential time algorithm to compute the exact GED and a corresponding edit sequence in $O^*(4 + \varepsilon)^n$ time and polynomial space, provided one of the two graphs admits strictly sublinear balanced separators. In particular, the claimed runtime holds if one of the graphs is $K_h$-minor free (e.g., planar), or has bounded treewidth, which is the case for many real-world applications (e.g., all instances in GEDLIB). This substantially improves the best known worst-case running time bounds of $O^*(n!)$ for these graph classes.

Authors: Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen, Mingyu Guo

Treewidth is a fundamental graph invariant that quantifies how tree-like a given graph is. It is extensively used with dynamic programming to design fixed-parameter tractable algorithms for many NP-hard graph combinatorial optimization problems. However, despite broad theoretical applicability, treewidth dynamic programming (TDP) does not scale in practice beyond graphs with very small treewidth. Rather than applying TDP as a standalone technique, in this paper, we demonstrate that TDP can serve as a broadly applicable enhancer for a wide range of graph combinatorial optimization algorithms. Our framework leverages the concept of treewidth modulators, which refer to vertex sets whose removal significantly reduces the treewidth. We further propose an empirically efficient procedure for generating such treewidth modulators. To enhance an algorithm $\textit{A}$, we use $\textit{A}$ to heuristically make decisions on the modulators vertices, after which the remaining decisions outside the treewidth modulators become scalable for TDP. To demonstrate the general applicability of our proposed framework. We experimented with three classic graph combinatorial optimization models: Maximum Independent Set, Minimum Vertex Cover, and Max Cut. We apply TDP to enhance algorithms across diverse paradigms, including evolutionary search, greedy heuristics, and graph-neural-network-based heuristics. For all combinations of optimization models and base algorithms, TDP significantly improves performance over the original methods. In many settings, TDP-enhanced greedy heuristics are competitive with, and sometimes clearly outperform, state-of-the-art commercial solvers.

Authors: Yuhao Guo, Seth Pettie, Daniel Skora, Chengzhang Wan

We prove that the $\textsf{Greedy}$ binary search tree is $2^{O(\sqrt{\log\log n})}$-competitive. It is widely conjectured that $\textsf{Greedy}$ is $O(1)$-competitive, but before this work it was not known to be $f$-competitive, for any non-trivial $f(n)=o(\log n)$. Our analysis differs from prior analyses of binary search trees. It takes what might be called a "scaling" approach, where the cost at a refined scale is related to the cost at a coarser scale, and Wilber's interleave lower bound.

Authors: Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Weiqiang Zheng

Budget-feasible mechanism design is a classic framework introduced by Singer, but there is still a wide gap between existing upper and lower bounds. In this paper, we significantly advance the state of the art. First, without computational constraints, we show that there exists a budget-feasible universally truthful mechanism with the following approximation ratios: - $3$ for monotone submodular valuations and $e+1$ for nonmonotone submodular valuations, improving over $3.798$ and $9.742$, respectively. - $e+1$ for XOS valuations, improving over $28$. In large markets, our approximation can be improved deterministically to $e$. - $2e+1$ for subadditive valuations, improving over $33$. In large markets, our approximation can be improved deterministically to $2e$. Moreover, for subadditive valuations, we obtain a constant-approximation mechanism that runs in polynomial time using demand queries. This improves over the previous best approximation of $O(\log \log n)$, resolving a long-standing open problem going back to Dobzinski, Papadimitriou, and Singer, who conjectured that a constant approximation requires exponentially many demand queries. We obtain these results through a simple and unifying framework based on non-truthful indirect mechanisms, recently coined compensation design. In particular, through a potential argument, we establish constant price-of-stability bounds for compensation design based on marginal-contribution payment rules, which we then translate into truthful direct mechanisms. For subadditive valuations, the core of the argument is a new smoothing lemma showing that every subadditive function can be approximated within a factor of $2$ by a self-bounding function. This is also of independent interest, readily addressing an open question in multiwinner elections by showing the existence of a $2e$-approximate core even under subadditive valuations.

Authors: Sara Ahmadian, Shuchi Chawla, Ravi Kumar, Manish Purohit, Shirley Zhang

We present a new online algorithm for the well-known Multi-Level Aggregation Problem (MLAP) with arbitrary delay functions, achieving a $2D$-competitive ratio, where $D$ is the depth of the underlying tree. This result improves the current best-known competitive ratio of $O(D^2)$ and asymptotically matches the $D$-competitive bound previously known only for the deadline variant, thereby closing the asymptotic gap between the two settings. Our key technical contribution is a novel dual fitting framework that provides a unified analysis for both settings; in particular, it also establishes a $D$-competitive ratio for MLAP with deadlines. Our analysis is built upon two new ideas: a hindsight dual construction, which resolves the infeasibility issues in traditional online primal-dual methods, and a time-dependent dual packing that maintains feasibility over dynamic request sets.

Authors: Yuchong Pan, Michel X. Goemans

The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, each vertex has a capacity, and the goal is to find a maximum weight subset of edges whose total incident demand at every vertex does not exceed its capacity. We study $(α, β)$-bicriteria approximation algorithms, which return a solution of weight at least $1/α$ times the optimum while allowing an additive capacity violation of at most $β$ times the maximum edge demand. We give an iterative relaxation algorithm for the demand matching problem that exploits a structural characterization of strictly fractional extreme points of the natural LP relaxation, which reduces the residual rounding problem to odd-cycle instances. Combined with a better-of-two rounding strategy, this yields $(7/6, 1)$- and $(1, 1)$-bicriteria approximation algorithms for general and bipartite graphs, respectively. We further generalize this approach to obtain a parametric family of algorithms, including a $(1, 4/3)$-bicriteria approximation. Separately, for the more general $k$-hypergraph demand matching problem, we give a greedy, combinatorial $(k, 1)$-bicriteria approximation algorithm. We complement these algorithmic results with matching lower bounds relative to the natural LP relaxation for $β= 0$ and all $β\geq 1$, completely characterizing the trade-off between weight approximation and additive capacity violation in this range.

Authors: Michael Saks, Aravind Srinivasan, Renata Valieva

The standard method of exponential moments for proving concentration bounds can often be replaced by an argument based on elementary symmetric polynomials. We introduce an additional element of randomness into this framework, which reduces the problem to bounding product moments over a uniformly sampled set of indices. We show that this approach gives useful bounds in three settings. For read-$Δ$ families under limited independence, we obtain bounds governed by the degrees of randomly induced dependency subgraphs, improving the dependence on worst-case degrees. For random binary linear hashing with (semi-)random inputs, we derive fixed-bin and maximum-load bounds by controlling the rank defect of random tuples of input keys. Finally, for stochastic processes, we show how decay of product moments yields concentration bounds, recovering the spectral and mixing-time scales for finite-state Markov chains.