Theory of Computing Report

Authors: Ignacio Barros, Michaël Cadilhac, Guillermo A. Pérez

We study existential Presburger arithmetic extended with divisibility predicates (EPAD). Its satisfiability problem has long been known to be NP-hard, and has often been expected to lie in NP. We prove that it is PP-hard, ruling out this expectation unless NP=PP. This also implies \PP-hardness of satisfiability for positive Boolean combinations of word equations and length constraints. The lower bound is compatible with a strong form of Lipshitz-style simplification. We define a polynomial-time recognizable fragment, called \MergeAbs, in which the usual finite-quotient replacement of divisibility atoms can be repeated until no divisibility atom remains. Nevertheless, EPAD satisfiability is already PP-hard on this fully simplifiable fragment. The reduction starts from a threshold coefficient problem for a class of arithmetic circuits using only addition and shifts. The same systems used in the reduction also expose a limitation of normalization. A polynomial-size scaling family, indexed by $j$, forces an endpoint relation $v=(2^{2^j}+1)u$, and the natural finite-quotient simplification records it as one equation with coprime coefficients whose largest coefficient has bit-size $Θ(2^j)$.

Authors: Ignacio Barros, Michaël Cadilhac, Guillermo A. Pérez

We study existential Presburger arithmetic extended with divisibility predicates (EPAD). Its satisfiability problem has long been known to be NP-hard, and has often been expected to lie in NP. We prove that it is PP-hard, ruling out this expectation unless NP=PP. This also implies \PP-hardness of satisfiability for positive Boolean combinations of word equations and length constraints. The lower bound is compatible with a strong form of Lipshitz-style simplification. We define a polynomial-time recognizable fragment, called \MergeAbs, in which the usual finite-quotient replacement of divisibility atoms can be repeated until no divisibility atom remains. Nevertheless, EPAD satisfiability is already PP-hard on this fully simplifiable fragment. The reduction starts from a threshold coefficient problem for a class of arithmetic circuits using only addition and shifts. The same systems used in the reduction also expose a limitation of normalization. A polynomial-size scaling family, indexed by $j$, forces an endpoint relation $v=(2^{2^j}+1)u$, and the natural finite-quotient simplification records it as one equation with coprime coefficients whose largest coefficient has bit-size $Θ(2^j)$.

Monday, June 15 2026, 00:00

On Cutting Cakes and Crossing Curves

Authors: Alexandros Hollender, Gilbert Maystre, Kilian Risse

We consider the classic envy-free cake-cutting problem where the goal is to cut and allocate a divisible resource among a set of agents in a way that avoids any envy between them. When the agents' valuation functions are continuous and nonnegative, an envy-free solution is guaranteed to exist where each agent is allocated a contiguous piece of the resource. Such a solution can be efficiently computed using the standard cut-and-choose algorithm for two agents, but the problem is known to be hard when there are at least four agents. The setting with three agents has remained open. We show that the problem remains intractable for three agents. We obtain this result by uncovering a novel connection between cake-cutting and a computational problem corresponding to the Jordan curve theorem, introduced by Adler, Daskalakis, and Demaine (2016). As our main technical contribution, we provide the first lower bounds for the Jordan curve problem in the form of a query lower bound as well as hardness for the class UEOPL, a subclass of PPAD containing notoriously challenging problems such as Simple Stochastic Games and the P-matrix Linear Complementarity Problem.

Authors: Alexandros Hollender, Gilbert Maystre, Kilian Risse

We consider the classic envy-free cake-cutting problem where the goal is to cut and allocate a divisible resource among a set of agents in a way that avoids any envy between them. When the agents' valuation functions are continuous and nonnegative, an envy-free solution is guaranteed to exist where each agent is allocated a contiguous piece of the resource. Such a solution can be efficiently computed using the standard cut-and-choose algorithm for two agents, but the problem is known to be hard when there are at least four agents. The setting with three agents has remained open. We show that the problem remains intractable for three agents. We obtain this result by uncovering a novel connection between cake-cutting and a computational problem corresponding to the Jordan curve theorem, introduced by Adler, Daskalakis, and Demaine (2016). As our main technical contribution, we provide the first lower bounds for the Jordan curve problem in the form of a query lower bound as well as hardness for the class UEOPL, a subclass of PPAD containing notoriously challenging problems such as Simple Stochastic Games and the P-matrix Linear Complementarity Problem.

Monday, June 15 2026, 00:00

The Program Is Still There: A Conservation Law for Program Discovery

Authors: Jorge Miguel Silva

Finding the shortest program that generates a sequence is uncomputable, and for six decades that fact has been mistaken for a wall around finding any generating program. It is not a wall but a price, and this paper measures it. For every algorithm that learns about a candidate program only through its score, a class spanning Levin search, evolutionary methods, simulated annealing, and the cross-entropy method, we define the coupling width of a search problem and prove an unconditional worst-case lower bound, exponential in that width with base one less than the domain size. From it follows a conservation law: structural knowledge injected into a search trades one for one against the search it removes, and their sum can never fall below the length of the program sought. Levin's 1973 upper bound and the lower bound proved here are the two ends of one conserved quantity, closing on each other as the instruction set grows. The only escape is to read a candidate's structure rather than its score, and its price, which we prove for generic targets, is incompleteness. A deterministic engine built on this theory recovers a generating program, certified by compressing its data and predicting an unseen continuation, for 2,383 of 3,914 sequences across four independent populations, including 244 of the 256 elementary cellular automata, with measured discovery cost rising along program length more than an order of magnitude inside the score-oracle worst case.

Authors: Jorge Miguel Silva

Finding the shortest program that generates a sequence is uncomputable, and for six decades that fact has been mistaken for a wall around finding any generating program. It is not a wall but a price, and this paper measures it. For every algorithm that learns about a candidate program only through its score, a class spanning Levin search, evolutionary methods, simulated annealing, and the cross-entropy method, we define the coupling width of a search problem and prove an unconditional worst-case lower bound, exponential in that width with base one less than the domain size. From it follows a conservation law: structural knowledge injected into a search trades one for one against the search it removes, and their sum can never fall below the length of the program sought. Levin's 1973 upper bound and the lower bound proved here are the two ends of one conserved quantity, closing on each other as the instruction set grows. The only escape is to read a candidate's structure rather than its score, and its price, which we prove for generic targets, is incompleteness. A deterministic engine built on this theory recovers a generating program, certified by compressing its data and predicting an unseen continuation, for 2,383 of 3,914 sequences across four independent populations, including 244 of the 256 elementary cellular automata, with measured discovery cost rising along program length more than an order of magnitude inside the score-oracle worst case.

Monday, June 15 2026, 00:00

Moving between 3-manifold triangulations is NP-hard

Authors: Stephan Tillmann, Anastasiia Tsvietkova

We show that \textsc{number of bistellar moves and sparse degree-two edge collapses for 3-sphere} is NP-hard. It follows that a similar problem for an arbitrary 3-manifold is NP-hard as well. This is the first NP-hardness result concerning moves between two triangulations of a 3-manifold.

Authors: Stephan Tillmann, Anastasiia Tsvietkova

We show that \textsc{number of bistellar moves and sparse degree-two edge collapses for 3-sphere} is NP-hard. It follows that a similar problem for an arbitrary 3-manifold is NP-hard as well. This is the first NP-hardness result concerning moves between two triangulations of a 3-manifold.

Monday, June 15 2026, 00:00

An Efficient Private Algorithm for Community Detection

Authors: Vincent Cohen-Addad, Alessandro Epasto, Haim Kaplan, Hanna Komlós, Silvio Lattanzi

In this paper, we study the community detection problem in the stochastic block model (SBM) under privacy constraints. We introduce private and highly efficient algorithms for exact community detection within the SBM framework. Our algorithms represent the first differentially private methods capable of achieving exact recovery in a wide range of model parameters with near-linear time and space complexity. This is a significant improvement over previous SBM recovery algorithms, which either required pseudo-polynomial time or a quadratic scaling of resources for a constant privacy budget. Central to our approach is the introduction of a new concept, adaptive disjoint-star algorithms. These algorithms efficiently explore the graph's structure by querying node degrees on edge-disjoint subgraphs. We demonstrate that this general class of algorithms inherently offers strong privacy guarantees, a result that potentially holds value beyond the scope of SBM community detection. Finally, in we perform an empirical analysis of our algorithms showing that they can scale exact recovery on graphs with two orders of magnitude more nodes than prior work.

Authors: Vincent Cohen-Addad, Alessandro Epasto, Haim Kaplan, Hanna Komlós, Silvio Lattanzi

In this paper, we study the community detection problem in the stochastic block model (SBM) under privacy constraints. We introduce private and highly efficient algorithms for exact community detection within the SBM framework. Our algorithms represent the first differentially private methods capable of achieving exact recovery in a wide range of model parameters with near-linear time and space complexity. This is a significant improvement over previous SBM recovery algorithms, which either required pseudo-polynomial time or a quadratic scaling of resources for a constant privacy budget. Central to our approach is the introduction of a new concept, adaptive disjoint-star algorithms. These algorithms efficiently explore the graph's structure by querying node degrees on edge-disjoint subgraphs. We demonstrate that this general class of algorithms inherently offers strong privacy guarantees, a result that potentially holds value beyond the scope of SBM community detection. Finally, in we perform an empirical analysis of our algorithms showing that they can scale exact recovery on graphs with two orders of magnitude more nodes than prior work.

Monday, June 15 2026, 00:00

On a Conjecture for Parameterized st-Orientations

Authors: Charalampos Papamanthou

MaxSTN and MinSTN -- proposed by Papamanthou and Tollis (TCS 2008, JGAA 2010) -- are two algorithms for producing $st$-orientations of biconnected graphs with long and short longest paths respectively. Based on extensive experiments on planar and non-planar graphs of up to 5,000 nodes, it was conjectured that $\ell_{\max} \geq \ell_{\min}$ for every biconnected graph $G$, where $\ell_{\max}$ and $\ell_{\min}$ denote the longest-path lengths of the two orientations. This paper disproves this conjecture by exhibiting a biconnected graph on 9 vertices for which MaxSTN yields $\ell_{\max}=6$ while MinSTN yields $\ell_{\min}=7$, regardless of how ties are broken in either algorithm.

Authors: Charalampos Papamanthou

MaxSTN and MinSTN -- proposed by Papamanthou and Tollis (TCS 2008, JGAA 2010) -- are two algorithms for producing $st$-orientations of biconnected graphs with long and short longest paths respectively. Based on extensive experiments on planar and non-planar graphs of up to 5,000 nodes, it was conjectured that $\ell_{\max} \geq \ell_{\min}$ for every biconnected graph $G$, where $\ell_{\max}$ and $\ell_{\min}$ denote the longest-path lengths of the two orientations. This paper disproves this conjecture by exhibiting a biconnected graph on 9 vertices for which MaxSTN yields $\ell_{\max}=6$ while MinSTN yields $\ell_{\min}=7$, regardless of how ties are broken in either algorithm.

Monday, June 15 2026, 00:00

Designing Efficient and Reachable Routes: The $k$-Step-Central Shortest Path Problem

Authors: Johnson Phosavanh, Dmytro Matsypura

Designing rapid transportation routes requires balancing efficiency and reachability. Shortest-path models ensure direct, cost-efficient routes but ignore coverage, while centrality-based approaches maximize accessibility but do not enforce operational constraints. We study the problem of selecting a shortest path that maximizes reachability, measured as the number of nodes within a fixed distance of the path. To do this, we introduce the $k$-Step-Central Shortest Path problem and analyse its structural properties. We show that optimal solutions on unweighted graphs can be found in polynomial time and propose an algorithm with a novel pruning rule. We also prove that the problem becomes NP-hard when edge weights are introduced. Additionally, we show that our algorithm can be used to solve the NP-hard problem of finding the closeness-central shortest path in a graph. We demonstrate the efficiency and scalability of our algorithm on synthetic and real-world networks with up to 2,000 nodes. Our results show that improving reachability can substitute for route expansion: increasing the reach of transit lines drastically increases their coverage with shorter routes. This suggests that investments in active transport infrastructure that improve reachability can be more effective than extending primary routes, providing a data-driven basis for allocating resources in network design.

Authors: Johnson Phosavanh, Dmytro Matsypura

Designing rapid transportation routes requires balancing efficiency and reachability. Shortest-path models ensure direct, cost-efficient routes but ignore coverage, while centrality-based approaches maximize accessibility but do not enforce operational constraints. We study the problem of selecting a shortest path that maximizes reachability, measured as the number of nodes within a fixed distance of the path. To do this, we introduce the $k$-Step-Central Shortest Path problem and analyse its structural properties. We show that optimal solutions on unweighted graphs can be found in polynomial time and propose an algorithm with a novel pruning rule. We also prove that the problem becomes NP-hard when edge weights are introduced. Additionally, we show that our algorithm can be used to solve the NP-hard problem of finding the closeness-central shortest path in a graph. We demonstrate the efficiency and scalability of our algorithm on synthetic and real-world networks with up to 2,000 nodes. Our results show that improving reachability can substitute for route expansion: increasing the reach of transit lines drastically increases their coverage with shorter routes. This suggests that investments in active transport infrastructure that improve reachability can be more effective than extending primary routes, providing a data-driven basis for allocating resources in network design.

Monday, June 15 2026, 00:00

