Theory of Computing Report

Every engineer and scientist knows there is a fundamental difference between a “simulation” and a “prediction,” but what is the root of that distinction? At the highest level, we contrast simulation against black-box modeling. Simulations are typically thought of as “transparent boxes” where we can describe the intent of each part of the model that produces a forecast.

A roboticist might think of a simulation as a computer system designed to integrate the differential equations that define basic laws of physics. For example, you predict the path the airplane takes based on physical models of lift and drag and how the plane moves under different control settings. Simple simulations based on reduced equations might suffice for some tasks. For others, we might have to rely on computational fluid dynamics to truly capture the behavior we’re after.

The transparent box becomes murky when systems are too complex to predict precisely. Many designers accept adding randomness to their simulations, provided they can characterize the statistical models as plausible. The dynamics of coin flipping are too hard to capture precisely, but we’re usually fine with a random number generator that produces an even number of heads and tails. Noise in measurement devices often reliably has statistics that match those of Gaussian or Poisson random numbers, and such stochastic processes are reasonable stand-ins for the sorts of signals we’ll encounter in the wild. Maybe you can simulate elections based on random numbers derived from current polling results.

Where do we draw the line between sampling and simulation? I maintain that LLMs are simulations of language. We train next-token predictors in language models so that their generation matches the statistical properties of the data. Indeed, maximum likelihood selects probability distributions that make past sequences likely in the future. I’ve received a lot of pushback on this because the samples generated by the transformer are too black-box to count as simulations. This reaction suggests to me that some people want simulations to arise from models with articulable causal explanations.

The academic literature on simulation is also intentionally vague about the difference between modeling, sampling, and simulation. But this quote from the 1975 textbook Systems Simulation: The Art and Science, by industrial engineer Robert Shannon, highlights a crucial feature of simulation:

“Simulation is the process of designing a model of a real system and conducting experiments with this model for the purpose either of understanding the behavior of the system or of evaluating various strategies (within the limits imposed by a criterion or set of criteria) for the operation of the system.”

For Shannon, simulation is purpose-driven. You replace a real system with a model, and then evaluate counterfactuals in the modeled world. A forecast that is not evaluating a counterfactual configuration or strategy is not a simulation. Simulation is anything where we can evaluate counterfactual futures and gain insights from them.

Simulations can help engineers describe the behavior of complex systems and build theories and hypotheses for why that behavior occurs. Engineers can also use them to predict future behavior of the system if they were to intervene with some new policy or if an external force acted to change some parameters.

Under this broad tent, optimal control is simulation. Since everyone learns LQR first, we get such clean formulas out that we don’t think of this as a simulator. We think of this as an analytical technique. But if you instead solve LQR by gradient descent, you’ll find that you need to simulate to compute a gradient. This is the “forward pass” in backpropagation, a method for computing gradients that was initially invented to solve optimal control problems.

Indeed, the process of solving LQR by gradient descent looks like this: You pick a cost function that seems to match your design specification. You try a particular control policy out. You get a signal back based on its performance under your cost function. You use this signal to modify your control policy to a policy with lower cost and try again. Once you have repeated this enough times so that you don’t think you can further improve, you deploy the control system trained in simulation.

AI people have coined a cutesy name for this iterative control design process: “sim2real.” On the one hand, sim2real looks like it’s doing something far more sophisticated than optimal control. The simulators they use are highly complex, their control policies are neural networks, and their cost functions are a clever pastiche of best past practice. However, robotic sim2real is a short conceptual hop from Kalman’s papers on basic linearization of chemical plants in the 50s.1 And just as today’s roboticist wishes Nvidia GPUs were cheaper, Kalman and Koepcke lament how they would be better served by more compute.

The question then becomes, how good does your simulation need to be for control? In their description of sim2real, Zakka et al. discuss the demand for the highest-fidelity simulations possible. But what does that even mean for a simulation to be high fidelity? How can you validate the assertion of high fidelity? Components with dramatically different behaviors look the same once they are interconnected in feedback loops. How can we identify what modeling is necessary? Once they are connected in feedback, identifying actual parameters becomes impossible. What is the right way to deal with uncertainty in the simulators? Is “domain adaptation,” the hot trend of the last decade where we simulate a lot of different plausible environments, the right way to make progress? Which transparent boxes can be replaced with black boxes? These are some of the questions I’ll dig into during today’s lecture. In the next post, I’ll report on partial answers.

Subscribe now

By Ben Recht

Authors: Petr Kučera, Petr Martinek

Monadic second order logic (MSO2) plays an important role in parameterized complexity due to the Courcelle's theorem. This theorem states that the problem of checking if a given graph has a property specified by a given MSO2 formula can be solved by a parameterized linear time algorithm with respect to the treewidth of the graph and the size of the formula. We extend this result by showing that models of MSO2 formula with free variables can be represented with a decision diagram whose size is parameterized linear in the above mentioned parameter. In particular, we show a parameterized linear upper bound on the size of a sentential decision diagram (SDD) when treewidth is considered and a parameterized linear upper bound on the size of an ordered binary decision diagram (OBDD) when considering the pathwidth in the parameter. In addition, building on a lower bound on the size of OBDD by Razgon (2014), we show that there is an MSO2 formula and a class of graphs with bounded treewidth which do not admit an OBDD with the size parameterized by the treewidth. Our result offers a new perspective on the Courcelle's theorem and connects it to the area of knowledge representation.

Authors: Kalle Alaluusua, B. R. Vinay Kumar

Hypergraph data are often projected onto a weighted graph by constructing an adjacency matrix whose $(i,j)$ entry counts the number of hyperedges containing both nodes $i$ and $j$. This reduction is computationally convenient, but it can lose information: distinct hypergraphs may induce the same matrix, and the matrix entries are generally dependent because each hyperedge contributes to multiple pairs. We study the planted clique problem under this matrix-only observation model. For detection, we show that a spectral norm test is asymptotically powerful at the $\sqrt{n}$ scale, with explicit dependence on the background hyperedge probability. For recovery, we analyze a polynomial-time spectral method based on the leading eigenvector and prove exact recovery at the canonical $\sqrt{n}$ scale, again with explicit dependence on the background hyperedge probability. We also extend both results to sparse regimes in which the background hyperedge probability may depend on $n$. Our analysis adapts a leave-one-out eigenvector framework to this setting. These results provide rigorous detection and recovery guarantees when only the adjacency matrix is observed.

Authors: Zoe Geiselmann, Michael Joswig, Lars Kastner, Konrad Mundinger, Sebastian Pokutta, Christoph Spiegel, Marcel Wack, Max Zimmer

A T-curve of degree $d$ is given by a regular unimodular triangulation of $d \cdot Δ_2$ together with a sign distribution on its lattice points. By Viro's Patchworking Theorem, this determines the ambient isotopy type (a.k.a. real scheme) of a smooth real plane projective algebraic curve of the same degree. We present a near-quadratic time algorithm for extracting that isotopy type from the triangulation and the signs. Through a GPU-accelerated implementation, this allows one to compute billions of real schemes per second, enabling exhaustive enumeration at scale. This algorithm was essential for our recent construction of all 121 real schemes of degree seven by T-curves.

Authors: Rui Xu, Dafei Qin, Kaichun Qiao, Qiujie Dong, Huaijin Pi, Qixuan Zhang, Longwen Zhang, Lan Xu, Jingyi Yu, Wenping Wang, Taku Komura

Recent advancements in autoregressive transformers have demonstrated remarkable potential for generating artist-quality meshes. However, the token ordering strategies employed by existing methods typically fail to meet professional artist standards, where coordinate-based sorting yields inefficiently long sequences, and patch-based heuristics disrupt the continuous edge flow and structural regularity essential for high-quality modeling. To address these limitations, we propose Strips as Tokens (SATO), a novel framework with a token ordering strategy inspired by triangle strips. By constructing the sequence as a connected chain of faces that explicitly encodes UV boundaries, our method naturally preserves the organized edge flow and semantic layout characteristic of artist-created meshes. A key advantage of this formulation is its unified representation, enabling the same token sequence to be decoded into either a triangle or quadrilateral mesh. This flexibility facilitates joint training on both data types: large-scale triangle data provides fundamental structural priors, while high-quality quad data enhances the geometric regularity of the outputs. Extensive experiments demonstrate that SATO consistently outperforms prior methods in terms of geometric quality, structural coherence, and UV segmentation.