Flood and Harvest: The Provable Necessity of Trivia for Generating Valuable Mathematics via the Lens of Language Generation in the Limit

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

AI systems coupled to proof assistants now generate formal mathematics at scale, and the gap between what a checker can verify and what a mathematician would value has become the binding constraint. We model the generation of valuable mathematics as nested language generation in the limit: a verifiable formal language $F$, accessed through a membership oracle (the proof checker), contains an unknown valuable language $H \in \mathcal{H}$ revealed only through an adversarial enumeration of a core $C \subseteq H$ of exact density $α$ (the literature). Every output is valuable ($\in H$), trivial ($\in F \setminus H$), or a hallucination ($\notin F$). We settle four questions. First, the verifier is not taste: the collections admitting generation with breadth are exactly those of the oracle-free model, characterized fiber-wise by Angluin's condition. Second, the verifier does buy sound coverage, covering all unseen valuable statements while asserting only valid ones: possible with it, impossible without it; it relocates unavoidable errors from false to trivial. Third, and centrally, a sharp dichotomy on the tight family: generators emitting finitely many trivia achieve optimal coverage $α/2$, while any infinite trivia allowance, even at vanishing rate, jumps the optimum to $1-α/2$ (both tight, for cores presented as the candidate intersection), and one generator attains both ends. The transition is in trivia count, not rate; the gap $1-α$ is the unrecorded mass. Fourth, both regimes instantiate in a compression model of mathematics. A perfect verifier cannot substitute for taste: the unbounded stream of correct-but-worthless statements is not an engineering accident but a provable necessity, since covering unrecorded valuable mathematics requires an infinite, but asymptotically negligible, stream of certified trivia.

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

AI systems coupled to proof assistants now generate formal mathematics at scale, and the gap between what a checker can verify and what a mathematician would value has become the binding constraint. We model the generation of valuable mathematics as nested language generation in the limit: a verifiable formal language $F$, accessed through a membership oracle (the proof checker), contains an unknown valuable language $H \in \mathcal{H}$ revealed only through an adversarial enumeration of a core $C \subseteq H$ of exact density $α$ (the literature). Every output is valuable ($\in H$), trivial ($\in F \setminus H$), or a hallucination ($\notin F$). We settle four questions. First, the verifier is not taste: the collections admitting generation with breadth are exactly those of the oracle-free model, characterized fiber-wise by Angluin's condition. Second, the verifier does buy sound coverage, covering all unseen valuable statements while asserting only valid ones: possible with it, impossible without it; it relocates unavoidable errors from false to trivial. Third, and centrally, a sharp dichotomy on the tight family: generators emitting finitely many trivia achieve optimal coverage $α/2$, while any infinite trivia allowance, even at vanishing rate, jumps the optimum to $1-α/2$ (both tight, for cores presented as the candidate intersection), and one generator attains both ends. The transition is in trivia count, not rate; the gap $1-α$ is the unrecorded mass. Fourth, both regimes instantiate in a compression model of mathematics. A perfect verifier cannot substitute for taste: the unbounded stream of correct-but-worthless statements is not an engineering accident but a provable necessity, since covering unrecorded valuable mathematics requires an infinite, but asymptotically negligible, stream of certified trivia.

Monday, June 15 2026, 00:00

Online Convex Optimization with Sublinear Noisy Probes

Authors: Simone Di Gregorio, Anupam Gupta, Stefano Leonardi, Matteo Russo

We study Online Convex Optimization (OCO) over a convex set $K\subseteq \mathbb R^d$, where in each round $t$ the learner selects $x_t\in K$ and then observes a convex loss $f_t:K\to[0,1]$, with the goal of minimizing regret to the best fixed decision in hindsight. We introduce a unified probing model that generalizes two recent lines of work: sublinear best-expert queries in the experts setting, and pairwise (comparison-based) feedback available every round in OCO. In our framework, the learner has a budget of $k\le T$ pairwise probes; on a probed round it may query two points and learn which one has smaller loss. Our main result shows that even a sublinear and noisy probe budget can provably improve worst-case regret in the full feedback OCO regime. With $k$ $δ$-noisy pairwise probes, we obtain: $ \text{Reg}_T \le O\left(\min\left\{\sqrt{dT\ln T},\; \frac{dT\ln T}{k|1-2δ|}\right\}\right) $, which is tight (up to logarithmic factors in $T$) across $T$, $k$ and $δ$. Specifically regarding the noise parameter $δ\in [0,1]$, the regret guarantee smoothly degrades as the oracle response approaches a coin flip, i.e., $δ$ is close to $\frac{1}{2}$. When applying the same techniques to a finite $K$ for the prediction with $d$ experts setting, the resulting rates are instead completely tight in all parameters, including $d$. Our analysis gives a streamlined treatment of pairwise probing in OCO by quantifying the benefit of probing via a variance reduction effect, combined with a second-order (variance-based) analysis of Continuous Exponential Weights.

Authors: Simone Di Gregorio, Anupam Gupta, Stefano Leonardi, Matteo Russo

We study Online Convex Optimization (OCO) over a convex set $K\subseteq \mathbb R^d$, where in each round $t$ the learner selects $x_t\in K$ and then observes a convex loss $f_t:K\to[0,1]$, with the goal of minimizing regret to the best fixed decision in hindsight. We introduce a unified probing model that generalizes two recent lines of work: sublinear best-expert queries in the experts setting, and pairwise (comparison-based) feedback available every round in OCO. In our framework, the learner has a budget of $k\le T$ pairwise probes; on a probed round it may query two points and learn which one has smaller loss. Our main result shows that even a sublinear and noisy probe budget can provably improve worst-case regret in the full feedback OCO regime. With $k$ $δ$-noisy pairwise probes, we obtain: $ \text{Reg}_T \le O\left(\min\left\{\sqrt{dT\ln T},\; \frac{dT\ln T}{k|1-2δ|}\right\}\right) $, which is tight (up to logarithmic factors in $T$) across $T$, $k$ and $δ$. Specifically regarding the noise parameter $δ\in [0,1]$, the regret guarantee smoothly degrades as the oracle response approaches a coin flip, i.e., $δ$ is close to $\frac{1}{2}$. When applying the same techniques to a finite $K$ for the prediction with $d$ experts setting, the resulting rates are instead completely tight in all parameters, including $d$. Our analysis gives a streamlined treatment of pairwise probing in OCO by quantifying the benefit of probing via a variance reduction effect, combined with a second-order (variance-based) analysis of Continuous Exponential Weights.

Monday, June 15 2026, 00:00

TR26-100 | Bipartite Matching is in NC | Rohit Gurjar, Roshan Raj, Thomas Thierauf, Abhranil Chatterjee, Sumanta Ghosh

from ECCC Papers

We show that the bipartite matching problem is in NC. We extend the result to weighted bipartite matching and the computation of the noncommutative rank of a symbolic matrix. In particular, this implies that the decision version of linear matroid intersection is in NC as well. The techniques are based on the polynomial method, inspired from a construction of subspace design by Guruswami and Kopparty (Combinatorica 2016).

Sunday, June 14 2026, 15:43

TR26-099 | Kikuchi Graphs of Random Hypergraphs are Approximately Johnson | Pravesh Kothari

from ECCC Papers

We prove that level-$\ell$ Kikuchi graphs of random $2r$-uniform hypergraphs spectrally approximate Kikuchi graph of the complete $2r$-uniform hypergraph at a sampling rate that is sharp up to a logarithmic factor, in the regime $r\leq \ell \leq n/2$. Our proof is based on the matrix Bernstein inequality, but, unlike prior works, we apply it to an appropriate collection of blocks of Johnson eigenspaces. Our analysis relies on a new, simple band-locality property for arbitrary Kikuchi graphs. As an application, we prove that the natural degree-$2\ell$ sum-of-squares relaxation for the Max $2r$-XOR problem is ``integral'' when the input is a planted noisy $2r$-XOR instance on a random hypergraph with $\gtrsim n \cdot (n/\ell)^{r-1} \log n$ hyperedges.

Sunday, June 14 2026, 13:05

TR26-098 | SNARGs for NP from Unprovability of Mathematical Theorems | Jiatu Li, YaoChing Hsieh, Abhishek Jain, Surya Mathialagan

from ECCC Papers

Modern cryptography relies on the intractability of computational problems. We present an approach to build cryptography from a new source of hardness: proving mathematical theorems. Our main result is a construction of succinct non-interactive arguments (SNARGs) for NP under standard derandomization (prBPP = prP) and cryptographic assumptions (LWE and SXDH), as well as a new, but natural assumption on the hardness of proving lower bounds in proof complexity. Specifically, our assumption states that it is impossible to prove, within a weak bounded arithmetic theory, the correctness of certifying hard tautologies against Extended Frege. This assumption is inspired by an informal mathematical challenge proposed by Razborov [Ann. Math. '15], and can be viewed as a generalization of an unconditional unprovability result due to Krají?ek and Pudlák [J. Symb. Log. '89]. Our construction is, in fact, a simple variant of the SNARG constructed by Jin, Kalai, Lombardi, and Vaikuntanathan [STOC '24]. While the soundness of their construction was only proven for a subclass of NP, we prove its soundness for all NP under our assumption. At the heart of our result is the key observation that cryptographic reasoning is simple in a formal sense: the security proof of most cryptographic primitives can be formalized in a weak theory. In particular, we show how to formalize the scheme of Jin et al. in Je?ábek's theory APC? [J. Symb. Log. '07] -- a weak theory in bounded arithmetic.

Sunday, June 14 2026, 05:45

The "fable" of Anthropic and the USG

from The Geomblog

News moves fast. 12 hours ago I was enjoying the demolition that the US put on Paraguay when I heard that Anthropic had shut down access to Fable and Mythos (their latest and most powerful models).

Since then, more news has surfaced about what went down, and I feel like it's a good exercise in understanding both the policy and psychodrama around AI today - with maybe even a moral or two like Aesop's .... FABLES (yes I'm going to keep making bad jokes and no you can't stop me)

Part 1: The event

Let's first lay out the facts of the matter. To the best of my knowledge, here's what transpired.

Some researchers (apparently at Amazon) uncovered ways to jailbreak Fable to (possibly) perform cybersecurity-related attacks.
Someone (apparently Andy Jassy) told the White House (or the Treasury Secretary) about this.
The WH and Anthropic had a back and forth on what needed to be done about this: Anthropic claimed these were not serious jalbreaks, and the WH said that they were and that Anthropic needed to either take down the model or something...
The WH then invoked export controls to demand that Anthropic block access to Fable/Mythos for foreign nationals (regardless of where they happen to be)
Anthropic blocked access entirely, arguing that they had no way of distinguishing foreign nationals from American citizens.

Now most of the reporting will focus on solidifying the facts of the matter (I hope) and will probably also focus on the drama. Drama is fun (don't get me wrong), but it can make thinking about policy really hard.
So let me lay out some of the questions about the drama that might be useful to have answered, but then try to focus on the bigger policy questions that come out of this.

What were these mysterious jailbreaks? This is actually an important question that will shape the policy response as well.
How were these jailbreaks flagged and sent up the chain, and why was the communication of the form "hey I called my buddy at the WH and told him stuff"?
What actually transpired in the discussion between the WH and Anthropic?

Part II: Clean-slate PolicyLet's pretend we are working in a vacuum for a second, and think about this with policy hats on, without worrying about the actual players (unrealistic I know, but a useful exercise).
The US Government is worried about powerful models allowing any user to generate (say) cybersecurity hacks that can compromise critical national infrastructure (for e.g the financial sector which is why the Treasury Secretary is paying close attention). These models are general purpose and have many uses, and the USG doesn't just want to shut them down entirely (we can debate that, but not right now).
What they'd like to do is have some way to monitor models for specific kinds of risks, before deployment, and also on a continuing basis. Maybe there's some kind of voluntary program where providers of powerful models give access to independent testers (for eg. some kind of Center for AI Security Standards and Innovation) who can identify risks, communicate these risks to the companies involved, and make sure that mitigations are put in place. It wouldn't be perfect, but it would be an ongoing process.
If this sounds familiar, it should. because a) it's how we do cybersecurity right now without any government involvement and b) it's a little bit of how the recent WH EO was constructed (there were other parts of the EO that are problematic, but again, not for now)
In other words, there's a way to do what the government wants if this is indeed what they want and companies are willing to cooperate (this is setting aside whether you and I want the government to do this. That's a different discussion)
Part III: (we know) DramaWell. that's all well and good. But I don't unfortunately live in a rationalist universe where I can write 20,000 word screeds on moreright.com and be "aligned" with everyone else. What's the reality here?
The first thing I want to emphasize is that drama loves a good guy (yes "guy") and a bad guy, and it's really tempting to first decide who's the bad guy and then decide the other one must be good. It would be really tempting to say for e.g "the Trump administration has no clue on AI and therefore Anthropic is the good guy", or "Tech companies are evillll and the administration is therefore doing the right thing".
Unfortunately (reporters please please pretty please pay attention), it's not that simple.
There are no innocent actors here.
This particular administration has always approached AI regulation in a very "we will say we are hands off but actually we are not but it's really about who's in favor and who's not that decides how we will act" way. Trying to retrofit logical policy actions onto that is hard, and this case is no different. The administration seems to operate its AI policy on some mix of favoritism, pique, and vengeance, and so it's hard to reconcile this reaction with the complete silence when (say) Grok was churning out CSAM and deepfake nonconsensual porn on demand while also being used within the department of war defense. For more on the internal incoherence of the administration's approach to AI, see Justin Hendrix's great analysis.
Anthropic is the "hero" of the moment, because their seeming adversary is the "bad guy" for so many in tech policy. But on the eve of the UFC fight on the WH lawn, keep in mind that these are all actors, and there's an audience. Anthropic is about to go public and make an insane amount of money for some people. It's in their interest to say "oh yeah our models are SCARY (good) and the best out there" and also say at the same time "Yeah your jailbreak is not that scary and we are fine and can release our systems". I don't doubt that there are people at Anthropic who genuinely believe such things, but Anthropic is a corporation (not a "lab") and is in the business of market control and profit.
Specifically, it is entirely possible that Fable is both a great improvement on Opus, and can do some questionable things better, and is also susceptible to the same jailbreaks and vulnerabilities as other models. It's possible it's not some special unicorn that is so dangerous we all have to trust in Anthropic's good intentions, but just the next incarnation of a product with many of the same weaknesses. We just don't know because Anthropic won't say, and won't actually allow for independent testing separately from the folks they want to give access to.
Part IV: So what should we do? This episode doesn't change many of the things we understand already about the contours of AI policy. And in fact it's dangerous to overindex on one episode - that tends to leads to a whack-a-mole approach to doing AI regulation that has been harmful in other settings.
1. We need to regulate the downstream risks and harms that come from the introduction of AI.
All this nonsense around "but but innovation" needs to stop. You can tell an argument is not very useful when it's been used over and over again for virtually every single sector of society over the past century, including all the currently regulated sectors that we don't want to loosen regulations on.
We need to do this 10 years ago. And we need to do this now. The AI industry is not some delicate hothouse flower that needs nurturing. It's a robust trillion dollar enterprise that's reshaping our world and will do so without our say so.
2. It's more effective to focus sector by sector.
Cybersecurity risks are concrete risks that we can evaluate in a focused way. And we can make use of the infrastructure and policy around cybersecurity to do so. Will this exact framework work for (say) threats to the electrical grid? probably not, and so we need a different "vertical" for understanding, evaluating, and mitigating risks in that sector. And so on.
3. You don't need to focus only on the tech: focus on the ecosystem of actors and safeguards currently in place
There's a lot of concern around the use of AI in medicine, and in the financial sector. But these are both heavily regulated sectors where there are already checks in place to make sure that the systems function as we want them to. Are they perfect? no. But it's easier to tweak an existing system of safeguards. Maybe AI is used to generate a new drug: but such a drug will need to go through regular clinical trials with real people (not synthetic!) in order to be put on the market. So focus on where AI might be compromising an existing system of governance, rather than assuming we need to regulate the model itself.
4. Testing testing testing (independently) To really assess the risks associated with the introduction of AI in different sectors, we need ... testing. Independent testing - not whatever blog posts the labs companies put out. But focused testing on specific issues, rather than general "capability testing". And we need to build and support the infrastructure for that. This is already too long to go on a rant about the decimation of the scientific research apparatus in the US courtesy of the administration, but yes, the decimation of the scientific research apparatus in the US will have a direct effect on our ability to test for risks and harms, and has to be part of any policy directions we explore.

By Suresh Venkatasubramanian

News moves fast. 12 hours ago I was enjoying the demolition that the US put on Paraguay when I heard that Anthropic had shut down access to Fable and Mythos (their latest and most powerful models).

Since then, more news has surfaced about what went down, and I feel like it's a good exercise in understanding both the policy and psychodrama around AI today - with maybe even a moral or two like Aesop's .... FABLES (yes I'm going to keep making bad jokes and no you can't stop me)

Part 1: The event

Let's first lay out the facts of the matter. To the best of my knowledge, here's what transpired.

Some researchers (apparently at Amazon) uncovered ways to jailbreak Fable to (possibly) perform cybersecurity-related attacks.
Someone (apparently Andy Jassy) told the White House (or the Treasury Secretary) about this.
The WH and Anthropic had a back and forth on what needed to be done about this: Anthropic claimed these were not serious jalbreaks, and the WH said that they were and that Anthropic needed to either take down the model or something...
The WH then invoked export controls to demand that Anthropic block access to Fable/Mythos for foreign nationals (regardless of where they happen to be)
Anthropic blocked access entirely, arguing that they had no way of distinguishing foreign nationals from American citizens.

Now most of the reporting will focus on solidifying the facts of the matter (I hope) and will probably also focus on the drama. Drama is fun (don't get me wrong), but it can make thinking about policy really hard.

So let me lay out some of the questions about the drama that might be useful to have answered, but then try to focus on the bigger policy questions that come out of this.

What were these mysterious jailbreaks? This is actually an important question that will shape the policy response as well.
How were these jailbreaks flagged and sent up the chain, and why was the communication of the form "hey I called my buddy at the WH and told him stuff"?
What actually transpired in the discussion between the WH and Anthropic?

Part II: Clean-slate Policy

Let's pretend we are working in a vacuum for a second, and think about this with policy hats on, without worrying about the actual players (unrealistic I know, but a useful exercise).

The US Government is worried about powerful models allowing any user to generate (say) cybersecurity hacks that can compromise critical national infrastructure (for e.g the financial sector which is why the Treasury Secretary is paying close attention). These models are general purpose and have many uses, and the USG doesn't just want to shut them down entirely (we can debate that, but not right now).

What they'd like to do is have some way to monitor models for specific kinds of risks, before deployment, and also on a continuing basis. Maybe there's some kind of voluntary program where providers of powerful models give access to independent testers (for eg. some kind of Center for AI Security Standards and Innovation) who can identify risks, communicate these risks to the companies involved, and make sure that mitigations are put in place. It wouldn't be perfect, but it would be an ongoing process.

If this sounds familiar, it should. because a) it's how we do cybersecurity right now without any government involvement and b) it's a little bit of how the recent WH EO was constructed (there were other parts of the EO that are problematic, but again, not for now)

In other words, there's a way to do what the government wants if this is indeed what they want and companies are willing to cooperate (this is setting aside whether you and I want the government to do this. That's a different discussion)

Part III: (we know) Drama

Well. that's all well and good. But I don't unfortunately live in a rationalist universe where I can write 20,000 word screeds on moreright.com and be "aligned" with everyone else. What's the reality here?

The first thing I want to emphasize is that drama loves a good guy (yes "guy") and a bad guy, and it's really tempting to first decide who's the bad guy and then decide the other one must be good. It would be really tempting to say for e.g "the Trump administration has no clue on AI and therefore Anthropic is the good guy", or "Tech companies are evillll and the administration is therefore doing the right thing".

Unfortunately (reporters please please pretty please pay attention), it's not that simple.

There are no innocent actors here.

This particular administration has always approached AI regulation in a very "we will say we are hands off but actually we are not but it's really about who's in favor and who's not that decides how we will act" way. Trying to retrofit logical policy actions onto that is hard, and this case is no different. The administration seems to operate its AI policy on some mix of favoritism, pique, and vengeance, and so it's hard to reconcile this reaction with the complete silence when (say) Grok was churning out CSAM and deepfake nonconsensual porn on demand while also being used within the department of war defense. For more on the internal incoherence of the administration's approach to AI, see Justin Hendrix's great analysis.

Anthropic is the "hero" of the moment, because their seeming adversary is the "bad guy" for so many in tech policy. But on the eve of the UFC fight on the WH lawn, keep in mind that these are all actors, and there's an audience. Anthropic is about to go public and make an insane amount of money for some people. It's in their interest to say "oh yeah our models are SCARY (good) and the best out there" and also say at the same time "Yeah your jailbreak is not that scary and we are fine and can release our systems". I don't doubt that there are people at Anthropic who genuinely believe such things, but Anthropic is a corporation (not a "lab") and is in the business of market control and profit.

Specifically, it is entirely possible that Fable is both a great improvement on Opus, and can do some questionable things better, and is also susceptible to the same jailbreaks and vulnerabilities as other models. It's possible it's not some special unicorn that is so dangerous we all have to trust in Anthropic's good intentions, but just the next incarnation of a product with many of the same weaknesses. We just don't know because Anthropic won't say, and won't actually allow for independent testing separately from the folks they want to give access to.

Part IV: So what should we do?

This episode doesn't change many of the things we understand already about the contours of AI policy. And in fact it's dangerous to overindex on one episode - that tends to leads to a whack-a-mole approach to doing AI regulation that has been harmful in other settings.

1. We need to regulate the downstream risks and harms that come from the introduction of AI.

All this nonsense around "but but innovation" needs to stop. You can tell an argument is not very useful when it's been used over and over again for virtually every single sector of society over the past century, including all the currently regulated sectors that we don't want to loosen regulations on.

We need to do this 10 years ago. And we need to do this now. The AI industry is not some delicate hothouse flower that needs nurturing. It's a robust trillion dollar enterprise that's reshaping our world and will do so without our say so.

2. It's more effective to focus sector by sector.

Cybersecurity risks are concrete risks that we can evaluate in a focused way. And we can make use of the infrastructure and policy around cybersecurity to do so. Will this exact framework work for (say) threats to the electrical grid? probably not, and so we need a different "vertical" for understanding, evaluating, and mitigating risks in that sector. And so on.

3. You don't need to focus only on the tech: focus on the ecosystem of actors and safeguards currently in place

There's a lot of concern around the use of AI in medicine, and in the financial sector. But these are both heavily regulated sectors where there are already checks in place to make sure that the systems function as we want them to. Are they perfect? no. But it's easier to tweak an existing system of safeguards. Maybe AI is used to generate a new drug: but such a drug will need to go through regular clinical trials with real people (not synthetic!) in order to be put on the market. So focus on where AI might be compromising an existing system of governance, rather than assuming we need to regulate the model itself.

4. Testing testing testing (independently)

To really assess the risks associated with the introduction of AI in different sectors, we need ... testing. Independent testing - not whatever blog posts the labs companies put out. But focused testing on specific issues, rather than general "capability testing". And we need to build and support the infrastructure for that. This is already too long to go on a rant about the decimation of the scientific research apparatus in the US courtesy of the administration, but yes, the decimation of the scientific research apparatus in the US will have a direct effect on our ability to test for risks and harms, and has to be part of any policy directions we explore.

By Suresh Venkatasubramanian

Saturday, June 13 2026, 20:51

Congratulations, Dr. Sridhar!

from David Eppstein

This past week was the final exam week for our spring term, and in it we also held the doctoral defense of another Ph.D. student, Vinesh Sridhar (advised by Mike Goodrich). Vinesh organized his thesis in an unusually symmetric way, with two parts on computing with noisy primitives, two parts on in-place algorithms, two parts on sequential algorithms, and two parts on parallel algorithms, in four combinations (noisy sequential, noisy parallel, in-place sequential, in-place parallel).

I’ve previously written here about Vinesh’s work with Mike and me on computational geometry algorithms with noisy primitives, which we published in WADS 2025. In this work, following a random walk back and forth along a search path in a history DAG or other geometric data structure (and occasionally, choosing a false step and then backtracking) allows algorithms based on this idea to avoid the logarithmic time penalty of repeating each noisy query for enough repetitions to be sure that it is accurate. Being sure means “with high probability”: the failure probability should be inversely polynomial in the input size.

Vinesh and Mike published a parallel follow-up to this at CCCG 2025, “Optimal parallel algorithms for convex hulls in 2d and 3d under noisy primitive operations”. A difficulty here is that, for a divide-and-conquer algorithm, a failure probability that is inverse polynomial in the size of a small subproblem may not be inverse polynomial in the much larger input size. To work around this, Vinesh and Mike used the idea of “failure sweeping”, in which one divides the input into polynomially-many subproblems, lets some of them fail with a probability that is larger than the target failure probability (but still small enough that with high probability there are few failures). Then, one cleans up the failed subproblems in a second pass using a fast and more reliable parallel algorithm with a greater total work bound that is cancelled by the smaller number of subproblems.

The in-place part of Vinesh’s thesis focused on in-place sorting algorithms, where one is allowed only $O(1)$ extra words of memory beyond the array being sorted. The classical choice for this is heapsort, which can be implemented to run in-place and takes time $O(n\log n)$ to sort an $n$-item array. This is optimal in the worst case, but many other sorting algorithms go beyond worst case time complexity to run more quickly for inputs that are not completely unsorted. An important class of these are entropy-sensitive sorting algorithms. Their runtime on input sequences that can be partitioned into $r$ sorted runs of size $n_i$ is $O(n(H+1))$, where the entropy $H$ is defined by

\[\mathrm{H}=-\sum_{i=1}^r \frac{n_i}{n}\log_2 \frac{n_i}{n}.\]