Authors: Jacob Sriraman, Eli Barton, Brittany Terese Fasy, David L. Millman, Brendan Mumey, Nate Rengo, Braeden Sopp, Vasishta Tumuluri, Binhai Zhu

We consider the parametric shortest paths problem in a linearly interpolated graph. Given two positively-weighted directed graphs $G_0=(V,E,ω_0)$ and $G_1=(V,E,ω_1),$ the linearly interpolated graph is the family of graphs $(1-λ)G_0+λG_1$, parameterized by $λ\in [0,1]$. The problem is to compute all distinct parametric shortest paths. We compute a data structure in $Θ(k|E|\log |V|)$ time, where~$k$ is the number of distinct parametric shortest paths over all~$λ\in [0,1]$ that exist for a nontrivial interval of parameters, each corresponding to a linear function in a maximal sub-interval of $[0,1]$. Using this data structure, a shortest path query takes~$Θ(\log k)$ time.

Authors: Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy

For an arbitrary family of predicates $\mathcal{F} \subseteq \{0,1\}^{[q]^k}$ and any $ε> 0$, we prove a single-pass, linear-space streaming lower bound against the gap promise problem of distinguishing instances of Max-CSP$({\mathcal{F}})$ with at most $β+ε$ fraction of satisfiable constraints from instances of with at least $γ-ε$ fraction of satisfiable constraints, whenever Max-CSP$({\mathcal{F}})$ admits a $(γ,β)$-integrality gap instance for the basic LP. This subsumes the linear-space lower bound of Chou, Golovnev, Sudan, Velingker, and Velusamy (STOC 2022), which applies only to a special subclass of CSPs with linear-algebraic structure. (Their result itself generalizes work of Kapralov and Krachun (STOC 2019) for Max-CUT.) Our approach identifies the right ``analytic'' analogues of previously-used linear-algebraic conditions; this yields substantial simplifications while capturing a much larger class of problems. Our lower bound is essentially optimal for single-pass streaming, since: (1) All CSPs admit $(1-ε)$-approximations in quasilinear space, and (2) sublinear-space streaming algorithms can simulate the LP (on bounded-degree instances), giving approximation algorithms when integrality gap instances do not exist. The starting point for our lower bound is a reduction from a "distributional implicit hidden partition'' problem defined by Fei, Minzer, and Wang (STOC 2026) in the context of multi-pass streaming. Our result is an analogue of theirs in the single-pass setting, where we obtain a much stronger (and tight) space lower bound.

Authors: Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, Fang-Yi Yu

Packing disjoint subgraphs in a given graph is a fundamental problem with many applications. Motivated by political districting, we focus on connected subgraphs that are compact (e.g., having constant radius from a single center vertex) and that satisfy additional composition requirements, such as a minimum population/weight threshold or balanced weight types (e.g., political affiliations). We aim to maximize coverage by disjoint districts that meet these requirements. In this work, we present new results that substantially improve the previously known bounds on balanced star districts for planar and minor-free graphs (Dharangutte et al. 2025). In particular, we improve the approximation factor from $O(\log n)$ to $O(1)$ for packing balanced star districts using the exact same algorithm, but with a refined analysis. We also extend the results beyond planar graphs to minor-free graphs and an even broader family of graphs of bounded expansion. Additionally, we obtain an $O(1)$ approximation for packing radius-$k$ districts (with a constant $k$) in planar and apex-minor-free graphs. In order to get a $(1+\varepsilon)$ approximation on the max coverage, we show that this can be achieved if we allow a slight relaxation of the balancedness parameters (by a factor that can be made arbitrarily close to $1$), for bounded radius-$k$ districts on planar and apex-minor-free graphs. We show that all of these results can also be obtained if we enforce a minimum weight threshold for each district as the composition requirement, rather than balancedness. We present various results on hardness and hardness of approximation for this variant, by graph and district types.

Authors: Alistair Moffat, David Hawking

We address the problem of motivating students in Data Structures and Algorithms courses by presenting two simple problems that each have a series of improvements to a basic algorithm, leading to spectacular decreases in runtimes. Coining a new term, we refer to such sequences as being "thrills of algorithms". Seeing runtimes drop from an estimate of days (or even years) to just a few seconds has a visceral impact which conveys the importance of efficient algorithms in a way unlikely to be forgotten. The demonstrations are particularly compelling because they can be performed live in class on the lecturer's laptop. To assist staff teaching such courses we provide detailed pseudocode descriptions and complexity analyses for the various methods, and can supply implementations on request.

We develop a topological framework for proving lower bounds on sign-rank via $\mathbb{Z}_2$–equivariant topology, and use it to resolve the sign-rank of the Gap Hamming Distance problem up to lower-order terms. For every (partial) sign matrix $A$, we associate a free $\mathbb{Z}_2$–simplicial complex $S(A)$ and show that sign-rank of $A$ is characterized by the linear analog of $\mathbb{Z}_2$-index of $S(A)$. As a consequence, the classical $\mathbb{Z}_2$–index of $S(A)$ lower bounds the sign-rank of $A$, which reduces sign-rank lower bounds to topological obstructions. This reduction allows us to use various tools from $\mathbb{Z}_2$–equivariant topology, particularly in regimes where classical lower-bound techniques break down. As the main application, we consider the Gap Hamming Distance function $\mathrm{GHD}_k^n$ (defined for $k < n/2$), which distinguishes pairs of strings in $\{0,1\}^n$ with Hamming distance at most $k$ from pairs with distance at least $n-k$. We prove an essentially tight lower bound and show that for any $k$, \[ \text{sign-rank}(\mathrm{GHD}_k^n) = (1-o_k(1))\,2k. \] where the $o_k(1)$ term is $O\left(\sqrt{\frac{\log k}{k}}\right)$. This improves on the previous lower bound of Hatami, Hosseini, and Meng (STOC 2023) who proved that sign-rank of $\mathrm{GHD}_k^n$ is at least $\Omega(k/\log(n/k))$. A key technical ingredient is a new analysis of the $\mathbb{Z}_2$-coindex (which lower bounds $\mathbb{Z}_2$-index) of the Vietoris--Rips complex of the hypercube in the sparse regime which yields an essentially tight lower bound. Previously, no results were known in the sparse regime.

Given a propositional proof system $P$, we may define a formula $\text{Prf}^P_s(F)$ which is satisfiable if and only if the formula $F$ has a length $\leq s$ refutation in $P$. These formulas have received much attention in recent years due to their fundamental nature --- if a powerful proof system $P$ cannot refute $\text{Prf}^Q_s(F)$, and $P$ can formalize a set of techniques, then we cannot expect these techniques to prove lower bounds on $Q$ proofs --- as well as due to their relationship to proving non-automatability of proof systems, as pioneered by Atserias and Müller. We provide, to our knowledge, one of the first positive results regarding these principles.Let $\text{Prf}^{\mathrm{Frege}_d}_{s,l}$ denote the $\text{Prf}$ formula for depth-$d$ Frege proofs of length $s$ and in which each line has size bounded by $l$. We show that in the regime of exponential length $s = 2^{n^\varepsilon}$, and polynomial-line size $l=n^{O(1)}$, depth-$d$ Frege proofs can refute $\text{Prf}_{s,l}^{\mathrm{Frege}_d}(\text{PHP}^{n+1}_n)$, and hence we give an example of a proof system $P$ which seemingly can prove its own lower bounds. In fact, our upper bounds can already be implemented in the fragment Res($\log$), and hence even an apparently limited subsystem of depth-$d$ Frege is already capable of proving depth-$d$ Frege lower bounds. To the best of our knowledge, this is the first example of a propositional proof system which is capable of proving strong lower bounds against itself. We prove our results by using a constructive proof of the switching lemma due to Razborov, particularly its presentation by Urquhart and Fu, and combining it with a recent study of $\text{Prf}^{\text{Res}}$ by Li, Li, and Ren, in order to reduce the problem of refuting $\text{Prf}_{s,l}^{\mathrm{Frege}_d}(\text{PHP}^{n+1}_n)$ to refuting the weak pigeonhole principle.

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

One of the main uses of simulation and forecasting in designed feedback systems is for deciding how to act. If I can map what will happen next, I can choose actions that steer me toward good outcomes. This mindset seems perfectly sensible, and it’s the backbone of statistical decision theory, tree search in game play, optimal control, and model predictive control. Moreover, people who are good at prediction get clout. You can even win money in markets. It seems like forecasting is a skill and talent, and one that requires deep knowledge of how the world works. And yet, in class on Monday, I discussed how you can make excellent forecasts by simple, strategic accounting.

To understand why, let’s examine how we know if forecasts are good. It’s sort of obvious, but we can only evaluate our predictions of the future once the future has become the past. I can’t tell how good your forecast is until the forecast event occurs. No matter how much we think about setting up ungamable metrics, forecasters can only be evaluated retrospectively. And this retrospective nature means we can cast forecasting in the game theoretic framework from last week. Let me write out the rules in the format I’ve been using.

We have a two-player game with repeated interactions. In every round t,

1. Information x_t is revealed to both players.

2. Player One makes the forecast p_t

3. Player Two takes reveals the actual outcome y_t

4. A score s_t is assigned based on the triple (x_t,p_t,y_t).

Player One is the “forecaster.” Their goal is to accumulate as high a score as possible, summed across all rounds. Player Two wants the sum of all of the s_t to be as low as possible.

Now, we need to come up with score functions that can’t be “gamed,” and people have thought of many. For example, you might require the forecaster to have a low Brier score.

Now, a low Brier score is impossible in the adversarial context. Think about this weird game of bit prediction, where Player One guesses a number 0 or 1 and Player Two responds with the correct answer equal to 0 or 1. Player Two goes second and can always pick the opposite of what Player One says. That seems unfair.

Last week, I brought up the possibility of judging Player One with regret. Regret would measure the difference between Player One’s score and the score of a player who knows all of Player Two’s moves in advance but can only play a single prediction. In math, this quantity is written as

But good predictions alone may not be what you care about. Certainly, you’d want the frequencies to match. If you are predicting a sequence of probabilities, the average of those probabilities should match the average of the actual outcomes. If you consistently predict a player makes 90% of their free throws, we should see 90% of free throws made.

Similarly, other expected values should match. If you are changing your probabilities over time, the variance of the outcomes should still match the variance of your probabilities.

Maybe you’d prefer the predictions to be good across stratifications of the data. For example, if you are predicting free throws, maybe you’d want your forecasts to be accurate for all players individually. There are lots of subtests and subsets I can inspect, and I’d like to check that you are making good predictions on all of them.

Perhaps you’d like a certain degree of calibration from the forecast. In all of Player One’s forecasts where they say 20%, Player Two should say 1 only 20% of the time. In the forecasts where they say 60%, Player Two should say 1 60% of the time. If in all of the times Player One says there’s a 90% chance of a 1, only 10% of the times Player Two plays a 1, we’d think Player One is a pretty bad forecaster. Trying to achieve calibration across all possible probabilistic predictions seems a lot harder than just getting a single frequency correct in a Brier score game.

Mathematically, however, all of these problems are basically the same. They list a set of “test functions”, and Player 1 wants the following to be small for every single test function:

What are the test functions? If all we care about is getting the frequency that y_t equals one correct, then the test function is the constant function. For calibration, the test function is equal to one when a forecaster predicts probability x% and 0 otherwise. You’ll have one test function for each calibration bin. For calibration across strata, there will be a function for each stratum. Even Brier scores amount to calibration. You can get a low Brier Score by calibrating the functions

for all values of q.

The amazing thing is that making calibration errors of the form E_f small is incredibly mechanical. Juanky Perdomo and I spell out the general details in Section 3 of the tutorial “In Defense of Defensive Forecasting.” More or less, you just have to choose a prediction that makes the future look uncorrelated with the past. And you can always find such a prediction with simple search. Though there are specific details you have to deal with for each case, essentially the same procedure applies to very general sets of calibration functions.

We found that we could reduce every metric used to evaluate forecasting skill to some form of generalized calibration. There are whole bodies of work on proper scoring rules, conformal prediction, omniprediction, and outcome indistinguishability that reduce to generalized calibration. In the forecasting game, this generalized calibration can be done without specific domain expertise. As long as the evaluation metrics are prescribed in advance, a Defensive Forecaster will do well in fantasy sports, weather prediction, and election forecasting. It doesn’t need to know anything about the topic other than the judgment scheme.

Though Juanky and I wrote up our defense of defensive forecasting almost a year ago, this week was the first time I tried to present it in class. I got a lot of puzzled looks, as if I was playing clever card tricks. That’s the correct reaction! We are naturally impressed by people who are good at forecasting. We’re obsessed with predicting the future. Predictions from soothsayers are reassuring even if they’re consistently wrong.

And yet, forecasting is often just playing clever tricks for fun and profit. Though Dean Foster and Rahesh Vorha famously showed that percentile calibration amounted to bookkeeping thirty years ago, it turns out that all forms of generalized calibration can be achieved through bookkeeping. Next time someone tries to impress you with their prediction market prowess, remember that cooking the books isn’t the same as clairvoyance.

Subscribe now

By Ben Recht

I posted about using the Banach-Tarski Paradox(BT)  to explain the miracle of Loaves and Fishes (LF) here.

Darling says that whenever I fool my readers or my students then I have to tell them later, so I'll tell you now: The story about me meeting with Pope and talking about the BT Paradox (that would be a good name for a rock band: B-T-Paradox) was not true. I think my readers know that.

 

1) I first learned the Banach-Tarski Paradox as a grad student in 1981 when I read Hillary Putnam's article Models and Reality where he writes on Page 470:

One cannot simply sit down in one's study and ``decide'' that ``V=L'' is to be true, or that the axiom of choice is to be true. Nor would it be appropriate for the mathematical community to call an international convention and legislate these matters. Yet , it seems to me that if we encountered an extra-terrestrial species of intelligent beings who had developed a high level of mathematics, and it turned out they rejected the axiom of choice (perhaps because of the Tarski-Banach Theorem), it would be wrong to regard them as simply making a mistake. To do that would, on view, amount to saying that acceptance of the axiom of choice is built into our notion of rationality itself; that does not seem to me to be the case.

I agree with him and I wonder if we accept AC too readily. See my blog post on the BT paradox and my wife's strong opinion (she's against it).    

2) Back in 1981 my first thought was I wonder if someone has thought to use the BT paradox to explain the LF? And if so, were they serious or was it some kind of  joke? And does the Pope really get a discount at Pope-Yes? 

I also had the meta-thought (which I could not have said as cleanly as I will now):

 I wonder how I could find out if anyone else has thought of the BT-LF connection? 

Recall that back in 1981 the Internet was but a glint in Al Gore's eyes.  So back then I could not find out if anyone else had that thought of BT-LF. 

But now I can! And indeed, as I expected, some other people have made the connection of BT to LF: 

A tweet and a Reddit thread discussing the tweet: here. Not serious 

A serious article, I think, here   

A 24-page article about Holy Water and BT.  I can't imagine an article that long being a parody so I think its serious, see here. On the other hand, there is a 12-page article about Ramsey Theory and History that I think is supposed to be a parody, see here. 

A parody article, I think, here

I am sure there are more. 

3) I had thought of doing a blog post about BT and LF  a long time ago,  but Pope Leo having a math degree was the final push I needed.

4) The word cardinal has three very different meanings: (a) a type of infinity, (b) a position in the Catholic church, (c) the bird.  Same for large cardinal

5) One of my students who proofread the post thought that people will know it's a hoax since I am a vegetarian and hence would not eat at Pope-Yes, even if the Pope was paying. 

 

By gasarch

Authors: Reed Phillips

Tarski's theorem states that every monotone function from a complete lattice to itself has a fixed point. We specifically consider the two-dimensional lattice $\mathcal{L}^2_n$ on points $\{1, \ldots, n\}^2$ and where $(x_1, y_1) \leq (x_2, y_2)$ if $x_1 \leq x_2$ and $y_1 \leq y_2$. We show that the quantum query complexity of finding a fixed point given query access to a monotone function on $\mathcal{L}^2_n$ is $Ω((\log n)^2)$, matching the classical deterministic upper bound. The proof consists of two main parts: a lower bound on the quantum query complexity of a composition of a class of functions including ordered search, and an extremely close relationship between finding Tarski fixed points and nested ordered search.