This can be done by finding runs and then repeatedly merging the shortest two, but the merged runs may not be consecutive in the input sequence, making an in-place merge problematic. Instead, Timsort and several similar alternatives build a stack of runs in a left-right scan of the input, while doing so merging pairs of short runs near the top of the stack. This leaves a sequence of sorted runs on the stack whose sizes grow roughly according to a geometric sequence, which can be repeatedly popped and merged. The geometric growth of the stack means that the stack itself can be stored in $O(\log n)$ space, but while small this is not small enough to be in-place. Vinesh finds two strategies for reducing the space in this family of algorithms. In the “walking” strategy, only the top $O(1)$ stack elements are maintained; the next ones below that are rediscovered one at a time, as they become needed, by a sequential search within each run. In the “jumping” strategy, some elements within each run are placed out of order, in order to encode extra information to speed up the walking algorithm. Vinesh shows that most entropy-sensitive merging algorithms (but not Timsort itself) can be made in-place by walking, and that all known ones can be made in-place by jumping. He published this work (joint with Ofek Gila and Mike Goodrich) as “How to sort in a refrigerator: Simple entropy-sensitive strictly in-place sorting algorithms” in LATIN 2026.

The final part of the thesis comes from a paper with the colorful title “Raiders of the lost log: Synchronous parallel in-place models and algorithms” (with Goodrich in the 28th Workshop on Advances in Parallel and Distributed Computational Models, 2026, and selected as an “outstanding paper” for APDCM 2027). It’s not currently free online but Vinesh and Mike promise to make an arXiv version soon. This part involves PRAM model parallel machines where the only shared memory is the input and each parallel processor has only a bounded amount of private memory. The title comes from a technique inspired by the first scene of the first Indiana Jones movie, in which Jones (unsuccessfully) swaps a sandbag for a booby-trapped gold figurine. In their algorithmic technique, Vinesh and Mike have the parallel processors each swap their working memory for a piece of the input data that they control, freeing up enough shared memory to perform their algorithms. They apply this technique not only to in-place sorting, but also to convex hulls, parallel primitives such as prefix sums and tree contraction, and the generation of random permutations.

The defense was presented very smoothly and clearly, and Vinesh’s many results (including several papers not included in the thesis) made for an easy pass of his defense. Congratulations, Vinesh!

(Discuss on Mastodon)

By David Eppstein

Saturday, June 13 2026, 18:21

Announcing WoLA 2026 in Boston

from Property Testing Review

The 10th edition of WoLA, the Workshop on Local Algorithms, will be taking place on August 16-18, 2026 at at Boston University, Boston, MA, just before APPROX/RANDOM! For those unfamiliar with WoLA: Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have […]

The 10th edition of WoLA, the Workshop on Local Algorithms, will be taking place on August 16-18, 2026 at at Boston University, Boston, MA, just before APPROX/RANDOM!

For those unfamiliar with WoLA:

Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have been studied in a number of areas in theoretical computer science and mathematics. Some of these areas include sublinear-time algorithms, distributed algorithms, inference in large networks and graphical models. These communities have similar goals but a variety of approaches, techniques, and methods. This workshop is aimed at fostering dialogue and cross-pollination of ideas between the various communities.

You are all invited! For more on (free) registration, how to submit a poster or propose a talk, list of invited speakers, and local arrangements, see the website.

Don’t miss it! Not only is WoLA a truly enjoyable and interesting event, showcasing exciting new results and directions of research, it’s also one centered around an incredibly welcoming and collegial (and fun!) community of researchers. But that’s not all! Expect a particularly amazing edition this year, as this is the 10th anniversary edition of WoLA, and it is being held on the top floor of the new Computer and Data Sciences building at BU, with breathtaking views of Boston.

From Futurama: the Professor, saying "Good news, everyone"

Program Committee: Maryam Aliakbarpour (Rice University), Sepehr Assadi (University of Waterloo; Chair), Eric Blais (University of Waterloo), Yi-Jun Chang (National University of Singapore), Talya Eden (Bar Ilan University), Nathan Harms (University of British Columbia), Akash Kumar (IIT Bombay), Yannic Maus (TU Graz), Sofya Raskhodnikova (Boston University; Local Chair)), Chen Wang (Rensselaer Polytechnic Institute).

By Clement Canonne

Saturday, June 13 2026, 10:14

Language Models and Automated Reification

from Ben Recht

A new piece in The Ideas Letter with Leif Weatherby and Tyler Shoemaker.

Leif Weatherby, Tyler Shoemaker, and I have a new essay out today in The Ideas Letter about the creation of reality through pseudoscience, religion, and psychosis. Of course, it’s mostly about AI. Starting with the bizarre appearance of Antropic co-founder and mechanistic interpretability zealot Chris Olah at the side of Pope Leo as he read out his encyclical, we explore how commercial large language models automate the creation of reality.

The term of art for the process by which abstract concepts are made into material objects is reification. Marxist theorists think of the reification of social relations, where qualitative things like actions become commodified. This is the process by which labor becomes objectified and priced, and subsequently alienated from the person who does the work. Distinctly, historians and philosophers of science think of reification in terms of how correlational associations are named and become real through coordinated research programs. When your biggest companies all claim to be doing research, you can see how these two become one, with coordinated research becoming commodity itself.

LLMs are not only generated by a technological oligarchy, but also introduce a new twist into the process of reality generation. LLMs automate reification. LLMs are designed to produce explanations for us. We skip the steps in the collective creation of scientific concepts (aka thinking and arguing) and let LLMs do it for us through their linguistic association. LLMs entice you to skip the step of interpretation of outputs. Why not just ask Claude what it thinks?

As an illustrative example, we discuss Stephen J Gould’s historical analysis of the g factor in psychometrics research. In the social sciences, everything is correlated with everything. If you run some sort of correlational analysis on any data set, you’ll find something. Gould describes the process through which psychometricians decided that the correlational quantity that linked different measures of intelligence—the g factor—was real, and how they created a whole scientific research program to reinforce the reality of the g factor.

You know who still loves factor analysis? Mechanistic interpretability researchers. AI researchers have found themselves enamored with psychometrics as they work to prove their LLM toys are conscious. But they have new technology that Charles Spearman and his colleagues didn’t have a century ago: the LLMs themselves! Whereas 20th-century psychometrists had to think about causal stories to explain their strong correlational findings, interpretability researchers can automate this process. They can give an LLM the output of a factor analysis and ask it to explain the factors. Since it returns answers in natural language, this feels like discovery even though you have offloaded the process that would have been done by thinking about it to a machine. This process sets off a loop in which scientists and citizens alike give iterative credence to concepts generated by correlating text. We write:

“Models, in other words, kick off an associative chain of ideas by effectively auto-labeling queries. It’s like taking the principal components derived from that data about oak trees, boat speeds, cat whiskers, and Letterboxd reviews, and asking ChatGPT: “What do each of these artifacts mean?” ChatGPT will respond—and then keep the conversation going, bringing in more associations that more or less fit. But as we have already argued, this doesn’t only happen to amateurs who are easy to pathologize. How is this different from the standard methodology of interpretability research? In both the cases that might be dismissed as psychosis and the ones celebrated at AI conferences, interaction with LLMs induces mental friction. They create a feeling that discovery is there. By elaborating on what you put in through a context that the model has trained on, it is able to make connections that feel both correct and expansive, filling in the area around your thought—simulating the feeling that you are having a new thought. The model helps you refine the obscurity of your prompt through a chain of associations, and suddenly you have something. This is reification at work. And when the next link in a chain of thoughts comes along, it becomes hard to resist prompting the model again.”

LLMs are built to automate a complex web of reification. They are designed to tell us what we want to hear. As we write, “Trained on an enormous corpus of human writing, speech, and code, and tuned to refine responses around context and memory as user interactions unroll, a model of this kind is designed to provide the sense that one’s expectation is being exceeded.”

Artificial intelligence is a bizarre technology that participates in its own mythmaking. Anthropic is the most deeply invested in telling outrageous stories about its products, but no one in this space is innocent. As I’ve written before, I think that benchmarks get an unnecessarily bad rap. I certainly agree that you can’t “benchmark general purpose technology.” I agree that maxing out benchmark scores doesn’t mean a product will be better received by customers. But when we move away from benchmarking in artificial intelligence, we get stuck in storytelling. LLMs are designed and intended to convince us that their stories are real. When backed by a turbocharged capitalist engine, the reification becomes inevitable. Stories become commodities. Those commodities sell like hotcakes. And there is nothing more real than when the number goes up.

I’ll leave you there, as I need to go check on the value of my SpaceX shares. Read the whole article and let us know what you think.

Subscribe now

By Ben Recht

Friday, June 12 2026, 14:15

Workshop on Local Algorithms

from CS Theory Events

August 16-18, 2026 Boston University, Boston, USA www.local-algorithms.com/WOLA2026/ Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have been studied in a number of areas in theoretical computer science and mathematics. Some of these areas include sublinear-time algorithms, distributed algorithms, inference in … Continue reading Workshop on Local Algorithms

By shacharlovett

August 16-18, 2026 Boston University, Boston, USA https://www.local-algorithms.com/WOLA2026/ Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have been studied in a number of areas in theoretical computer science and mathematics. Some of these areas include sublinear-time algorithms, distributed algorithms, inference in … Continue reading Workshop on Local Algorithms

By shacharlovett

Friday, June 12 2026, 01:44

Extended Frege proofs, circuits and rewriting

Authors: Jan Krajicek

Inspired by a statement about Extended Frege proof systems by Jain and Jin (FOCS 2022) we prove that: - there is a p-time binary relation $\approx$ between circuits that implies their logical equivalence, - the relation $\approx$ implies that each of the two circuits can be rewritten into the other one by possibly deleting some gates and adding at most seven new gates, - if the equivalence $C \equiv D$ has a size $s$ proof in an Extended Frege or a Circuit Frege proof system then there is a chain of circuits $E_i$ $$ C = E_0 \approx \dots \approx E_t = D $$ with $t \le s^{O(1)}$.

Authors: Jan Krajicek

Inspired by a statement about Extended Frege proof systems by Jain and Jin (FOCS 2022) we prove that: - there is a p-time binary relation $\approx$ between circuits that implies their logical equivalence, - the relation $\approx$ implies that each of the two circuits can be rewritten into the other one by possibly deleting some gates and adding at most seven new gates, - if the equivalence $C \equiv D$ has a size $s$ proof in an Extended Frege or a Circuit Frege proof system then there is a chain of circuits $E_i$ $$ C = E_0 \approx \dots \approx E_t = D $$ with $t \le s^{O(1)}$.

Friday, June 12 2026, 00:00

Token Complexity Theory for AI-Augmented Computing

Authors: Jie Wang

AI-augmented computing delegates natural language queries, code generation requests, and other open-ended tasks to a cluster of AI models that processes queries and generates responses. This paradigm introduces a resource dimension that neither classical time nor space complexity captures: the cost of sending queries to and receiving responses from such a cluster. We introduce token complexity, a formal resource measure defined as the minimum expected token cost to achieve a specified level of output quality on a task, and develop a taxonomy classifying AI systems by the strength of their probabilistic properties. We develop token complexity within the framework of AI-Oracle Turing machines, in which a probabilistic Turing machine interacts with a stochastic oracle via dedicated query and response tapes. We prove basic theorems establishing that token complexity behaves as expected: monotonicity (higher quality costs more tokens), convexity (quality improvements become progressively more expensive), price sensitivity (small price changes produce bounded cost changes), and price-relativity of task ordering (the token complexity ordering of tasks can reverse depending on the query-to-response cost ratio). We prove that the complexity frontier, defined as the set of all feasible resource bounds in tokens, time, and space, is non-empty, upward-closed, and convex.

Authors: Jie Wang

AI-augmented computing delegates natural language queries, code generation requests, and other open-ended tasks to a cluster of AI models that processes queries and generates responses. This paradigm introduces a resource dimension that neither classical time nor space complexity captures: the cost of sending queries to and receiving responses from such a cluster. We introduce token complexity, a formal resource measure defined as the minimum expected token cost to achieve a specified level of output quality on a task, and develop a taxonomy classifying AI systems by the strength of their probabilistic properties. We develop token complexity within the framework of AI-Oracle Turing machines, in which a probabilistic Turing machine interacts with a stochastic oracle via dedicated query and response tapes. We prove basic theorems establishing that token complexity behaves as expected: monotonicity (higher quality costs more tokens), convexity (quality improvements become progressively more expensive), price sensitivity (small price changes produce bounded cost changes), and price-relativity of task ordering (the token complexity ordering of tasks can reverse depending on the query-to-response cost ratio). We prove that the complexity frontier, defined as the set of all feasible resource bounds in tokens, time, and space, is non-empty, upward-closed, and convex.

Friday, June 12 2026, 00:00

The Switching Lemma shows what the Switching Lemma cannot prove: an unconditional natural-proofs barrier

Authors: Bruno Loff, Suhail Sherif, Navid Talebanfard, Francesca Ugazio

Razborov and Rudich (JCSS'97) observed that all known lower-bound proofs follow a certain pattern: when showing that a function $F$ is hard, along the way the proof provides us with a distinguisher, namely, an efficient algorithm which can distinguish easy functions from random functions. They called such lower-bound proofs natural proofs. They then showed a natural-proofs barrier: under standard cryptographic assumptions, natural proofs cannot show superpolynomial lower-bounds against Boolean circuits. Along similar lines it can be shown that under a suitable cryptographic assumption, natural proofs cannot significantly improve the current state-of-the-art lower bound against constant depth circuits (AC0). The state of the art, using Håstad's Switching Lemma (SL), is $2^{n^{1/(d-1)}}$ for depth-$d$ circuits, and (conditionally) no natural proof can prove lower bounds of $2^{n^{c/d}}$ for some large constant $c$. In this paper we revisit the natural-proofs barrier from an $\textit{unconditional}$ perspective. We focus on AC0-natural proofs, i.e. proofs whose distinguishers are computable by AC0 circuits. Razborov and Rudich observed that lower bounds based on SL are AC0-natural. We show that this is true for most known lower-bound techniques against constant-depth circuits. We then establish an unconditional barrier for such proofs. By localizing the Trevisan--Xue pseudorandom generator, we are able to show that no AC0-natural proof can prove a lower bound greater than $2^{n^{7/(d-5)}}$ against depth-$d$ circuits. This is in the same quantitative regime as the SL frontier which instead has $1/(d-1)$ in the power of $n$. The proof has a striking self-referential aspect: the proof of security of the Trevisan--Xue generator crucially relies on SL, and so SL has been used to show that AC0-natural proofs, such as SL itself, cannot prove AC0 lower bounds better than that of SL.

Authors: Bruno Loff, Suhail Sherif, Navid Talebanfard, Francesca Ugazio

Razborov and Rudich (JCSS'97) observed that all known lower-bound proofs follow a certain pattern: when showing that a function $F$ is hard, along the way the proof provides us with a distinguisher, namely, an efficient algorithm which can distinguish easy functions from random functions. They called such lower-bound proofs natural proofs. They then showed a natural-proofs barrier: under standard cryptographic assumptions, natural proofs cannot show superpolynomial lower-bounds against Boolean circuits. Along similar lines it can be shown that under a suitable cryptographic assumption, natural proofs cannot significantly improve the current state-of-the-art lower bound against constant depth circuits (AC0). The state of the art, using Håstad's Switching Lemma (SL), is $2^{n^{1/(d-1)}}$ for depth-$d$ circuits, and (conditionally) no natural proof can prove lower bounds of $2^{n^{c/d}}$ for some large constant $c$. In this paper we revisit the natural-proofs barrier from an $\textit{unconditional}$ perspective. We focus on AC0-natural proofs, i.e. proofs whose distinguishers are computable by AC0 circuits. Razborov and Rudich observed that lower bounds based on SL are AC0-natural. We show that this is true for most known lower-bound techniques against constant-depth circuits. We then establish an unconditional barrier for such proofs. By localizing the Trevisan--Xue pseudorandom generator, we are able to show that no AC0-natural proof can prove a lower bound greater than $2^{n^{7/(d-5)}}$ against depth-$d$ circuits. This is in the same quantitative regime as the SL frontier which instead has $1/(d-1)$ in the power of $n$. The proof has a striking self-referential aspect: the proof of security of the Trevisan--Xue generator crucially relies on SL, and so SL has been used to show that AC0-natural proofs, such as SL itself, cannot prove AC0 lower bounds better than that of SL.

Friday, June 12 2026, 00:00

A near-quadratic lower bound on the border determinantal complexity of $\sum_i x_i^n$ via conormal specialization

Authors: Karthik Sheshadri

The border determinantal complexity $\dcb(f)$ of a polynomial $f$ is the least $m$ such that $f$ is a limit of determinants of $m\times m$ matrices of affine-linear forms. We prove that for every $n\ge3$, over $\CC$, \[ \dcb\Big(\sum_{i=1}^n x_i^n\Big)\ \ge\ \frac{(n-1)^2}{4e}, \qquad \sdcb\Big(\sum_{i=1}^n x_i^n\Big)\ \ge\ \frac{(n-1)^2}{2e} \] in the ordinary and symmetric models respectively; both match the known $O(n^2)$ upper bounds up to the constant. To our knowledge these are the first border determinantal lower bounds for an explicit family that are superlinear in the number of variables: the known quadratic border bound for the permanent reads the \emph{dimension} of the dual variety and is linear in its number of variables, whereas we transfer the dual \emph{degree}. The proof has two ingredients. The first is an unconditional bound on the slot-$(n-2)$ conormal multidegree of the multiplicity-one Gauss-graph cycle of an arbitrary affine-linear determinant -- singular, reducible, and non-reduced fibers allowed -- by a multihomogeneous Bézout count of a lifted kernel incidence. The second is a specialization argument: along any degeneration $\det A_c\to\sum_ix_i^n$, the flat limit of these Gauss-graph cycles contains the conormal variety of the Fermat cone with positive coefficient. A cone-shift identity converts that conormal multidegree into the classical dual degree $n(n-1)^{n-2}$ of the smooth Fermat hypersurface, and an $(n-1)$-st root yields the quadratic bound. The exact lower bounds of the author's companion manuscripts follow as corollaries.

Authors: Karthik Sheshadri

The border determinantal complexity $\dcb(f)$ of a polynomial $f$ is the least $m$ such that $f$ is a limit of determinants of $m\times m$ matrices of affine-linear forms. We prove that for every $n\ge3$, over $\CC$, \[ \dcb\Big(\sum_{i=1}^n x_i^n\Big)\ \ge\ \frac{(n-1)^2}{4e}, \qquad \sdcb\Big(\sum_{i=1}^n x_i^n\Big)\ \ge\ \frac{(n-1)^2}{2e} \] in the ordinary and symmetric models respectively; both match the known $O(n^2)$ upper bounds up to the constant. To our knowledge these are the first border determinantal lower bounds for an explicit family that are superlinear in the number of variables: the known quadratic border bound for the permanent reads the \emph{dimension} of the dual variety and is linear in its number of variables, whereas we transfer the dual \emph{degree}. The proof has two ingredients. The first is an unconditional bound on the slot-$(n-2)$ conormal multidegree of the multiplicity-one Gauss-graph cycle of an arbitrary affine-linear determinant -- singular, reducible, and non-reduced fibers allowed -- by a multihomogeneous Bézout count of a lifted kernel incidence. The second is a specialization argument: along any degeneration $\det A_c\to\sum_ix_i^n$, the flat limit of these Gauss-graph cycles contains the conormal variety of the Fermat cone with positive coefficient. A cone-shift identity converts that conormal multidegree into the classical dual degree $n(n-1)^{n-2}$ of the smooth Fermat hypersurface, and an $(n-1)$-st root yields the quadratic bound. The exact lower bounds of the author's companion manuscripts follow as corollaries.

Friday, June 12 2026, 00:00

On the Counting Sequence of Z-convex Polyominoes

Authors: Luca Castelli, Paolo Massazza

The degree of convexity of a convex polyomino P is the smallest integer k such that any two cells of P can be joined by a monotone path inside P with at most k changes of direction. In this paper, we present a set of formulas and equations that are the basis of a C++ program that allows you to compute the longest counting sequence known to date (with respect to the area) of convex polyominoes of degree of convexity at most 2

Authors: Luca Castelli, Paolo Massazza

The degree of convexity of a convex polyomino P is the smallest integer k such that any two cells of P can be joined by a monotone path inside P with at most k changes of direction. In this paper, we present a set of formulas and equations that are the basis of a C++ program that allows you to compute the longest counting sequence known to date (with respect to the area) of convex polyominoes of degree of convexity at most 2

Friday, June 12 2026, 00:00

A Calculus of Apartness over Separoids: Effective Convex Representation, Stratified Conservativity, and the Complexity of Entailment

Authors: Faruk Alpay, Baris Basaran

Every finite family of compact convex bodies in Euclidean space induces an apartness relation between disjoint index sets: two sets are apart when the convex hulls of the corresponding unions are disjoint. This paper studies the finite theory obtained by taking apartness as the primitive relation. Its basic laws are symmetry, bilateral subsumption, and vacuity, equivalently the separation-polarity form of acyclic separoids. The main contribution is an effective rational realization theorem with uniform margins and the exact consequence theory it supports. Every finite apartness separoid is realized by rational polytopes whose coordinates are indexed by maximal separations. Maximal separations and minimal Radon partitions can be enumerated from a full table, generators, or a membership oracle; the coordinate values have controlled bit height; and each coordinate records a readable certificate of one maximal separation. The realization separates every apart pair with clearance at least 2, remains correct under outer parallel enlargement by any radius below 1, and yields full-dimensional convex bodies after thickening. The distance-function layer records standard convex-analytic stability through Lipschitz comparison, monotonicity under inclusion, and outer parallel bodies. On the logical side, positive entailment is exactly one-premise subsumption. Boolean consequence over Euclidean scenes is sound, complete, and decidable; satisfiability is NP-complete, validity is coNP-complete, and positive entailment is linear for sorted encodings. A stratification theorem shows that Boolean reasoning introduces no new atomic apartness beyond separoid closure. Fixed-dimensional consequence relations form a strictly decreasing hierarchy that stabilizes in dimension n minus 1 for n sites.

Authors: Faruk Alpay, Baris Basaran

Every finite family of compact convex bodies in Euclidean space induces an apartness relation between disjoint index sets: two sets are apart when the convex hulls of the corresponding unions are disjoint. This paper studies the finite theory obtained by taking apartness as the primitive relation. Its basic laws are symmetry, bilateral subsumption, and vacuity, equivalently the separation-polarity form of acyclic separoids. The main contribution is an effective rational realization theorem with uniform margins and the exact consequence theory it supports. Every finite apartness separoid is realized by rational polytopes whose coordinates are indexed by maximal separations. Maximal separations and minimal Radon partitions can be enumerated from a full table, generators, or a membership oracle; the coordinate values have controlled bit height; and each coordinate records a readable certificate of one maximal separation. The realization separates every apart pair with clearance at least 2, remains correct under outer parallel enlargement by any radius below 1, and yields full-dimensional convex bodies after thickening. The distance-function layer records standard convex-analytic stability through Lipschitz comparison, monotonicity under inclusion, and outer parallel bodies. On the logical side, positive entailment is exactly one-premise subsumption. Boolean consequence over Euclidean scenes is sound, complete, and decidable; satisfiability is NP-complete, validity is coNP-complete, and positive entailment is linear for sorted encodings. A stratification theorem shows that Boolean reasoning introduces no new atomic apartness beyond separoid closure. Fixed-dimensional consequence relations form a strictly decreasing hierarchy that stabilizes in dimension n minus 1 for n sites.

Friday, June 12 2026, 00:00

Sketching Intersection Profiles: A Simple Proof and Three Applications

Authors: Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Alessandro Panconesi, Erasmo Tani, Andrew Tomkins

In this work we settle the complexity of three sketching problems. (i) We show that sketching vertex neighborhood sizes in graphs requires $Ω(n^2)$ bits, standing in sharp contrast to the $\tilde{O}(n)$ complexity of sketching edge cuts. (ii) We obtain tight lower and upper bounds of $\tildeΘ(n^2)$ for sketching coverage functions with additive and multiplicative errors. (iii) We prove an $Ω(n^2)$ lower bound for sketching Random Utility Models under the $\ell_\infty$-norm, improving upon the previous $Ω(n \log n)$ bound and matching a known upper bound to within logarithmic factors. These bounds are obtained through a connection with the problem of sketching the intersection profile of a distribution $D$ on $2^{[n]}$. Specifically, we seek a succinct data structure that, for any query set $S \subseteq [n]$, approximates the quantity $\Pr_{T \sim D}[T \cap S \neq \varnothing]$ to within a small constant additive error. One can obtain lower bounds for this latter problem directly from known results about the itemset frequency estimation problem in databases for which tight bounds are known. As an additional contribution, we also provide an alternative proof for the intersection profile sketching lower bound, in the setting in which the accuracy parameter is constant. This proof relies solely on elementary probability avoiding the heavier machinery used in previous proofs.

Authors: Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Alessandro Panconesi, Erasmo Tani, Andrew Tomkins

In this work we settle the complexity of three sketching problems. (i) We show that sketching vertex neighborhood sizes in graphs requires $Ω(n^2)$ bits, standing in sharp contrast to the $\tilde{O}(n)$ complexity of sketching edge cuts. (ii) We obtain tight lower and upper bounds of $\tildeΘ(n^2)$ for sketching coverage functions with additive and multiplicative errors. (iii) We prove an $Ω(n^2)$ lower bound for sketching Random Utility Models under the $\ell_\infty$-norm, improving upon the previous $Ω(n \log n)$ bound and matching a known upper bound to within logarithmic factors. These bounds are obtained through a connection with the problem of sketching the intersection profile of a distribution $D$ on $2^{[n]}$. Specifically, we seek a succinct data structure that, for any query set $S \subseteq [n]$, approximates the quantity $\Pr_{T \sim D}[T \cap S \neq \varnothing]$ to within a small constant additive error. One can obtain lower bounds for this latter problem directly from known results about the itemset frequency estimation problem in databases for which tight bounds are known. As an additional contribution, we also provide an alternative proof for the intersection profile sketching lower bound, in the setting in which the accuracy parameter is constant. This proof relies solely on elementary probability avoiding the heavier machinery used in previous proofs.

Friday, June 12 2026, 00:00

Temporal Conductance and Bounds on the Voter Model for Dynamic Networks

Authors: Tatiana Rocha Avila, Holger Dell, John Lapinskas

The voter model is a classical stochastic process that models how opinions might spread through a network: at each step, every node lazily adopts the opinion of a random neighbour; eventually all nodes share the same opinion (consensus). Stronger connectivity should yield faster consensus. Berenbrink, Giakkoupis, Kermarrec, and Mallmann-Trenn (ICALP 2016) make this precise via the network's conductance: if the network has $m$ edges, minimum degree $d_{\min}$, and conductance at least $φ$, then the voter model reaches consensus in expected $O(m/(d_{\min}φ))$ steps. Their results extend to dynamic networks with fixed vertex degrees by considering the network's conductance at each time step. We introduce temporal conductance $Φ$, a more general connectivity measure for dynamic networks. Unlike static conductance, which collapses to $0$ whenever some snapshot is disconnected, $Φ$ captures connectivity through edges that appear at different times. We generalise the results of Berenbrink et al. from static conductance to temporal conductance, showing that the expected consensus time of the standard voter model is at most $O(m/(d_{\min}Φ))$. Moreover, we prove that this bound is tight up to constant factors. We expect temporal conductance to be a useful primitive for analysing other dynamics on temporal networks, and potentially time-inhomogeneous Markov chains more generally.

Authors: Tatiana Rocha Avila, Holger Dell, John Lapinskas

The voter model is a classical stochastic process that models how opinions might spread through a network: at each step, every node lazily adopts the opinion of a random neighbour; eventually all nodes share the same opinion (consensus). Stronger connectivity should yield faster consensus. Berenbrink, Giakkoupis, Kermarrec, and Mallmann-Trenn (ICALP 2016) make this precise via the network's conductance: if the network has $m$ edges, minimum degree $d_{\min}$, and conductance at least $φ$, then the voter model reaches consensus in expected $O(m/(d_{\min}φ))$ steps. Their results extend to dynamic networks with fixed vertex degrees by considering the network's conductance at each time step. We introduce temporal conductance $Φ$, a more general connectivity measure for dynamic networks. Unlike static conductance, which collapses to $0$ whenever some snapshot is disconnected, $Φ$ captures connectivity through edges that appear at different times. We generalise the results of Berenbrink et al. from static conductance to temporal conductance, showing that the expected consensus time of the standard voter model is at most $O(m/(d_{\min}Φ))$. Moreover, we prove that this bound is tight up to constant factors. We expect temporal conductance to be a useful primitive for analysing other dynamics on temporal networks, and potentially time-inhomogeneous Markov chains more generally.

Friday, June 12 2026, 00:00

The $(1 + 1)$-EA in Dynamic Environments

Authors: Georg Hasebe, Johannes Lengler, Raghu Raman Ravi

We study the $(1 + 1)$-EA in dynamic linear environments, where in every generation selection is performed with respect to a freshly sampled linear function with positive weights. We consider the Dynamic Binary Value problem, where each generation uses a uniformly random permutation of $1,2,4,\dots,2^{n-1}$, and a Uniform weight variant, where the weights are drawn independently from $\mathrm{Unif}(0,1)$. Both of them have recently been integrated into the IOHprofiler platform and empirically studied. For both models we prove a sharp threshold in the mutation parameter $χ$ for mutation rate $χ/n$. Below the threshold, the expected optimisation time is $\mathcal{O}(n\log n)$, whereas above it the runtime becomes $2^{Ω(n)}$. For the Dynamic Binary Value problem in the exponential regime, we also quantify at what distance from the optimum the optimisation process stagnates. We show that there is a second threshold: a distance that is efficiently reached, but reaching any smaller distance takes exponential time. This quantifies and proves previous empirical findings.

Authors: Georg Hasebe, Johannes Lengler, Raghu Raman Ravi

We study the $(1 + 1)$-EA in dynamic linear environments, where in every generation selection is performed with respect to a freshly sampled linear function with positive weights. We consider the Dynamic Binary Value problem, where each generation uses a uniformly random permutation of $1,2,4,\dots,2^{n-1}$, and a Uniform weight variant, where the weights are drawn independently from $\mathrm{Unif}(0,1)$. Both of them have recently been integrated into the IOHprofiler platform and empirically studied. For both models we prove a sharp threshold in the mutation parameter $χ$ for mutation rate $χ/n$. Below the threshold, the expected optimisation time is $\mathcal{O}(n\log n)$, whereas above it the runtime becomes $2^{Ω(n)}$. For the Dynamic Binary Value problem in the exponential regime, we also quantify at what distance from the optimum the optimisation process stagnates. We show that there is a second threshold: a distance that is efficiently reached, but reaching any smaller distance takes exponential time. This quantifies and proves previous empirical findings.

Friday, June 12 2026, 00:00

Split Tallies: A Discrete Certificate Calculus for Auditing Dynamic Ordered Sets in Constant Memory

Authors: Faruk Alpay, Levent Sarioglu

We study retrospective auditing for dynamic ordered sets maintained by an untrusted party. A passive auditor watches insert, delete, membership, predecessor, successor, min, and max operations, stores five machine words and a flag, and receives a constant-size public tally record per operation. At audit time the maintainer discloses the claimed live vacant intervals. The method represents order semantics by maximal gaps: gaps are born, cited, consumed, and timestamped, while two hidden field accumulators test equality of the birth and consumption ledgers. Honest executions are accepted with probability one. If any answer in a T-operation session is wrong, acceptance occurs with probability at most (4T+1)/p over one secret field element, against computationally unbounded maintainers. We prove that deterministic and visible-coin auditors require linear state, and that removing the timestamp rule permits an exact replay forgery. A leaf-oriented (2,4)-tree implements the maintainer in O(log n) worst-case time per operation with one extra word per element, and its rebalancing events admit an auditable O(m) envelope over m updates. Checkpoint audits compose with additive error.

Authors: Faruk Alpay, Levent Sarioglu

We study retrospective auditing for dynamic ordered sets maintained by an untrusted party. A passive auditor watches insert, delete, membership, predecessor, successor, min, and max operations, stores five machine words and a flag, and receives a constant-size public tally record per operation. At audit time the maintainer discloses the claimed live vacant intervals. The method represents order semantics by maximal gaps: gaps are born, cited, consumed, and timestamped, while two hidden field accumulators test equality of the birth and consumption ledgers. Honest executions are accepted with probability one. If any answer in a T-operation session is wrong, acceptance occurs with probability at most (4T+1)/p over one secret field element, against computationally unbounded maintainers. We prove that deterministic and visible-coin auditors require linear state, and that removing the timestamp rule permits an exact replay forgery. A leaf-oriented (2,4)-tree implements the maintainer in O(log n) worst-case time per operation with one extra word per element, and its rebalancing events admit an auditable O(m) envelope over m updates. Checkpoint audits compose with additive error.

Friday, June 12 2026, 00:00

Exhaustive Generation of Genus-One Knot and Link Diagrams via Maps on the Torus

Authors: Alexander Omelchenko

We present an algorithmic framework for the exhaustive generation and tabulation of knot and link diagrams on the thickened torus T^2 x I, based on the theory of maps on surfaces. Cellular 4-regular torus projections are encoded by permutation pairs (alpha, sigma), and unsensed equivalence classes are enumerated completely and without duplication via canonical representatives. Crossing assignments, local diagram-level reductions, and the generalized Kauffman-type bracket are formulated entirely within the same permutation model. The pipeline is validated against published genus-one classifications for crossing numbers N <= 5 and then extended to N = 6, 7, 8, producing, to our knowledge, the first complete genus-one tabulation at these crossing numbers under the stated comparison conventions. The resulting dataset contains more than 33,000 knot and link types. Besides the tables, the computation yields proved structural facts, including a parity statement for the a-span of the bracket and a sharp upper bound N-1 for the number of bigon faces in a 4-regular torus map. It also suggests several conjectures, among them a formula for the maximum number of straight-ahead components, the absence of equi-quadrilateral knot projections, and a 4N upper bound for the genus-one bracket span.

Authors: Alexander Omelchenko

We present an algorithmic framework for the exhaustive generation and tabulation of knot and link diagrams on the thickened torus T^2 x I, based on the theory of maps on surfaces. Cellular 4-regular torus projections are encoded by permutation pairs (alpha, sigma), and unsensed equivalence classes are enumerated completely and without duplication via canonical representatives. Crossing assignments, local diagram-level reductions, and the generalized Kauffman-type bracket are formulated entirely within the same permutation model. The pipeline is validated against published genus-one classifications for crossing numbers N <= 5 and then extended to N = 6, 7, 8, producing, to our knowledge, the first complete genus-one tabulation at these crossing numbers under the stated comparison conventions. The resulting dataset contains more than 33,000 knot and link types. Besides the tables, the computation yields proved structural facts, including a parity statement for the a-span of the bracket and a sharp upper bound N-1 for the number of bigon faces in a 4-regular torus map. It also suggests several conjectures, among them a formula for the maximum number of straight-ahead components, the absence of equi-quadrilateral knot projections, and a 4N upper bound for the genus-one bracket span.

Friday, June 12 2026, 00:00

(Un)ranking Permutation Classes

Authors: Nathanaël Hassler, Vincent Vajnovszki

Permutations avoiding a pattern of length three are enumerated by the Catalan numbers. In this work, we present methods for ranking and unranking such permutations in lexicographic or colexicographic order.

Authors: Nathanaël Hassler, Vincent Vajnovszki

Permutations avoiding a pattern of length three are enumerated by the Catalan numbers. In this work, we present methods for ranking and unranking such permutations in lexicographic or colexicographic order.

Friday, June 12 2026, 00:00

Random Generation of $k$-coloured Motzkin Paths

Authors: Elena Barcucci, Antonio Bernini, Stefano Bilotta, Renzo Pinzani

We study k-coloured Motzkin paths, namely Motzkin paths in which horizontal steps can be coloured in k different ways, and investigate their connection with the number of prefixes ending at odd height from both an analytical and a combinatorial point of view. Moreover, the combinatorial approach provides a random generation algorithm for k-coloured Motzkin paths in linear-time.

Authors: Elena Barcucci, Antonio Bernini, Stefano Bilotta, Renzo Pinzani

We study k-coloured Motzkin paths, namely Motzkin paths in which horizontal steps can be coloured in k different ways, and investigate their connection with the number of prefixes ending at odd height from both an analytical and a combinatorial point of view. Moreover, the combinatorial approach provides a random generation algorithm for k-coloured Motzkin paths in linear-time.

Friday, June 12 2026, 00:00

Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling

Authors: Kaito Baba, Evripidis Bampis, Giorgos Mitropoulos

Recently, Antoniadis et al. (ICLR 2025) proposed a framework for incorporating predictions to approximate NP-hard selection problems. Despite its simplicity, this approach tightly matches theoretical lower bounds, making its generalization highly compelling. We address an open question raised in the work of Antoniadis et al., concerning the extension of this approach to other important problems outside the class of selection problems, such as scheduling. We develop a learning-augmented algorithm for the makespan minimization problem on unrelated machines, denoted by $R\|C_{\max}$. By using predictions of heavy job assignments, we achieve a polynomial-time $(1+\varepsilon)$-approximation for accurate predictions that smoothly degrades to a worst-case 2-approximation as the error increases. We conclude our work with an empirical analysis of our method.

Authors: Kaito Baba, Evripidis Bampis, Giorgos Mitropoulos

Recently, Antoniadis et al. (ICLR 2025) proposed a framework for incorporating predictions to approximate NP-hard selection problems. Despite its simplicity, this approach tightly matches theoretical lower bounds, making its generalization highly compelling. We address an open question raised in the work of Antoniadis et al., concerning the extension of this approach to other important problems outside the class of selection problems, such as scheduling. We develop a learning-augmented algorithm for the makespan minimization problem on unrelated machines, denoted by $R\|C_{\max}$. By using predictions of heavy job assignments, we achieve a polynomial-time $(1+\varepsilon)$-approximation for accurate predictions that smoothly degrades to a worst-case 2-approximation as the error increases. We conclude our work with an empirical analysis of our method.

Friday, June 12 2026, 00:00

Binary Search Variants: A Comprehensive Analysis

Authors: Ali Dasdan

Binary search is deceptively simple in concept yet notoriously difficult to implement correctly. This paper presents a unified treatment of binary search: five core variants, six derived query functions, and four standard library implementations (BSD, glibc, Java, C++ STL), each with consistent notation, loop invariants, and analysis. We introduce bsearch_ultimate, a combined search that subsumes all variants in a single call. Every algorithm is provided as synchronized Python code, Dafny formal proof, and pseudocode. All implementations are validated by over 9,500 tests and 21 Dafny formal verifications; an additional six deliberately faulty implementations demonstrate common bug categories and Dafny's ability to detect them. We also provide memorable rules linking boundary choices to loop conditions and update formulas.

Authors: Ali Dasdan

Binary search is deceptively simple in concept yet notoriously difficult to implement correctly. This paper presents a unified treatment of binary search: five core variants, six derived query functions, and four standard library implementations (BSD, glibc, Java, C++ STL), each with consistent notation, loop invariants, and analysis. We introduce bsearch_ultimate, a combined search that subsumes all variants in a single call. Every algorithm is provided as synchronized Python code, Dafny formal proof, and pseudocode. All implementations are validated by over 9,500 tests and 21 Dafny formal verifications; an additional six deliberately faulty implementations demonstrate common bug categories and Dafny's ability to detect them. We also provide memorable rules linking boundary choices to loop conditions and update formulas.

Friday, June 12 2026, 00:00

Diffusion-Network Alignment: An Efficient Algorithm and Explicit Probability Bounds

Authors: Ziao Wang, Lei Ying

This paper studies a variation of the classic network alignment problem, named diffusion-network alignment. The goal is to align the vertices of a rooted diffusion tree to the vertices of a network, where the diffusion tree could be from a communication trace or contact tracing, and the network could be an online or offline social network. Different from the classic network alignment where both networks are fully observed, this model captures the information asymmetry of two networks. To solve this problem, this paper presents an efficient algorithm based on tree correlation tests to extract alignment information from local neighborhoods. We analyze the performance of the algorithm in the sparse graph regime and show that with high probability, all matched pairs are correct. Furthermore, for each vertex on the diffusion tree, this paper establishes an explicit lower bound on the probability that the vertex is correctly matched. These lower bounds are depth-dependent and increase as vertices get closer to the root.

Authors: Ziao Wang, Lei Ying

This paper studies a variation of the classic network alignment problem, named diffusion-network alignment. The goal is to align the vertices of a rooted diffusion tree to the vertices of a network, where the diffusion tree could be from a communication trace or contact tracing, and the network could be an online or offline social network. Different from the classic network alignment where both networks are fully observed, this model captures the information asymmetry of two networks. To solve this problem, this paper presents an efficient algorithm based on tree correlation tests to extract alignment information from local neighborhoods. We analyze the performance of the algorithm in the sparse graph regime and show that with high probability, all matched pairs are correct. Furthermore, for each vertex on the diffusion tree, this paper establishes an explicit lower bound on the probability that the vertex is correctly matched. These lower bounds are depth-dependent and increase as vertices get closer to the root.

Friday, June 12 2026, 00:00

Adaptive Weighted Averaging

Authors: Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit

We study the problem of selecting the largest among $n$ unknown values $x_1,\dots,x_n$ given only a single unbiased estimate $y_i$ for each $x_i$. We design strategies that are simultaneously admissible (not uniformly dominated by any other strategy) and also never worse than a given baseline such as uniform random selection. We provide an application to stochastic optimization, where we obtain online-to-batch conversion bounds with a desirable "no-compromise" guarantee: they are never worse than standard random iterate selection, and yet can be significantly better in benign settings.

Authors: Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit

We study the problem of selecting the largest among $n$ unknown values $x_1,\dots,x_n$ given only a single unbiased estimate $y_i$ for each $x_i$. We design strategies that are simultaneously admissible (not uniformly dominated by any other strategy) and also never worse than a given baseline such as uniform random selection. We provide an application to stochastic optimization, where we obtain online-to-batch conversion bounds with a desirable "no-compromise" guarantee: they are never worse than standard random iterate selection, and yet can be significantly better in benign settings.

Friday, June 12 2026, 00:00

A unified complexity bound for logconcave sampling

Authors: Yunbum Kook, Santosh S. Vempala

We give a simple, unified, and nearly tight bound for sampling arbitrary logconcave distributions from a warm start using the In-and-Out algorithm along with exponential lifting. The main new ingredient in the analysis is an improved bound on the Poincaré constant of a lifted distribution. As a consequence, the resulting convergence rate is nearly tight for both constrained settings (e.g., Gaussian restricted to a convex body) and well-conditioned settings (e.g., strongly logconcave and smooth densities).

Authors: Yunbum Kook, Santosh S. Vempala

We give a simple, unified, and nearly tight bound for sampling arbitrary logconcave distributions from a warm start using the In-and-Out algorithm along with exponential lifting. The main new ingredient in the analysis is an improved bound on the Poincaré constant of a lifted distribution. As a consequence, the resulting convergence rate is nearly tight for both constrained settings (e.g., Gaussian restricted to a convex body) and well-conditioned settings (e.g., strongly logconcave and smooth densities).

Friday, June 12 2026, 00:00

Random Proposals: A Softmax-Based Local-Improvement Framework for Maximum Weighted Matching

Authors: Ahmed M. Alzuhair, Ahmed Alherz

We propose a randomized local-improvement algorithm for the Maximum Weighted Matching (MWM) problem. Our method introduces a softmax-based biased sampling mechanism that achieves local $\varepsilon$-dominance and yields an expected $\frac{1}{2}-\varepsilon$ approximation ratio. We prove convergence guarantees and show that the algorithm runs in $O\!\left(m\log(1/\varepsilon)/p_{\min}\right)$ time, where $p_{\min}$ is the minimum softmax proposal probability over all edges; under mild conditions on the bias parameter and weight range, this simplifies to $O(m\log(1/\varepsilon))$. The framework provides a tunable tradeoff between convergence speed and approximation quality.

Authors: Ahmed M. Alzuhair, Ahmed Alherz

We propose a randomized local-improvement algorithm for the Maximum Weighted Matching (MWM) problem. Our method introduces a softmax-based biased sampling mechanism that achieves local $\varepsilon$-dominance and yields an expected $\frac{1}{2}-\varepsilon$ approximation ratio. We prove convergence guarantees and show that the algorithm runs in $O\!\left(m\log(1/\varepsilon)/p_{\min}\right)$ time, where $p_{\min}$ is the minimum softmax proposal probability over all edges; under mild conditions on the bias parameter and weight range, this simplifies to $O(m\log(1/\varepsilon))$. The framework provides a tunable tradeoff between convergence speed and approximation quality.

Friday, June 12 2026, 00:00

Learning with Simulators: No Regret in a Computationally Bounded World

Authors: Sasha Voitovych, Abhishek Shetty, Noah Golowich, Alexander Rakhlin

Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some proxy thereof) of the data-generating process, while results for strongly dependent data are far more limited. Towards addressing this gap, we introduce the framework of simulatable processes, where the learner has access to a simulator that approximates the distribution generating the data (which may be an arbitrarily complex and dependent process). Surprisingly, given access to such a simulator, we show that we can recover the same learning guarantees as in the classical setting with independent data, namely, error bounds that depend on the VC dimension. Further, we use this framework to study the power of conditional sampling and show strict statistical and computational advantages in this setting. As a highlight of our framework, we exhibit a single algorithm that simultaneously learns any given VC class under all processes samplable in bounded polynomial time, with regret controlled by the time-bounded Kolmogorov complexity of the process. This provides a significant conceptual broadening of the classical PAC model.

Authors: Sasha Voitovych, Abhishek Shetty, Noah Golowich, Alexander Rakhlin

Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some proxy thereof) of the data-generating process, while results for strongly dependent data are far more limited. Towards addressing this gap, we introduce the framework of simulatable processes, where the learner has access to a simulator that approximates the distribution generating the data (which may be an arbitrarily complex and dependent process). Surprisingly, given access to such a simulator, we show that we can recover the same learning guarantees as in the classical setting with independent data, namely, error bounds that depend on the VC dimension. Further, we use this framework to study the power of conditional sampling and show strict statistical and computational advantages in this setting. As a highlight of our framework, we exhibit a single algorithm that simultaneously learns any given VC class under all processes samplable in bounded polynomial time, with regret controlled by the time-bounded Kolmogorov complexity of the process. This provides a significant conceptual broadening of the classical PAC model.