Authors: Joseph Slote, Alexander Volberg, Haonan Zhang

Polynomial threshold functions (PTFs) are an important low-complexity class of Boolean functions, with strong connections to learning theory and approximation theory. Recent work on learning and testing PTFs has exploited structural and isoperimetric properties of the class, especially bounds on average sensitivity, one of the central themes in the study of PTFs since the Gotsman--Linial conjecture. In this work we exhibit a new geometric sense in which PTFs are tightly constrained, by studying them through the lens of the \textit{Boolean surface area} (or Talagrand boundary): \[ \text{BSA}[f]={\mathbb E}|\nabla f| = {\mathbb E}|\sqrt{{Sens}_f(x)}, \] which is a natural measure of vertex-boundary complexity on the discrete cube. Our main result is that every degree-$d$ PTF $f$ has subpolynomial Boolean surface area: \[ \text{BSA}[f]\le \exp(C(d)\sqrt{\log n}). \] This is a superpolynomial improvement over the previous bound of $n^{1/4}(\log n)^{C(d)}$ that follows from Kane's landmark bounds on average sensitivity of PTFs \cite{DK}.

Authors: Haimeng Zhao, Alexander Zlokapa, Hartmut Neven, Ryan Babbush, John Preskill, Jarrod R. McClean, Hsin-Yuan Huang

Broadly applicable quantum advantage, particularly in classical data processing and machine learning, has been a fundamental open problem. In this work, we prove that a small quantum computer of polylogarithmic size can perform large-scale classification and dimension reduction on massive classical data by processing samples on the fly, whereas any classical machine achieving the same prediction performance requires exponentially larger size. Furthermore, classical machines that are exponentially larger yet below the required size need superpolynomially more samples and time. We validate these quantum advantages in real-world applications, including single-cell RNA sequencing and movie review sentiment analysis, demonstrating four to six orders of magnitude reduction in size with fewer than 60 logical qubits. These quantum advantages are enabled by quantum oracle sketching, an algorithm for accessing the classical world in quantum superposition using only random classical data samples. Combined with classical shadows, our algorithm circumvents the data loading and readout bottleneck to construct succinct classical models from massive classical data, a task provably impossible for any classical machine that is not exponentially larger than the quantum machine. These quantum advantages persist even when classical machines are granted unlimited time or if BPP=BQP, and rely only on the correctness of quantum mechanics. Together, our results establish machine learning on classical data as a broad and natural domain of quantum advantage and a fundamental test of quantum mechanics at the complexity frontier.

Authors: Eireann Leverett, Jeroen van der Ham-de Vos

We present a constructive proof that a single C program, the \emph{Vulnerability Factory}, admits a countably infinite set of distinct, independently CVE-assignable software vulnerabilities. We formalise the argument using elementary set theory, verify it against MITRE's CVE Numbering Authority counting rules, sketch a model-checking analysis that corroborates unbounded vulnerability generation, and provide a Turing-machine characterisation that situates the result within classical computability theory. We then contextualise this result within the long-running debate on whether undiscovered vulnerabilities in software are \emph{dense} or \emph{sparse}, and introduce the concept of \emph{vulnerability abundance}: a quantitative analogy to chemical elemental abundance that describes the proportional distribution of vulnerability classes across the global software corpus. Because different programming languages render different vulnerability classes possible or impossible, and because language popularity shifts over time, vulnerability abundance is neither static nor uniform. Crucially, we distinguish between infinite \emph{vulnerabilities} and the far smaller set of \emph{exploits}: empirical evidence suggests that fewer than 6\% of published CVEs are ever exploited in the wild, and that exploitation frequency depends not only on vulnerability abundance but on the market share of the affected software. We argue that measuring vulnerability abundance, and its interaction with software deployment, has practical value for both vulnerability prevention and cyber-risk analysis. We conclude that if one programme can harbour infinitely many vulnerabilities, the set of all software vulnerabilities is necessarily infinite, and we suggest the Vulnerability Factory may serve as a reusable proof artifact, a foundational `test object',for future formal results in vulnerability theory.

Authors: Pan Peng, Jingyu Wu