Friday, June 12 2026, 00:00

Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry

Authors: Maximilian J. Kramer, Carsten Schubert, Jens Eisert

For general max-k-XORSAT with $k \geq 3$, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless $\mathsf{P} = \mathsf{NP}$: approximating beyond the random-assignment value of $1/2$ is $\mathsf{NP}$-hard. The picture changes when each variable appears in at most $D$ constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order $1/\sqrt{D}$. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the corresponding algorithmic guarantee was established by Barak et al. Whether the same holds over general finite fields, and what it implies for quantum algorithms, has not been established. We make this connection explicit and extend the hardness to max-E$k$-LINSAT$(q,r)$ with bounded degree $D$ and over arbitrary finite fields $\mathbb{F}_q$, proving that it is $\mathsf{NP}$-hard to exceed $r/q + \mathcal{O}_{q,r}(1/\sqrt{D})$. These results provide the complexity-theoretic benchmark for the bounded-degree instances targeted by decoded quantum interferometry (DQI), QAOA, and classical heuristics. Any quantum advantage on bounded-degree instances is therefore confined to the constant prefactor. We further show that in the context of DQI and on $(k,D)$-regular instances, this prefactor is sensitive to the nature of the decoder: DQI with classical decoders faces an information-theoretic $1/\sqrt{D \log D}$ barrier that prevents it from matching the hardness scaling, while DQI with quantum decoders is compatible with the $1/\sqrt{D}$ scaling -- identifying quantum decoding as the key ingredient for matching the complexity-theoretic scaling with DQI.

Authors: Maximilian J. Kramer, Carsten Schubert, Jens Eisert

For general max-k-XORSAT with $k \geq 3$, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless $\mathsf{P} = \mathsf{NP}$: approximating beyond the random-assignment value of $1/2$ is $\mathsf{NP}$-hard. The picture changes when each variable appears in at most $D$ constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order $1/\sqrt{D}$. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the corresponding algorithmic guarantee was established by Barak et al. Whether the same holds over general finite fields, and what it implies for quantum algorithms, has not been established. We make this connection explicit and extend the hardness to max-E$k$-LINSAT$(q,r)$ with bounded degree $D$ and over arbitrary finite fields $\mathbb{F}_q$, proving that it is $\mathsf{NP}$-hard to exceed $r/q + \mathcal{O}_{q,r}(1/\sqrt{D})$. These results provide the complexity-theoretic benchmark for the bounded-degree instances targeted by decoded quantum interferometry (DQI), QAOA, and classical heuristics. Any quantum advantage on bounded-degree instances is therefore confined to the constant prefactor. We further show that in the context of DQI and on $(k,D)$-regular instances, this prefactor is sensitive to the nature of the decoder: DQI with classical decoders faces an information-theoretic $1/\sqrt{D \log D}$ barrier that prevents it from matching the hardness scaling, while DQI with quantum decoders is compatible with the $1/\sqrt{D}$ scaling -- identifying quantum decoding as the key ingredient for matching the complexity-theoretic scaling with DQI.

Friday, June 12 2026, 00:00

Testing Bipartiteness in Logarithmic Rounds

Authors: Yumou Fei, Ronitt Rubinfeld

The seminal work of Goldreich and Ron (\textit{Combinatorica, 1999}) showed that bipartiteness of bounded-degree graphs can be tested using $O(\sqrt{n\log n})$ random walks of length $O(\log^{6} n)$. In this work, we improve their result by showing that $O(\sqrt{n})$ random walks of length $O(\log n)$ suffice. As a corollary, we obtain an $O(\log n)$-pass, $O(\sqrt{n}\log n)$-space streaming algorithm for testing bipartiteness, whose pass complexity is optimal in light of a recent lower bound of Fei, Minzer, and Wang (\textit{arXiv, 2026}). Our proof takes a different approach from that of Goldreich and Ron, using the semidefinite programming relaxation for Max-Cut introduced by Goemans and Williamson (\textit{J. ACM, 1995}).

Authors: Yumou Fei, Ronitt Rubinfeld

The seminal work of Goldreich and Ron (\textit{Combinatorica, 1999}) showed that bipartiteness of bounded-degree graphs can be tested using $O(\sqrt{n\log n})$ random walks of length $O(\log^{6} n)$. In this work, we improve their result by showing that $O(\sqrt{n})$ random walks of length $O(\log n)$ suffice. As a corollary, we obtain an $O(\log n)$-pass, $O(\sqrt{n}\log n)$-space streaming algorithm for testing bipartiteness, whose pass complexity is optimal in light of a recent lower bound of Fei, Minzer, and Wang (\textit{arXiv, 2026}). Our proof takes a different approach from that of Goldreich and Ron, using the semidefinite programming relaxation for Max-Cut introduced by Goemans and Williamson (\textit{J. ACM, 1995}).

Friday, June 12 2026, 00:00

Differentially Private Hierarchical Heavy Hitters

Authors: Ari Biswas, Graham Cormode, Yaron Kanza, Divesh Srivastava, Zhengyi Zhou

The task of finding _Hierarchical_ Heavy Hitters (HHH) was introduced by Cormode et al. [VLDB 2003] as a generalisation of the heavy hitter problem. While finding HHH in data streams has been studied extensively, the question of releasing HHH when the underlying data is private remains unexplored. In this paper, we study differentially private HHH release in both the streaming and non-streaming setting. In the non-streaming setting, we show the surprising result that the relative error in estimating the residual count for any prefix is independent of the height of the hierarchy and the number of heavy hitters in the stream. Meanwhile, in the streaming setting, although the exact version of HHH has low global sensitivity (as counting queries are 1-sensitive), the approximation functions due to streaming have high global sensitivity, linear in the available space. Despite this obstacle, we show that the absolute error for estimating frequencies in the steaming setting is independent of the available space.

Authors: Ari Biswas, Graham Cormode, Yaron Kanza, Divesh Srivastava, Zhengyi Zhou

The task of finding _Hierarchical_ Heavy Hitters (HHH) was introduced by Cormode et al. [VLDB 2003] as a generalisation of the heavy hitter problem. While finding HHH in data streams has been studied extensively, the question of releasing HHH when the underlying data is private remains unexplored. In this paper, we study differentially private HHH release in both the streaming and non-streaming setting. In the non-streaming setting, we show the surprising result that the relative error in estimating the residual count for any prefix is independent of the height of the hierarchy and the number of heavy hitters in the stream. Meanwhile, in the streaming setting, although the exact version of HHH has low global sensitivity (as counting queries are 1-sensitive), the approximation functions due to streaming have high global sensitivity, linear in the available space. Despite this obstacle, we show that the absolute error for estimating frequencies in the steaming setting is independent of the available space.