We study quantum property testing for directed graphs with maximum in-degree and out-degree bounded by some universal constant $d$. For a proximity parameter $\varepsilon$, we show that any property that can be tested with $O_{\varepsilon,d}(1)$ queries in the classical bidirectional model, where both incoming and outgoing edges are accessible, can also be tested in the quantum unidirectional model, where only outgoing edges are accessible, using $n^{1/2 - Ω_{\varepsilon,d}(1)}$ queries. This yields an almost quadratic quantum speedup over the best known classical algorithms in the unidirectional model. Moreover, we prove that our transformation is almost tight by giving an explicit property $P_\varepsilon$ that is $\varepsilon$-testable within $O_\varepsilon(1)$ classical queries in the bidirectional model, but requires $\widetildeΩ(n^{1/2-f'(\varepsilon)})$ quantum queries in the unidirectional model, where $f'(\varepsilon)$ is a function that approaches $0$ as $\varepsilon$ approaches $0$. As a byproduct, we show that in the unidirectional model, the number of occurrences of any constant-size subgraph $H$ can be approximated up to additive error $δn$ using $o(\sqrt{n})$ quantum queries.

Authors: Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou

We initiate the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan [KM24], under the constraint of differential privacy. We consider the continual release model, where a generator must eventually output a stream of valid strings while protecting the privacy of the entire input sequence. Our first main result is that for countable collections of languages, privacy comes at no qualitative cost: we provide an $\varepsilon$-differentially-private algorithm that generates in the limit from any countable collection. This stands in contrast to many learning settings where privacy renders learnability impossible. However, privacy does impose a quantitative cost: there are finite collections of size $k$ for which uniform private generation requires $Ω(k/\varepsilon)$ samples, whereas just one sample suffices non-privately. We then turn to the harder problem of language identification in the limit. Here, we show that privacy creates fundamental barriers. We prove that no $\varepsilon$-DP algorithm can identify a collection containing two languages with an infinite intersection and a finite set difference, a condition far stronger than the classical non-private characterization of identification. Next, we turn to the stochastic setting where the sample strings are sampled i.i.d. from a distribution (instead of being generated by an adversary). Here, we show that private identification is possible if and only if the collection is identifiable in the adversarial model. Together, our results establish new dimensions along which generation and identification differ and, for identification, a separation between adversarial and stochastic settings induced by privacy constraints.

Authors: Ainesh Bakshi, Xinyu Tan

Gibbs states are a natural model of quantum matter at thermal equilibrium. We investigate the role of external fields in shaping the entanglement structure and computational complexity of high-temperature Gibbs states. External fields can induce entanglement in states that are otherwise provably separable, and the crossover scale is $h\asymp β^{-1} \log(1/β)$, where $h$ is an upper bound on any on-site potential and $β$ is the inverse temperature. We introduce a quasi-local Lindbladian that satisfies detailed balance and rapidly mixes to the Gibbs state in $\mathcal{O}(\log(n/ε))$ time, even in the presence of an arbitrary on-site external field. Additionally, we prove that for any $β<1$, there exist local Hamiltonians for which sampling from the computational-basis distribution of the corresponding Gibbs state with a sufficiently large external field is classically hard, under standard complexity-theoretic assumptions. Therefore, high-temperature Gibbs states with external fields are natural physical models that can exhibit entanglement and classical hardness while also admitting efficient quantum Gibbs samplers, making them suitable candidates for quantum advantage via state preparation.

Authors: Hui Liu, Zhijie Zhang

This paper re-examines the problem of fairly and efficiently allocating indivisible goods among agents with additive bivalued valuations. Garg and Murhekar (2021) proposed a polynomial-time algorithm that purported to find an EFX and fPO allocation. However, we provide a counterexample demonstrating that their algorithm may fail to terminate. To address this issue, we propose a new polynomial-time algorithm that computes a WEFX (Weighted Envy-Free up to any good) and fPO allocation, thereby correcting the prior approach and offering a more general solution. Furthermore, we show that our algorithm can be adapted to compute a WEQX (Weighted Equitable up to any good) and fPO allocation.

Authors: Marco Bressan, Stefano Clemente, Giacomo Fumagalli

We study the problem of counting $k$-\emph{hyper}graphlets, an interesting but surprisingly ignored primitive, with the aim of understanding if efficient algorithms exist. To this end we consider \emph{color coding}, a well-known technique for approximately counting $k$-graphlets in graphs. Our first result is that, on hypergraphs, color coding encounters a \emph{quadratic barrier}: under the Orthogonal Vector Conjecture, no implementation of it can run in time sub-quadratic in the size of the input. We then introduce a simple property, $(α,β)$-niceness, that hypergraphs from real-world datasets appear to satisfy for small values of $α$ and $β$. Intuitively, an $(α,β)$-nice hypergraph can be split into two sub-hypergraphs having respectively rank at most $α$ and degree at most $β$. By applying different techniques to each sub-hypergraph and carefully combining the outputs, we show how to run color coding in time $2^{O(k)} \cdot \big(2^β|V| + α^k |E| + α^2 β\size{H}\big)$, where $H=(V,E)$ is the input hypergraph. Afterwards, we can sample colorful $k$-hypergraphlets uniformly in expected $k^{O(k)} \cdot (β^2+\ln |V|)$ time per sample. Experiments on real-world hypergraphs show that our algorithm neatly outperforms the naive quadratic algorithm, sometimes by more than an order of magnitude.

Authors: Marcin Bienkowski, Julien Dallot, Dominik Danelski, Maciej Pacut, Stefan Schmid

Payment channel networks (PCNs) are a promising solution to make cryptocurrency transactions faster and more scalable. At their core, PCNs bypass the blockchain by routing the transactions through intermediary channels. However, a channel can forward a transaction only if it possesses the necessary funds: the problem of keeping the channels balanced is a current bottleneck on the PCN's transaction throughput. This paper considers the problem of maximizing the number of accepted transactions by a channel in a PCN. Previous works either considered the associated optimization problem with all transactions known in advance or developed heuristics tested on particular transaction datasets. This work however considers the problem in its purely online form where the transactions are arbitrary and revealed one after the other. We show that the problem can be modeled as a new online knapsack variant where the items (transaction proposals) can be either positive or negative depending on the direction of the transaction. The main contribution of this paper is a deterministic online algorithm that is $O(\log B)$-competitive, where $B$ is the knapsack capacity (initially allocated funds). We complement this result with an asymptotically matching lower bound of $Ω(\log B)$ which holds for any randomized algorithm, demonstrating our algorithm's optimality.

Authors: Francisco Sena, Aleksandr Politov, Corentin Moumard, Massimo Cairo, Romeo Rizzi, Manuel Cáceres, Sebastian Schmidt, Juha Harviainen, Alexandru I. Tomescu

A fundamental algorithmic problem in computational biology is to find all subgraphs of a given type (superbubbles, snarls, and ultrabubbles) in a directed or bidirected input graph. These correspond to regions of genetic variation and are useful in analyzing collections of genomes. We present the first linear-time algorithms for identifying all snarls and all ultrabubbles, resolving problems open since 2018. The algorithm for snarls relies on a new linear-size representation of all snarls with respect to the number of vertices in the graph. We employ the well-known SPQR-tree decomposition, which encodes all 2-separators of a biconnected graph. After several dynamic-programming-style traversals of this tree, we maintain key properties (such as acyclicity) that allow us to decide whether a given 2-separator defines a subgraph to be reported. A crucial ingredient for linear-time complexity is that acyclicity of linearly many subgraphs can be tested simultaneously via the problem of computing all arcs in a directed graph whose removal renders it acyclic (so-called feedback arcs). As such, we prove a fundamental result for bidirected graphs, that may be of independent interest: all feedback arcs can be computed in linear time for tipless bidirected graphs, while in general this is at least as hard as matrix multiplication, assuming the k-Clique Conjecture. Our results form a unified framework that also yields a completely different linear-time algorithm for finding all superbubbles. Although some of the results are technically involved, the underlying ideas are conceptually simple, and may extend to other bubble-like subgraphs. More broadly, our work contributes to the theoretical foundations of computational biology and advances a growing line of research that uses SPQR-tree decompositions as a general tool for designing efficient algorithms, beyond their traditional role in graph drawing.

Authors: Xiaoyu Leng, Hongchao Qin, Rong-Hua Li

Decomposing hypergraphs is a key task in hypergraph analysis with broad applications in community detection, pattern discovery, and task scheduling. Existing approaches such as $k$-core and neighbor-$k$-core rely on vertex degree constraints, which often fail to capture true density variations induced by multi-way interactions and may lead to sparse or uneven decomposition layers. To address these issues, we propose a novel \((k,δ)\)-dense subhypergraph model for decomposing hypergraphs based on integer density values. Here, $k$ represents the density level of a subhypergraph, while \(δ\) sets the upper limit for each hyperedge's contribution to density, allowing fine-grained control over density distribution across layers. Computing such dense subhypergraphs is algorithmically challenging, as it requires identifying an egalitarian orientation under bounded hyperedge contributions, which may incur an intuitive worst-case complexity of up to $O(2^{mδ})$. To enable efficient computation, we develop a fair-stable-based algorithm that reduces the complexity of mining a single $(k,δ)$-dense subhypergraph from $O(m^{2}δ^{2})$ to $O(nmδ)$. Building on this result, we further design a divide-and-conquer decomposition framework that improves the overall complexity of full density decomposition from $O(nmδ\cdot d^E_{\max} \cdot k_{\max})$ to $O(nmδ\cdot d^E_{\max} \cdot \log k_{\max})$. Experiments on nine real-world hypergraph datasets demonstrate that our approach produces more continuous and less redundant decomposition hierarchies than existing baselines, while maintaining strong computational efficiency. Case studies further illustrate the practical utility of our model by uncovering cohesive and interpretable community structures.

Authors: Guy Blelloch, Andrew Brady, Laxman Dhulipala, Jeremy Fineman, Jared Lo

We develop the first theoretically-efficient algorithm for maintaining the maximal independent set (MIS) of a graph in the parallel batch-dynamic setting. In this setting, a graph is updated with batches of edge insertions/deletions, and for each batch a parallel algorithm updates the maximal independent set to agree with the new graph. A batch-dynamic algorithm is considered efficient if it is work efficient (i.e., does no more asymptotic work than applying the updates sequentially) and has polylogarithmic depth (parallel time). In the sequential setting, the best known dynamic algorithms for MIS, by Chechik and Zhang (CZ) [FOCS19] and Behnezhad et al. (BDHSS) [FOCS19], take $O(\log^4 n)$ time per update in expectation. For a batch of $b$ updates, our algorithm has $O(b \log^3 n)$ expected work and polylogarithmic depth with high probability (whp). It therefore outperforms the best algorithm even in the sequential dynamic case ($b = 1)$. As with the sequential dynamic MIS algorithms of CZ and BDHSS, our solution maintains a lexicographically first MIS based on a random ordering of the vertices. Their analysis relied on a result of Censor-Hillel, Haramaty and Karnin [PODC16] that bounded the ``influence set" for a single update, but surprisingly, the influence of a batch is not simply the union of the influence of each update therein. We therefore develop a new approach to analyze the influence set for a batch of updates. Our construction of the batch influence set is natural and leads to an arguably simpler analysis than prior work. We then instrument this construction to bound the work of our algorithm. To argue our depth is polylogarithmic, we prove that the number of subrounds our algorithm takes is the same as depth bounds on parallel static MIS.

Authors: Chirag Wadhwa, Sitan Chen

In this work, we consider the fundamental task of quantum state certification: given copies of an unknown quantum state $ρ$, test whether it matches some target state $σ$ or is $ε$-far from it. For certifying $d$-dimensional states, $Θ(d/ε^2)$ copies of $ρ$ are known to be necessary and sufficient. However, the algorithm achieving this complexity makes fully entangled measurements over all $O(d/ε^2)$ copies of $ρ$. Often, one is interested in certifying states to a high precision; this makes such joint measurements intractable even for low-dimensional states. Thus, we study whether one can obtain optimal rates for quantum state certification and related testing problems while only performing measurements on $t$ copies at once, for some $1 < t \ll d/ε^2$. While it is well-understood how to use intermediate entanglement to achieve optimal quantum state learning, the only protocol known to achieve optimal testing is the one using fully entangled measurements. Our main result is a smooth copy complexity upper bound for state certification as a function of $t$, which achieves a near-optimal rate at $t = d^2$. In the high-precision regime, i.e., for $ε< \frac{1}{\sqrt{d}}$, this is a strict improvement over the entanglement used by the aforementioned optimal protocol. We also extend our techniques to develop new algorithms for the related tasks of mixedness testing and purity estimation, and show tradeoffs achieving the optimal rates for these problems at $t = d^2$ as well. Our algorithms are based on novel reductions from testing to learning and leverage recent advances in quantum state tomography in a non-black-box fashion. We complement our upper bounds with smooth lower bounds that imply joint measurements on $t \geq d^{Ω(1)}$ copies are necessary to achieve optimal rates for certification in the high-precision regime.

For an arbitrary family of predicates $\mathcal{F} \subseteq \{0,1\}^{[q]^k}$ and any $\epsilon > 0$, we prove a single-pass, linear-space streaming lower bound against the gap promise problem of distinguishing instances of Max-CSP$({\mathcal{F}})$ with at most $\beta+\epsilon$ fraction of satisfiable constraints from instances of with at least $\gamma-\epsilon$ fraction of satisfiable constraints, whenever Max-CSP$({\mathcal{F}})$ admits a $(\gamma,\beta)$-integrality gap instance for the basic LP. This subsumes the linear-space lower bound of Chou, Golovnev, Sudan, Velingker, and Velusamy (STOC 2022), which applies only to a special subclass of CSPs with linear-algebraic structure. (Their result itself generalizes work of Kapralov and Krachun (STOC 2019) for Max-CUT.) Our approach identifies the right ``analytic'' analogues of previously-used linear-algebraic conditions; this yields substantial simplifications while capturing a much larger class of problems. Our lower bound is essentially optimal for single-pass streaming, since: (1) All CSPs admit $(1-\epsilon)$-approximations in quasilinear space, and (2) sublinear-space streaming algorithms can simulate the LP (on bounded-degree instances), giving approximation algorithms when integrality gap instances do not exist. The starting point for our lower bound is a reduction from a "distributional implicit hidden partition'' problem defined by Fei, Minzer, and Wang (STOC 2026) in the context of multi-pass streaming. Our result is an analogue of theirs in the single-pass setting, where we obtain a much stronger (and tight) space lower bound.

We provide a computational complexity lens to understand the power of machine learning models, particularly their ability to model complex systems. Machine learning models are often trained on data drawn from sampleable or more complex distributions, a far wider range of distributions than just computable ones. By focusing on computable distributions, machine learning models can better manage complexity via probability. We abstract away from specific learning mechanisms, modeling machine learning as producing P/poly-computable distributions with polynomially-bounded max-entropy. We illustrate how learning computable distributions models complexity by showing that if a machine learning model produces a distribution $\mu$ that minimizes error against the distribution generated by a cryptographic pseudorandom generator, then $\mu$ must be close to uniform.

Applications are invited for a postdoctoral position in theoretical computer science (especially quantum computing) at the Graduate School of Mathematics, Nagoya University.

The position will start after July 2026. The starting date and duration are negotiable.

Website: http://francoislegall.com/jobs2026.html
Email: legall@math.nagoya-u.ac.jp

By shacharlovett

Authors: Tristan Simas

Exact relevance certification asks which coordinates are necessary to determine the optimal action in a coordinate-structured decision problem. The tractable families treated here admit a finite primitive basis, but optimizer-quotient realizability is maximal, so quotient shape alone cannot characterize the frontier. We prove a meta-impossibility theorem for efficiently checkable structural predicates invariant under the theorem-forced closure laws of exact certification. Structural convergence with zero-distortion summaries, quotient entropy bounds, and support-counting arguments explains why those closure laws are canonical. We establish the theorem by constructing same-orbit disagreements for four obstruction families, namely dominant-pair concentration, margin masking, ghost-action concentration, and additive/statewise offset concentration, using action-independent, pair-targeted affine witnesses. Consequently no correct tractability classifier on a closure-closed domain yields an exact characterization over these families. Here closure-orbit agreement is forced by correctness rather than assumed as an invariance axiom. The result therefore applies to correct classifiers on closure-closed domains, not only to classifiers presented through a designated admissibility package.

Authors: Matvey Mosievskiy, Lev Reyzin

We study computational limitations in \emph{multi-plant} average-case inference problems, in which $t$ disjoint planted structures of size $k$ are embedded in a random background on $n$ elements. A natural parameter in this setting is the total planted size $K := kt$. For several classic planted-subgraph problems, including planted clique, existing algorithmic and lower-bound evidence suggests a characteristic computational threshold near $\sqrt{n}$ in the single-plant setting. Our main result is a Sum-of-Squares (SoS) integrality gap for refuting the presence of multiple planted cliques. Specifically, for $G \sim G(n,1/2)$, we construct a degree-$d$ SoS pseudoexpectation for the natural relaxation that maximizes the total size of up to $t$ disjoint cliques. Throughout the regime $kt \le n^{1/2 - c\sqrt{d/\log n}},$ for a universal constant $c>0$, this relaxation achieves objective value $kt(1-o(1))$, and therefore degree-$d$ SoS cannot certify an upper bound below $kt$. This extends the planted-clique SoS lower bounds of~\cite{BarakHKKMP19} to a multi-plant setting with explicit disjointness constraints. As complementary evidence from a different computational model, we prove a lower bound in the statistical query (SQ) framework, extending the results of~\cite{FeldmanGRVX17}. We show that for detecting $t$ disjoint planted $k \times k$ bicliques (equivalently, a row-mixture distribution), when $kt = O(n^{1/2-δ})$ for any fixed $δ>0$, no polynomial-time SQ algorithm can distinguish the planted and null distributions with constant advantage.

Authors: Lance Fortnow

We provide a computational complexity lens to understand the power of machine learning models, particularly their ability to model complex systems. Machine learning models are often trained on data drawn from sampleable or more complex distributions, a far wider range of distributions than just computable ones. By focusing on computable distributions, machine learning models can better manage complexity via probability. We abstract away from specific learning mechanisms, modeling machine learning as producing P/poly-computable distributions with polynomially-bounded max-entropy. We illustrate how learning computable distributions models complexity by showing that if a machine learning model produces a distribution $μ$ that minimizes error against the distribution generated by a cryptographic pseudorandom generator, then $μ$ must be close to uniform.

Authors: Pritish Kamath, Ravi Kumar, Pasin Manurangsi

We study two conjectures posed in the analysis of Boolean functions $f : \{-1, 1\}^n \to \{-1, 1\}$, in both of which, the Majority function plays a central role: the "Majority is Least Stable" (Benjamini et al., 1999) and the "Non-Interactive Correlation Distillation for Erasures" (Yang, 2004; O'Donnell and Wright, 2012). While both conjectures have been refuted in their originally stated form, we obtain a nearly tight characterization of the noise parameter regime in which each of the conjectures hold, for all $n \ge 5$. Whereas, for $n=3$, both conjectures hold in all noise parameter regimes. We state refined versions of both conjectures that we believe captures the spirit of the original conjectures.

Authors: Martin Kolář

The definition of \NP\ requires, for each member language~$L$, a polynomial-time checking relation~$R$ and a constant~$k$ such that $w \in L \iff \exists y\,(|y| \leq |w|^k \wedge R(w,y))$. We show that this biconditional instantiates, for each member language, Hilbert's triple: a sound, complete, decidable proof system in which truth-in-$L$ and bounded provability coincide by fiat. We show further that the polynomial-time restriction on~$R$ does not exclude Gödel's proof-checking relation, which is itself polynomial-time and fits the definition as a literal instance. Hence \NP, taken as a totality over all polynomial-time~$R$, contains languages for which the biconditional asserts a property that Gödel's First Incompleteness Theorem prohibits. The semantic definition of \NP\ is unsatisfiable, for the same reason that Hilbert's Program is.

Authors: Mathias Bernhard

This paper presents a novel space-filling polyhedron (SFPH), here named the Josehedron, derived from the extremal points of the Fischer-Koch S triply periodic minimal surface (TPMS). The Josehedron is a plesiohedron with 12 faces (4 isosceles triangles and 8 mirror-symmetric quadrilaterals), 12 vertices, and 22 edges. It tiles three-dimensional space with 12 instances per cubic unit cell in 6 distinct orientations. The generating point set exhibits a remarkable connection to the pentagonal Cairo tiling when projected onto any coordinate plane. Several additional geometric properties are described, including integer vertex coordinates, interwoven labyrinths, and chiral symmetry between the polyhedra obtained from the combined minima and maxima of the function. Finally, the paper presents a general method for finding novel SFPHs based on any periodic function, TPMS, or other functions. The described method is applied to a selection of TPMS, and 7 additional, previously undocumented SFPH are shown in the Appendix.

Authors: Ulrich Bauer, Thomas Brüstle, Luis Scoccola

We introduce persistence with an emphasis on its algebraic foundations, using the representation theory of posets. Linear representations of posets arise in several areas of mathematics, including the representation theory of quivers and finite dimensional algebras, Morse theory and other areas of geometry, as well as topological inference and topological data analysis -- often via persistent homology. In some of these contexts, the category of poset representations of interest admits a metric structure given by the so-called interleaving distance. Persistence studies the algebraic properties of these poset representations and their behavior under perturbations in the interleaving distance. We survey fundamental results in the area and applications to pure and applied mathematics, as well as theoretical challenges and open questions.

Authors: Libor Barto, Maximilian Hadek, Dmitriy Zhuk

We develop a unified framework to characterize the power of higher-level algorithms for the constraint satisfaction problem (CSP), such as $k$-consistency, the Sherali-Adams LP hierarchy, and the affine IP hierarchy. As a result, solvability of a fixed-template CSP or, more generally, a Promise CSP by a given level is shown to depend only on the polymorphism minion of the template. Similarly, we obtain a minion-theoretic description of $k$-consistency reductions between Promise CSPs. We introduce a new hierarchy of SDP-like vector relaxations with vectors over $\mathbb Z_{p}$ in which orthogonality is imposed on $k$-tuples of vectors. Surprisingly, this relaxation turns out to be equivalent to the $k$-th level of the AIP-$\mathbb{Z}_p$ relaxation. We show that it solves the CSP of the dihedral group $\mathbf{D}_4$, the smallest CSP that fools the singleton BLP+AIP algorithm. Using this vector representation, we further show that the $p$-th level of the $\mathbb{Z}_p$ relaxation solves linear equations modulo $p^2$.

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

As large language models (LLMs) are increasingly trained on sensitive user data, understanding the fundamental cost of privacy in language learning becomes essential. We initiate the study of differentially private (DP) language identification and generation in the agnostic statistical setting, establishing algorithms and matching lower bounds that precisely quantify the cost of privacy. For both tasks, approximate $(\varepsilon, δ)$-DP with constant $\varepsilon > 0$ recovers the non-private error rates: $\exp(-r(n))$ for identification (for any $r(n) = o(n)$) and $\exp(-Ω(n))$ for generation. Under pure $\varepsilon$-DP, the exponents degrade by a multiplicative factor of $\min\{1, \varepsilon\}$, which we show is tight up to constants. Notably, for generation under pure DP with mild assumptions, the upper bound $\exp(-\min\{1,\varepsilon\} \cdot Ω(n))$ matches the lower bound up to some constants, establishing an optimal rate. Our results show that the cost of privacy in language learning is surprisingly mild: absent entirely under approximate DP, and exactly a $\min\{1,\varepsilon\}$ factor in the exponent under pure DP.

It is a long-standing open question whether the average-case hardness of NP implies the existence of a one-way function. The hypothetical world in which this does not hold is called Pessiland, which is the most pessimistic among Impagliazzo's five possible worlds. In this paper, we present the first "sharp" characterization of Pessiland: - NP is hard on average if and only if the minimum description length of programs in agnostic learning is hard to approximate on average with an approximation factor $\ell / \mathrm{polylog}(\ell)$, where $\ell$ is a new complexity measure of a distribution called advice complexity of sampling. - A one-way function does not exist if and only if the minimum description length of programs in agnostic learning is easy to approximate on average with an approximation factor $O(\ell)$. In particular, Pessiland is ruled out if and only if the small quantitative gap in approximation factors $\ell/\mathrm{polylog}(\ell)$ and $O(\ell)$ is closed. Our characterization is based on an optimal NP-hardness result for the Collective Minimum Monotone Satisfying Assignment (CMMSA) Problem, whose task is, given as input a collection of monotone formulas with at most $\ell$ literals, to compute the minimum weight of an assignment that satisfies as many monotone formulas as possible. We prove the NP-hardness of approximating the minimum weight within a factor of $\ell / \mathrm{polylog} \ell$, improving the previous inapproximability factor of $\ell^{\Omega(1)}$ by Hirahara (FOCS 2022). Our inapproximability factor is optimal up to the $\mathrm{polylog} \ell$ factor unless NP $\subseteq$ coAM because the CMMSA problem with an approximation factor $O(\ell)$ is in coAM.

The Department of Computer Science at Lund University invites applications for 1-2 PhD positions in theoretical computer science with focus on computational complexity and algorithms to be working in the research group of Susanna de Rezende. These are four-year full-time employed positions, but PhD positions usually include 20% teaching, in which case they are prolonged for one more year.

Website: https://derezende.github.io/openpositions/
Email: susanna.rezende@cs.lth.se

By shacharlovett

Authors: Petar Marković, Miklós Maróti, Ralph McKenzie, Aleksandar Prokić

We define a class of algebras, the semilattices of Mal'cev blocks (for short, SMB algebras). In a nutshell, these algebras are semilattices in which each element gets blown up into a Mal'cev algebra. We publish for the first time our old proofs that some SMB algebras induce tractable templates of the reprove that the Constraint Satisfaction Problem. Next, we reprove that, in fact, all SMB algebras induce tractable templates of the Constraint Satisfaction Problem, a result already proved by A. Bulatov. Also, we compare the two general proofs of the CSP Dichotomy and prove they are more similar than initially thought when they are applied to SMB algebras. This paper is the second in the series of papers investigating the SMB algebras and it is a precursor to our further research on the similarities between the proofs of the Dichotomy Theorem.

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

The Solow--Polasky diversity indicator (or magnitude) is a classical measure of diversity based on pairwise distances. It has applications in ecology, conservation planning, and, more recently, in algorithmic subset selection and diversity optimization. In this note, we investigate the computational complexity of selecting a subset of fixed cardinality from a finite set so as to maximize the Solow--Polasky diversity value. We prove that this problem is NP-hard in general metric spaces. The reduction is from the classical Independent Set problem and uses a simple metric construction containing only two non-zero distance values. Importantly, the hardness result holds for every fixed kernel parameter $θ_0>0$; equivalently, by rescaling the metric, one may fix the parameter to $1$ without loss of generality. A central point is that this is not a boilerplate reduction: because the Solow--Polasky objective is defined through matrix inversion, it is a nontrivial nonlinear function of the distances. Accordingly, the proof requires a dedicated strict-monotonicity argument for the specific family of distance matrices arising in the reduction; this strict monotonicity is established here for that family, but it is not assumed to hold in full generality. We also explain how the proof connects to continuity and monotonicity considerations for diversity indicators.

Authors: Thomas Depian, Carolina Haase, Martin Nöllenburg, André Schulz

A linkage $\mathcal{L}$ consists of a graph $G=(V,E)$ and an edge-length function $\ell$. Deciding whether $\mathcal{L}$ can be realized as a planar straight-line embedding in $\mathbb{R}^2$ with edge length $\ell(e)$ for all $e \in E$ is $\exists\mathbb{R}$-complete [Abel et al., JoCG'25], even if $\ell \equiv 1$, but a considerable part of $\mathcal{L}$ is rigid. In this paper, we study the computational complexity of the realization question for structurally simpler, less rigid linkages inside an open polygonal domain $P$, where the placement of some vertices may be specified in the input. We show XP-membership and W[1]-hardness with respect to the size of $G$, even if $\ell \equiv 1$ and no vertex positions are prescribed. Furthermore, we consider the case where $G$ is a path with prescribed start and end position and $\ell \equiv 1$. Despite the absence of any rigid components, we obtain NP-hardness in general, and provide a linear-time algorithm for arbitrary $\ell$ if $G$ has only three edges and $P$ is convex.

Authors: Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra, Arsen Vasilyan

In a landmark result, Linial, Mansour and Nisan (J. ACM 1993) gave a quasipolynomial-time algorithm for learning constant-depth circuits given labeled i.i.d. samples under the uniform distribution. Their work has had a deep and lasting legacy in computational learning theory, in particular introducing the $\textit{low-degree algorithm}$. However, an important critique of many results and techniques in the area is the reliance on product structure, which is unlikely to hold in realistic settings. Obtaining similar learning guarantees for more natural correlated distributions has been a longstanding challenge in the field. In particular, we give quasipolynomial-time algorithms for learning $\mathsf{AC}^0$ substantially beyond the product setting, when the inputs come from any graphical model with polynomial growth that exhibits strong spatial mixing. The main technical challenge is in giving a workaround to Fourier analysis, which we do by showing how new sampling algorithms allow us to transfer statements about low-degree polynomial approximation under the uniform setting to graphical models. Our approach is general enough to extend to other well-studied function classes, like monotone functions and halfspaces.

Authors: Jarosław Byrka, Yuhao Guo, Yang Hu, Shi Li, Chengzhang Wan, Zaixuan Wang

In this work we propose a single rounding algorithm for the fractional solutions of the standard LP relaxation for $k$-clustering. As a starting point, we obtain an iterative rounding $(\frac{3^p + 1}{2})$-Lagrangian Multiplier-Perserving (LMP) approximation for the $k$-clustering problem with the cost function being the $p$-th power of the distance. Such an algorithm outputs a random solution that opens $k$ facilities \emph{in expectation}, whose cost in expectation is at most $\frac{3^p + 1}{2}$ times the optimum cost. Thus, we recover the $2$-LMP approximation for $k$-median by Jain et al.~[JACM'03], which played a central role in deriving the current best $2$ approximation for $k$-median. Unlike the result of Jain et al., our algorithm is based on LP rounding, and it can be easily adapted to the $L_p^p$-cost setting. For the Euclidean $k$-means problem, the LMP factor we obtain is $\frac{11}{3}$, which is better than the $5$ approximation given by this framework for general metrics. Then, we show how to convert the LMP-approximation algorithms to a true-approximation, with only a $(1+\varepsilon)$ factor loss in the approximation ratio. We obtain a ($\frac{3^p + 1}{2}+\varepsilon$)-approximation algorithm for $k$-clustering with cost function being the $p$-th power of the distance, for $p \geq 1$. This reproduces the best known ($2+\varepsilon$)-approximation for $k$-median by Cohen-Addad et al. [STOC'25], and improves the approximation factor for metric $k$-means from 5.83 by Charikar at al. [FOCS'25] to $5+\varepsilon$ in our framework. Moreover, the same algorithm, but with a specialized analysis, attains ($4+\varepsilon$)-approximation for Euclidean $k$-means matching the recent result by Charikar et al. [STOC'26].

Authors: Mina Doosti, Ryan Sweke, Chirag Wadhwa

We introduce a framework for distributed quantum inference under communication constraints. In our model, $m$ distributed nodes each receive one copy of an unknown $d$-dimensional quantum state $ρ$, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of $ρ$. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT2019], by allowing quantum resources such as quantum communication and shared entanglement. Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state $σ$, decide whether $ρ=σ$ or $\|ρ-σ\|_1\geq ε$. Additionally, we focus on the case of limited quantum communication between distributed nodes and the central node. We show that when each communication channel is limited to only $n_q\leq \log d$ qubits, then the sample complexity of distributed state certification is $\mathcal{O}(\frac{d^2}{2^{n_q}ε^2})$ when public randomness is available to all nodes. Moreover, under the assumption that the channels used by the distributed nodes are mixedness-preserving, we prove a matching lower bound. We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an $Ω(\frac{d^3}{4^{n_q} ε^2})$ lower bound in the private-coin setting under the same assumption as above. Our lower bounds leverage a recently introduced quantum analogue of the celebrated Ingster-Suslina method and generalize arguments from the classical setting. Together, our work provides the first characterization of distributed quantum state certification in the regime of limited quantum communication and establishes a general framework for distributed quantum inference with communication constraints.

Authors: Pasin Manurangsi, Krzysztof Sornat

We present a polynomial-time algorithm for computing an optimal committee of size $k$ under any given Thiele voting rule for elections on the Voter Interval domain (i.e., when voters can be ordered so that each candidate is approved by a consecutive voters). Our result extends to the Generalized Thiele rule, in which each voter has an individual weight (scoring) sequence. This resolves a 10-year-old open problem that was originally posed for Proportional Approval Voting and later extended to every Thiele rule (Elkind and Lackner, IJCAI 2015; Peters, AAAI 2018). Our main technical ingredient is a new structural result -- a concavity theorem for families of intervals. It shows that, given two solutions of different sizes, one can construct a solution of any intermediate size whose score is at least the corresponding linear interpolation of the two scores. As a consequence, on Voter Interval profiles, the optimal total Thiele score is a concave function of the committee size. We exploit this concavity within an optimization framework based on a Lagrangian relaxation of a natural integer linear program formulation, obtained by moving the cardinality constraint into the objective. On Voter Interval profiles, the resulting constraint matrix is totally unimodular, so it can be solved in polynomial time. Our main algorithm and its proof were obtained via human--AI collaboration. In particular, a slightly simplified version of the main structural theorem used by the algorithm was obtained in a single call to Gemini Deep Think.

Authors: Afrouz Jabal Ameli, Jesper Nederlof, Shengzhe Wang

We provide improved space-time tradeoffs for permutation problems over additively idempotent semi-rings. In particular, there is an algorithm for the Traveling Salesperson Problem that solves $N$-vertex instances using space $S$ and time $T$ where $S\cdot T \leq 3.7493^{N}$. This improves a previous work by Koivisto and Parviainen [SODA'10] where $S\cdot T \leq 3.9271^N$, and overcomes a barrier they identified, as their bound was shown to be optimal within their framework. To get our results, we introduce a new parameter of a set system that we call the chain efficiency. This relates the number of maximal chains contained in the set system with the cardinality of the system. We show that set systems of high efficiency imply efficient space-time tradeoffs for permutation problems, and give constructions of set systems with high chain efficiency, disproving a conjecture by Johnson, Leader and Russel [Comb. Probab. Comput.'15].

Authors: Justin Dallant, László Kozma

The traveling salesman problem (TSP) is a cornerstone of combinatorial optimization and has deeply influenced the development of algorithmic techniques in both exact and approximate settings. Yet, improving on the decades-old bounds for solving TSP exactly remains elusive: the dynamic program of Bellman, Held, and Karp from 1962 uses $2^{n+O(\log{n})}$ time and space, and the divide-and-conquer approach of Gurevich and Shelah from 1987 uses $4^{n + O(\log^2{n})}$ time and polynomial space. A straightforward combination of the two algorithms trades off $T^{n+o(n)}$ time and $S^{n+o(n)}$ space at various points of the curve $ST = 4$. An improvement to this tradeoff when $2 < T < 2\sqrt{2}$ was found by Koivisto and Parviainen (SODA 2010), yielding a minimum of $ST \approx 3.93$. Koivisto and Parviainen show their method to be optimal among a broad class of partial-order-based approaches, and to date, no improvement or alternative method has been found. In this paper we give a tradeoff that strictly improves all previous ones for all $2 < T < 4$, achieving a minimum of $ST < 3.572$. A key ingredient is the construction of sparse set systems (hypergraphs) that admit a large number of maximal chains. The existence of such objects is of independent interest in extremal combinatorics, likely to see further applications. Along the way we disprove a combinatorial conjecture of Johnson, Leader, and Russell from 2013, relating it with the optimality of the previous tradeoff schemes for TSP. Our techniques extend to a broad class of permutation problems over arbitrary semirings, yielding improved space-time tradeoffs in these settings as well.