Friday, June 12 2026, 00:00

Now it is a great time to study whatever computer science will be in five years

from Emanuele Viola

Enrollment in computer science is declining, out of fear that AI will wipe out much of the demand for software engineers. So here are the jobs of the future: In 2008, when I was on the job market, computer science was at its nadir. The people behind the doors I was knocking on told me […]

Enrollment in computer science is declining, out of fear that AI will wipe out much of the demand for software engineers. So here are the jobs of the future:

Real estate agent. Indeed, it will be pretty hard for AI to steal their added value: zero.
Driver. We will always need a human to shuttle people to airports and drive food trucks coast to coast, obviously.
Banker. Nothing can beat the personal touch of a slender banker, all smiles and a nice suit, meeting you in a brick-and-mortar branch to tell you which buttons to push on your phone — the service courtesy of your account fees.
Electrician. So you can clean the vents in the data centers. If you are lucky, you get to install solar panels.

In 2008, when I was on the job market, computer science was at its nadir. The people behind the doors I was knocking on told me kids were told to study biology and law instead. What happened instead is that people entering the field precisely at that point were going to graduate at a very good time.

By Manu

Thursday, June 11 2026, 22:08

A Five-Plane Reference Architecture for Runtime Governance of Production AI Agents

Authors: Krti Tallam

Enterprise security was built to govern data boundaries: the protected surface was data at rest and in transit, and the controls -- access control, data-loss prevention, perimeter inspection -- governed crossings of that boundary. Production AI agents dissolve this assumption. An agent reads context, calls tools, invokes connectors, and modifies systems of record on an enterprise's behalf, so risk moves inside the workflow, into sequences of individually-permitted actions that may transform a business process no one authorized. Existing policy engines do not extend to this regime: they evaluate request-time decisions against atomic principals, where agentic systems require stateful evaluation against composite principals whose authority attenuates through delegation chains. We present a reference architecture for the runtime governance of production agents, built from four composable primitives: a five-plane decomposition (a reasoning plane that adjudicates intent, and four enforcement planes -- network, identity, endpoint, data -- that realize the decision), stop-anywhere mediation, composite principals with capability attenuation, and audit as a structured evidence substrate. We define a taxonomy of six interruption primitives that generalize allow and deny, state and argue for four correctness invariants, and demonstrate the foreclosure of seven production-agent threats across five concrete workflows. A reference implementation of the policy-engine core supplies measured evidence: attenuation correctness and evidence reconstructability hold on every trial, adjudication runs in single-digit microseconds, and the audit substrate's tamper-evidence behaves exactly as designed. We are explicit about scope: the architecture governs delegated action, not model behavior, and a full-system evaluation against a live agent benchmark is the invited next step.

Authors: Krti Tallam

Enterprise security was built to govern data boundaries: the protected surface was data at rest and in transit, and the controls -- access control, data-loss prevention, perimeter inspection -- governed crossings of that boundary. Production AI agents dissolve this assumption. An agent reads context, calls tools, invokes connectors, and modifies systems of record on an enterprise's behalf, so risk moves inside the workflow, into sequences of individually-permitted actions that may transform a business process no one authorized. Existing policy engines do not extend to this regime: they evaluate request-time decisions against atomic principals, where agentic systems require stateful evaluation against composite principals whose authority attenuates through delegation chains. We present a reference architecture for the runtime governance of production agents, built from four composable primitives: a five-plane decomposition (a reasoning plane that adjudicates intent, and four enforcement planes -- network, identity, endpoint, data -- that realize the decision), stop-anywhere mediation, composite principals with capability attenuation, and audit as a structured evidence substrate. We define a taxonomy of six interruption primitives that generalize allow and deny, state and argue for four correctness invariants, and demonstrate the foreclosure of seven production-agent threats across five concrete workflows. A reference implementation of the policy-engine core supplies measured evidence: attenuation correctness and evidence reconstructability hold on every trial, adjudication runs in single-digit microseconds, and the audit substrate's tamper-evidence behaves exactly as designed. We are explicit about scope: the architecture governs delegated action, not model behavior, and a full-system evaluation against a live agent benchmark is the invited next step.

Thursday, June 11 2026, 00:00

Output-sensitive Sparse Polynomial GCD over Finite Fields is NP-hard

Authors: Ruichen Qiu, Yichuan Cao, Qiao-Long Huang, Ruyong Feng, Xiao-Shan Gao

In this paper, we prove that output-sensitive sparse polynomial GCD computation over finite fields is NP-hard under BPP many-one reduction. More precisely, for two sparse univariate polynomials $f,g$ with finite field coefficients, there exists no randomized algorithm to compute $\mathrm{gcd}(f,g)$, which is polynomial-time in the sizes of $f,g,\gcd(f,g)$ under the standard complexity assumption $\mathrm{NP}\nsubseteq\mathrm{BPP}$. This settles the open problem posed as Challenge 5 in The Sparsity Challenges in the finite field setting. Furthermore, we show that the Roots of Unity Detection problem over finite fields is NP-hard; that is, determining whether the GCD of a sparse univariate polynomial and $x^n - 1$ has nonzero degree is NP-hard.

Authors: Ruichen Qiu, Yichuan Cao, Qiao-Long Huang, Ruyong Feng, Xiao-Shan Gao

In this paper, we prove that output-sensitive sparse polynomial GCD computation over finite fields is NP-hard under BPP many-one reduction. More precisely, for two sparse univariate polynomials $f,g$ with finite field coefficients, there exists no randomized algorithm to compute $\mathrm{gcd}(f,g)$, which is polynomial-time in the sizes of $f,g,\gcd(f,g)$ under the standard complexity assumption $\mathrm{NP}\nsubseteq\mathrm{BPP}$. This settles the open problem posed as Challenge 5 in The Sparsity Challenges in the finite field setting. Furthermore, we show that the Roots of Unity Detection problem over finite fields is NP-hard; that is, determining whether the GCD of a sparse univariate polynomial and $x^n - 1$ has nonzero degree is NP-hard.

Thursday, June 11 2026, 00:00

Sparse Polynomial Divisibility Test over Finite Field is CoNP-hard

Authors: Yichuan Cao, Ruichen Qiu, Qiao-Long Huang, Ruyong Feng, Xiao-Shan Gao

In this paper, we show that deciding whether a sparse polynomial does not divide another sparse polynomial exactly over finite fields is NP-hard under BPP many-one reductions. Equivalently, the sparse polynomial divisibility test over finite fields is CoNP-hard. This resolves the long-standing open problem concerning the computational complexity of the divisibility test for sparse polynomials in the setting of finite fields.

Authors: Yichuan Cao, Ruichen Qiu, Qiao-Long Huang, Ruyong Feng, Xiao-Shan Gao

In this paper, we show that deciding whether a sparse polynomial does not divide another sparse polynomial exactly over finite fields is NP-hard under BPP many-one reductions. Equivalently, the sparse polynomial divisibility test over finite fields is CoNP-hard. This resolves the long-standing open problem concerning the computational complexity of the divisibility test for sparse polynomials in the setting of finite fields.

Thursday, June 11 2026, 00:00

Quasi-linear Time Multiplication of Sparse Polynomials with Integer Coefficients

Authors: Qiao-Long Huang, Yichuan Cao, Ruichen Qiu, Xiao-Shan Gao

Sparse polynomial multiplication is a fundamental problem in computer algebra and the theory of computation, and the development of a quasi-linear time output-sensitive multiplication algorithm has been posed as an open challenge. In this paper, a counterexample is provided to a previously claimed solution to this open problem for integer coefficients. By employing the existing quasi-linear modular-black-box interpolation algorithm, we are able to provide an algorithm with quasi-linear bit complexity for the integer coefficients setting. Furthermore, in the case of coefficients over a finite field, we obtain an algorithm whose bit complexity is linear in the number of terms, the logarithm of the degree, and the logarithm of the size of the finite field.

Authors: Qiao-Long Huang, Yichuan Cao, Ruichen Qiu, Xiao-Shan Gao

Sparse polynomial multiplication is a fundamental problem in computer algebra and the theory of computation, and the development of a quasi-linear time output-sensitive multiplication algorithm has been posed as an open challenge. In this paper, a counterexample is provided to a previously claimed solution to this open problem for integer coefficients. By employing the existing quasi-linear modular-black-box interpolation algorithm, we are able to provide an algorithm with quasi-linear bit complexity for the integer coefficients setting. Furthermore, in the case of coefficients over a finite field, we obtain an algorithm whose bit complexity is linear in the number of terms, the logarithm of the degree, and the logarithm of the size of the finite field.

Thursday, June 11 2026, 00:00

Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data

Authors: Arie Soeteman, Balder ten Cate, Maurice Funk, Benny Kimelfeld, Carsten Lutz, Moritz Schönherr

The conventional approach to deep learning over relational databases applies neural models, such as Graph Neural Networks (GNNs), to a graph representation of the database. Recent approaches instead operate on databases directly, associating tuples with embeddings and extending query mechanisms to jointly process embeddings and relational content. Inspired by these developments, we introduce Neuro-Relational Programs (NRPs), a declarative query language for relational databases whose facts carry numeric vector embeddings. NRPs extend Datalog-style rules with operations that combine, aggregate, and transform embeddings, thereby interleaving relational reasoning and learnable neural components within a single formalism. This yields a general approach to neural computation over relational data: an NRP can be read both as a query plan with trainable components and as a neural architecture with relational structure built in. Natural syntactic fragments of NRPs recover existing architectures and query formalisms. Zero-ary NRPs correspond to non-adaptive query algorithms; monadic NRPs generalize GNN-style message passing and precisely capture Deep Homomorphism Networks, a connection that we extend to frontier-guarded NRPs over databases with row-ids. We characterize the expressive power of unrestricted NRPs with ReLU-FFN transformations by FOCQ, an extension of first-order logic with counting interpreted over real-weighted structures, yielding a precise connection with uniform TC$^0$ over ordered databases. Together, these results establish NRPs as a broad declarative framework for querying and neural computation over relational data.

Authors: Arie Soeteman, Balder ten Cate, Maurice Funk, Benny Kimelfeld, Carsten Lutz, Moritz Schönherr

The conventional approach to deep learning over relational databases applies neural models, such as Graph Neural Networks (GNNs), to a graph representation of the database. Recent approaches instead operate on databases directly, associating tuples with embeddings and extending query mechanisms to jointly process embeddings and relational content. Inspired by these developments, we introduce Neuro-Relational Programs (NRPs), a declarative query language for relational databases whose facts carry numeric vector embeddings. NRPs extend Datalog-style rules with operations that combine, aggregate, and transform embeddings, thereby interleaving relational reasoning and learnable neural components within a single formalism. This yields a general approach to neural computation over relational data: an NRP can be read both as a query plan with trainable components and as a neural architecture with relational structure built in. Natural syntactic fragments of NRPs recover existing architectures and query formalisms. Zero-ary NRPs correspond to non-adaptive query algorithms; monadic NRPs generalize GNN-style message passing and precisely capture Deep Homomorphism Networks, a connection that we extend to frontier-guarded NRPs over databases with row-ids. We characterize the expressive power of unrestricted NRPs with ReLU-FFN transformations by FOCQ, an extension of first-order logic with counting interpreted over real-weighted structures, yielding a precise connection with uniform TC$^0$ over ordered databases. Together, these results establish NRPs as a broad declarative framework for querying and neural computation over relational data.

Thursday, June 11 2026, 00:00

A Polynomial-Time $O(\sqrt n)$-Approximation for Undirected Three-Terminal Reachability-Preserving Minimum Edge Cut

Authors: Qi Duan

We study the undirected three-terminal reachability-preserving minimum edge cut problem. The input is an undirected graph $G=(V,E)$ with nonnegative edge costs, two protected terminals $s_1,s_2$, and a target terminal $t$. The goal is to remove a minimum-cost edge set so that $t$ is disconnected from the protected terminals while $s_1$ and $s_2$ remain connected. This problem captures a basic tension between separation and connectivity preservation. Prior work on connectivity-preserving cuts established polynomial-time solvability for some special cases, such as planar edge-cut instances, and strong hardness for node-cut variants, but a general-graph approximation guarantee for the undirected three-terminal edge-cut version does not appear to have been known. We give a polynomial-time $O(\sqrt n)$-approximation algorithm in this paper. This is the first known approximation algorithm for the problem

Authors: Qi Duan

We study the undirected three-terminal reachability-preserving minimum edge cut problem. The input is an undirected graph $G=(V,E)$ with nonnegative edge costs, two protected terminals $s_1,s_2$, and a target terminal $t$. The goal is to remove a minimum-cost edge set so that $t$ is disconnected from the protected terminals while $s_1$ and $s_2$ remain connected. This problem captures a basic tension between separation and connectivity preservation. Prior work on connectivity-preserving cuts established polynomial-time solvability for some special cases, such as planar edge-cut instances, and strong hardness for node-cut variants, but a general-graph approximation guarantee for the undirected three-terminal edge-cut version does not appear to have been known. We give a polynomial-time $O(\sqrt n)$-approximation algorithm in this paper. This is the first known approximation algorithm for the problem

Thursday, June 11 2026, 00:00

Automated Responsive Thematic Mapping with Layout Guides