Theory of Computing Report

The technical paper for the Erdős Unit Distance Problem lists only "OpenAI" as an author. When Bill posted on Sunday about the Erdős distance problems, he mentioned the names of OpenAI researchers who prompted and checked the proof. Sebastien Bubeck of OpenAI reached out directly and later as a comment saying this was really an OpenAI-wide achievement, and we shouldn't just single out people at the end of the funnel. I agree with Bubeck for this paper, but it brings up some challenging authorship issues for the future.

Most publishers follow the position of the Committee on Publication Ethics that AI tools cannot be listed as an author of a paper.

AI tools cannot meet the requirements for authorship as they cannot take responsibility for the submitted work. As non-legal entities, they cannot assert the presence or absence of conflicts of interest nor manage copyright and license agreements.

The paper doesn't list the model as an author, rather the organization (OpenAI) that produced it. The closest analog might be the paper that verified the Higgs boson, which has only "ATLAS Collaboration" on the author line and lists the nearly three thousand authors at the end of the paper. If OpenAI were to publish their paper, they should list everyone who worked on the model with at least a corresponding author to handle the legal issues mentioned in the COPE position.

There is also all the mathematicians whose work was fed into the training data, but I wouldn't list them even if we could. We don't add as authors those whose work we rely on, rather we cite them, and the OpenAI paper does have a healthy references section.

Shortly after the OpenAI announcement, Princeton Professor Will Sawin improved and gave an explicit exponent for the lower bound in a currently singularly authored paper. Often, but not always, when a paper improves a bound of a recently announced result, the papers get merged. I don't expect that to happen here, but if it did I would have no idea how to handle the authorship of the combined paper beyond just listing Sawin and OpenAI as the authors.

OpenAI used an internal model for this work, but one would hope they will eventually release this model to the public. If someone outside of OpenAI uses a released model to answer another open math question, even with a single prompt, do they need to add OpenAI as a co-author? I think not, as the model now becomes a tool when released. The researcher should disclose the role the model played, but the model's creators no longer need to be authors.

How about a thought experiment. Suppose you are working with a student by email on a paper and you put in equal effort so you will both be co-authors. Then you discover the student was mostly just feeding your emails to ChatGPT and sending you back the responses. Now who should be on the author list? The student should come off but it would feel strange writing this a solely authored paper. 

What if someone builds an AI mathematician that doesn't take any prompts? It just reads papers and occasionally writes its own. Who is the author? That "someone". What if they just used a regular AI agent and gave it the prompt "You are a research mathematician. Go read papers, prove theorems and write up your results." Maybe we'll have AI math journals filled with papers written, edited and refereed by AI models. I wonder how we'll COPE with that.

By Lance Fortnow

Authors: Andrea Cuteri, Giuseppe Mazzotta, Francesco Ricca

ASP(Q) extends Answer Set Programming (ASP) with Quantifiers over answer sets. In this paper we focus on the class of ASP(Q) programs with two quantifiers and weak constraints, denoted as 2-ASP(Q)^w. 2-ASP(Q)^w is a practically relevant fragment of ASP(Q) that is expressive enough to capture optimization problems up to the class Delta_3^P. On the theoretical side, we provide a complete complexity characterization of the main computational tasks for 2-ASP(Q)^w programs, including tight completeness results and the analysis of nontrivial cases that have not been addressed in previous works. On the practical side, we introduce novel strategies for computing (optimal) quantified answer sets in the Casper system, that rely on a Counterexample-Guided Abstraction Refinement (CEGAR) technique tailored to ASP(Q). An experimental evaluation on hard benchmarks from different application domains shows that the proposed techniques are effective in practice.

Authors: Saveliy V. Skresanov

The group isomorphism problem in computational complexity asks whether two finite groups given by their Cayley tables are isomorphic or not. Although polynomial-time isomorphism tests exist for many specific types of groups, no general polynomial-time algorithm is known, classes of solvable and nilpotent groups being the main obstacles. In 2012 Babai and Qiao gave a polynomial-time isomorphism test for the class of solvable groups admitting normal series with abelian Sylow factors. We generalize their result and give a polynomial-time isomorphism test for A-groups, i.e. groups with abelian Sylow subgroups. The algorithm heavily relies both on the computational methods developed by Babai and Qiao, and structural properties of A-groups.

Authors: Devin Frost, Kimberly Kokado, Csaba D. Tóth

This paper proves a conjecture by Solomon about Steiner shallow-light trees (SLT) in Euclidean $d$-space: It is shown that for any finite point set $\mathbb{R}^d$, any root, and any $ε>0$, there is a Euclidean Steiner $(1+ε,O(\sqrt{1/ε}))$-SLT without any dependence on dimension. We also revisit the core example, designed by Solomon, in the plane and its generalization to $d$-space.

Authors: Haakon Larsen, Tushant Mittal, Silas Richelson, Sourya Roy

Let $f: T\to \{ 0,1 \}$ be a Boolean function on the Boolean half-slice, $T$, \ie elements of $\{0,1\}^n$ with Hamming weight $n/2$. We show that if $f(x)+f(y)=f(x+y)$ holds with probability $\frac{1+δ}{2}$ over a uniform pair $(x,y)$ such that $x,y,x+y\in T$, then $f$ agrees with some linear function on at least $\frac{1+δ}{2}-o(1)$ fraction of the points in $T$. More generally, we show that if $f$ passes the natural $k$-query BLR test with probability $\frac{1+δ}{2}$ for any $k\geq3$, then it must agree with some affine function at $\frac{1+δ^{\frac{1}{k-2}}}{2}-o(1)$ fraction of the points in $T$. The only other known linearity test for the slice in the low soundness regime (i.e., when $δ$ can be arbitrarily small) was given by Kalai, Lifshitz, Minzer, and Ziegler [FOCS'24]. Our result improves upon this result in two significant ways: firstly, it works for $k=3$ queries, instead of requiring $k\geq4$; secondly, our result is sharper, e.g., when $k=4$, we are able to conclude an agreement of $\frac{1+\sqrtδ}{2}-o(1)$ instead of $\frac{1+c\sqrtδ}{2}$ for $c\approx.0035$. In particular, our result matches (up to the $o(1)$ term) the conclusion one obtains over the full hypercube via the classical BLR analysis. Our main technical contribution is a new dense model theorem using bounds on Krawtchouk polynomials. Using these Krawtchouk polynomial bounds, we also obtain a simple $k$-query test ($k\geq 5$) that avoids any use of the dense model machinery. This simplified test naturally extends to the slice over the $q$-ary hypercube, giving the first such result over larger alphabets.

Authors: Finn Moltmann, Tamio-Vesa Nakajima, Sebastian Wild

We give a more space-efficient implementation of adaptive mergesort: Virtual-Memory Powersort. Using internal buffering techniques, we significantly reduce the memory consumption of the algorithm; specifically, for sorting $n$ objects the required buffer area is reduced from space for $n/2$ objects to $O(\sqrt{n \log n})$ objects. While this space-efficiency can be achieved (indeed reduced to $O(1)$) conceptually very easily with known inplace merging algorithms, using these as a drop-in replacement for the standard merge algorithm incurs a substantial slow-down. Virtual-Memory Powersort, by contrast, uses the same number of moves and comparisons as previous Powersort implementations up to an additive $O(n)$ term. We report on an empirical running-time study comparing our implementation against other Powersort variants and state-of-the-art stable sorting methods, demonstrating that almost in-place stable sorting can be achieved with negligible overhead in many scenarios.

Authors: Vignesh Viswanathan

We consider the problem of dividing a set of indivisible goods among agents with additive valuations. This problem has been studied under various objectives in both the computer science and the operations research literature. Our main contribution is a novel dictator test using this problem, which can separate a dictator from any function sufficiently far from a dictator. We use this test to prove the following hardness results (assuming the unique games conjecture is true): (1) We show that it is NP-hard to approximate the max Nash welfare by a factor better than $\sqrt[3]{\frac{81}{65}} - \varepsilon \approx 1.0761$. This improves on the previous best known inapproximability factor of $\sqrt{\frac87} - \varepsilon \approx 1.069$. (2) We show that it is NP-hard to approximate the maximum budgeted allocation by a factor better than $\frac{243}{227} - \varepsilon \approx 1.07$. This improves on the previous best known inapproximability factor of $\frac{16}{15} - \varepsilon \approx 1.067$. (3) We show that it is NP-hard to approximate the max generalized assignment problem (GAP) by a factor better than $\frac{145}{129} - \varepsilon \approx 1.124$. This improves on the previous best known inapproximability factor of $\frac{11}{10} - \varepsilon \approx 1.10$.

Authors: Malte Luttermann, Ralf Möller, Marcel Gehrke

Exploiting the indistinguishability of objects in a probabilistic graphical model such as a factor graph is key to lifted probabilistic inference algorithms and allows for tractable probabilistic inference problems with respect to domain sizes. A central building block for the exploitation of indistinguishable objects in factor graphs is the identification of commutative factors, i.e., factors whose output values are invariant under permutations of input values assigned to a subset of their arguments. In this paper, we revisit the theoretical foundations underlying the state-of-the-art algorithm to detect commutative factors. Specifically, we show that in its current form, the state-of-the-art algorithm relies on a central theorem that is mistakenly regarded as a sufficient condition to identify commutative factors, while it actually only implies necessary condition. Consequently, the state of the art might, as we show in this paper, deliver incorrect results. To fix the flaws currently present in the state of the art, we prove a slightly modified version of the aforementioned theorem, which serves as a necessary condition to identify commutative factors. Moreover, we present a corrected version of the state-of-the-art algorithm, which keeps its efficiency while ensuring correctness and introduce a complementary algorithm with tighter worst-case bounds.

Authors: Yongho Shin, Phanu Vajanopath

Learning-augmented algorithms have received significant attention in recent years, particularly in the context of online optimization. Motivated by the high computational cost of generating predictions, a growing line of work studies the tradeoff between performance guarantees and the number of predictions used in learning-augmented algorithms for problems such as caching and metrical task systems. In this paper, we extend this line of research to online metric matching by developing parsimonious learning-augmented algorithms and establishing lower bounds on their performance. Our approach extends the Follow-the-Prediction framework to the parsimonious setting by filling in a virtual prediction in the absence of an actual prediction, using an online metric matching algorithm that maintains good intermediate matchings throughout its execution. We complement our theoretical results with an empirical evaluation, demonstrating the practical effectiveness of our approach.

Authors: Leon Stjepan Uroić, Marko Đurasević

Permutation-based metaheuristics are widely used for electric vehicle routing, where candidate solutions are represented as ordered sequences of customers. Such sequences, however, do not directly define feasible vehicle routes: they must be decoded by choosing where to split the permutation into routes and where to insert charging-station visits, subject to cargo capacity and battery constraints. These decisions are inherently interdependent, since each return to the depot both separates consecutive routes and restores the vehicle battery. This paper formalizes the task as the Fixed-Permutation Splitting and Charging Problem and proposes an exact forward labeling algorithm that constructs a minimum-distance feasible decoding of a fixed customer permutation using dynamic programming with dominance pruning. We further derive restricted variants representing increasingly simplified decoding strategies: first separating route splitting from charging-station insertion, and then additionally limiting each inter-customer segment to at most one charging-station visit. Computational experiments on benchmark and randomly generated instances, including comparisons with heuristic decoders from the literature, confirm that the exact decoder remains tractable in practice and reveal a clear hierarchy among decoding strategies. The most restrictive variant achieves runtimes close to those of heuristic decoders while delivering substantially higher decoding success rates and better solution quality. Less restrictive variants further improve quality and robustness at the cost of additional runtime. The exact joint decoder provides the optimal reference for each fixed permutation, clarifying the trade-offs introduced by common decoding simplifications.

In passing, I mentioned a new book by C. Thi Nguyen, The Score, which asks the question: Why are numerical scores fun in video games yet oppressive in social metrics? Or, more succinctly: Why do we love games and hate rules?

The Score is simultaneously a philosophy book, a self-help book, and a gentle introduction to the contemporary academic study of institutions. I applaud Nguyen for recognizing that a philosophy of games and rules needs to engage with ethnographic disciplines to make sense of why metric chasing is core to our current condition. His book makes the tension between individuals and populations more visible for those less willing to immerse themselves in the vast literature of science and technology studies.

Nguyen clearly summarizes the work on bureaucracy, statistics, and rules by scholars like Lorraine Daston, Theodore Porter, and anarchist anthropologist James Scott, whose classic Seeing Like a State is beloved by both the left and the reactionary right. But there’s another anarchist anthropologist who I think has already solved the core dilemma of The Score: David Graeber.

Graeber was not only an academic but a dedicated political activist. He was one of the central figures of the Occupy Movement, credited with helping coin its iconic slogan, “We are the 99%.” Though best known for his books Debt and Bullshit Jobs, my personal favorite is The Utopia of Rules. I like to think the subtitle was microtargeted to me: On Technology, Stupidity, and the Secret Joys of Bureaucracy. The book is a collection of five essays that, though readable separately, together provide a unified answer to Nguyen’s central question.

Graeber frames games and bureaucracy as offering similar utopian fantasies of fairness and equality. In games, everyone plays by the same rules. The outcomes are transparent. We know what it means to win and lose. Since everything is written down, we can all evaluate if we think it’s fair and argue for rule changes if it’s not. But bureaucracy promises the same thing. It has no shortage of written rules! We only have all of those rules to maintain transparency and fairness. We want everyone to be treated equally under the law, don’t we?

Score-based games let us escape in temporary fantasy, and yet, in their complex scoring systems, Graeber writes, they “reinforce the sense we live in a universe where accounting procedures define the very fabric of reality.” Video games and bureaucratic mechanisms are two reflections of the same reality. Ironically, the score-based games that Nguyen celebrates close off the imagination of alternative forms of governance.

Still, we love our board games and video games, and we hate going to the DMV. Why is that? What explains how getting enmeshed in a battle with HR or the IRS is terrifying and emotionally crippling? What explains why our popular imagination paints bureaucracy in surrealist, existential nightmares like in The Trial, Brazil, or Andor?

For Graeber, the main difference between games and bureaucracy is what he calls structural violence—“forms of pervasive social inequality that are ultimately backed up by the threat of physical harm.” Graeber argues that bureaucratic systems of endless, stupid paperwork are the defining example of structural violence in our society.

“Now, I admit that this emphasis on violence might seem odd. We are not used to thinking of nursing homes or banks or even HMOs as violent institutions—except perhaps in the most abstract and metaphorical sense. But the violence I’m referring to here is not abstract. I am not speaking of conceptual violence. I am speaking of violence in the literal sense: the kind that involves, say, one person hitting another over the head with a wooden stick. All of these are institutions involved in the allocation of resources within a system of property rights regulated and guaranteed by governments in a system that ultimately rests on the threat of force. ‘Force’ in turn is just a euphemistic way to refer to violence: that is, the ability to call up people dressed in uniforms, willing to threaten to hit others over the head with wooden sticks.”

It is this threat of force that makes bureaucracies so stupid. To see why, begin with violence itself. It is one of the only forms of human interaction that requires no interpersonal interpretation. We know exactly what happens with the conditional command: “Cross this line and I’ll shoot.” When you issue this edict, you are running a mechanical algorithm of violence that needs no understanding of the person who is coming at you. If they cross the line, you shoot them. Both you and your counterparty have a precise expectation of what happens after you pull the trigger.

This lack of interpretation is afforded only to those who have power and can actualize violence without repercussion. This consequent ability to harm makes those in power lazy. And the structures built to maintain these power structures become lazy with them.

Indeed, bureaucratic rules let those in power remain oblivious to what’s actually happening to everyone else. The stupidity of bureaucracy is a feature for those in power. It removes their need to understand those who are subject to the rules. Graeber’s argument is completely consistent with the views of stout institutionalists who tout the benefits and necessity of bureaucracy. Part of the benefit of bureaucratic systems is how they abstract complexity up a hierarchy, allowing people at each level to act without knowing all the details of what’s happening below them.

However, Graeber foregrounds the people at the bottom who are erased by quantified summaries. The erasure of those individuals into statistics means that those in power have no need to do the interpretive labor of thinking what it must be like to be them. Those who set the rules are privileged to not have to think about those forced to abide by them. By sharp contrast, those who have to deal with the rules are obliged to empathize with the powerful. They must constantly imagine how the powerful might act and react to avoid the persistent threat of violence. This is how normally intelligent people are forced to act like idiots when dealing with bureaucratic procedures.

Summarization and bureaucratization do not have to be stupid. You can read my architecture lecture from a few weeks back to see how well-designed hierarchical rule systems can create amazing outcomes. Graeber, to his credit, doesn’t disagree.

“To put it crudely: it is not so much that bureaucratic procedures are inherently stupid, or even that they tend to produce behavior that they themselves define as stupid—though they do do that—but rather, that they are invariably ways of managing social situations that are already stupid because they are founded on structural violence.”

Bureaucracy is stupid when it is used as a system of deempathization and structural violence. When rule-based systems reduce the interpretative labor of those in power, “such procedures come to partake of the very blindness and foolishness they seek to manage.”

Now, I don’t think you’re going to reach Ezra Klein and Derek Thompson listeners with Graeber’s far-left radicalism. You’re definitely not going to reach the staunch institutionalist liberals of Bluesky who hate David Graeber with every ounce of their being. I don’t mean this cynically: I think Nguyen wants to reach out to both of those audiences, and that’s his prerogative.

However, I think we are best off not forgetting Graeber and the left-wing movements that arose in the wake of the financial crisis. Though the stock market is soaring, it’s hard to argue the world is in a better place today than it was after 2008. The economist Joseph Stiglitz’s so-called 1% has lost some of its power, but only because it has ceded it to the 0.001%. There’s less faith in institutions than ever. The financialization and gamification of everything have put us all in the awkward position where every aspect of our lives is now connected to a risky set of dehumanizing rules. The radical critiques from the 2010s don’t have simple answers for our current polycrisis, but ignoring them walls off imagining better worlds.

Subscribe now

By Ben Recht

Authors: Islam Faisal, Anand Natarajan, Alexander Poremba

Commuting Hamiltonians lie at the boundary between classical constraint satisfaction and quantum many-body physics, exhibiting rich quantum structure while remaining more tractable than general noncommuting models. In contrast, physical Hamiltonians are rarely exactly commuting, which naturally motivates the study of almost commuting Hamiltonians. Despite their relevance, the implications of approximate commutation are only poorly understood. In this work, we show how to efficiently approximate any almost commuting $2$-local qubit Hamiltonian by a commuting one: we give a locality-preserving algorithmic rounding technique that maps any $2$-local Hamiltonian $H=\sum_{i=1}^m h_i$ with $\|[h_i,h_j]\| \leq ε$ to a nearby Hamiltonian $\hat{H}$ whose terms pair-wise commute, and which is within overall distance $\|H-\hat{H}\| = O(m\,ε^{1/6})$. As a consequence, we show that $δ$-approximations to the ground energy for $ε$-almost commuting $2$-local qubit Hamiltonians lie in $\mathsf{NP}$ when $δ\gg mε^{1/6}$, extending the classical containment well beyond the commuting setting. Finally, we present two applications of our rounding framework: Gibbs sampling and fast Hamiltonian simulation for almost commuting systems.

Authors: Stefan Bard, Gary MacGillivray, Jacobus Swarts

For an integer $t \geq 1$, a homomorphism of a digraph G to a digraph $H$ is $t$-frugal if no more than $t$ in-neighbours of any vertex of $G$ have the same image. There is a dichotomy theorem based on structural properties when $t=1$ and $H$ has a loop at each vertex, but there is unlikely to be such a theorem for general digraphs $H$. For $t \geq 2$ we describe a structural dichotomy theorem for $t$-frugal homomorphisms of general digraphs.

Authors: Ernst Althaus, Benjamin Merlin Bumpus, James Fairbanks, Emilio Minichiello, Daniel Rosiak

A limit of a (small) diagram $d : J \to E$ in a complete category $E$ can be thought of as specifying a set of equations involving the objects of $E$. To motivate this intuitively, one can think of each object $d(j)$ as a "variable" and each morphism in $J$ as a "constraint" connecting these variables. If $E$ has an initial object, a natural question arises: does our set of equations have any solution at all? Equivalently, we can ask: is the limit of $d$ initial? In this paper we consider the computational problem that, given finite diagram $d$ in a finitely complete category $E$, asks whether its limit is empty. We construct a fast algorithm (in the sense of parameterized complexity theory) that solves this problem when $E$ is of the form $\mathbf{FinSet}^{J}$ for a finite category $J$ and $d$ is a structured co-decomposition, i.e. a diagram arising from the opposite of the Grothendieck construction of a simple graph.

Authors: Xinyuan Yan, Rita Sevastjanova, Mennatallah El-Assady, Bei Wang

Neural networks encode inputs as high-dimensional vectors, known as representations, that capture how models process data by encoding task-relevant structure and semantics. Representation alignment refers to the degree to which different models, layers, or training conditions produce similar representations for the same inputs, with important implications for model interpretation, selection, and robustness analysis. Existing approaches to measure alignment primarily rely on geometric properties, such as neighborhood and cluster similarity, offering limited insight into the global organization of representations. In this work, we present TopoAlign, a topology-aware framework for visually comparing model representations from a structural perspective. Leveraging mapper graphs from topological data analysis, TopoAlign jointly analyzes graphs constructed from representations of shared inputs across different models or layers. The framework supports a top-down comparative workflow: it first performs global structure alignment via joint force-directed optimization to produce coordinated graph layouts; it then identifies local correspondences through automated detection of structurally matching regions, visualized with Bubble Sets; and finally it enables fine-grained pattern inspection through motif-based queries and membrane-inspired visualizations. We demonstrate TopoAlign through case studies on language and multimodal models, complemented by expert feedback. Our results show that TopoAlign provides meaningful insights into representation structure and alignment from a topological perspective.

Authors: Bundit Laekhanukit, Pasin Manurangsi, Ohad Trabelsi

We study the Densest At-Least-$k$-Subgraph (DAL$k$S) problem, in which we are given an undirected graph $G$ and an integer $k$, and the goal is to find a subgraph of $G$ with at least $k$ vertices with maximum density. The best-known algorithm, independently discovered by Khuller and Saha (2009) and by Andersen (2007), yields a 2-approximation for DAL$k$S in polynomial time. In this note, we provide a (simple) reduction from Densest $k$-Subgraph (D$k$S) to Densest At-Least-$k$-Subgraph, which shows that, if D$k$S is hard to approximate to within any constant factor, then DAL$k$S is hard to approximate to within $(3/2 - \varepsilon)$ factor for every $\varepsilon > 0$. This holds in both the normal (non-parameterized) and the parameterized (by $k$) settings. We then generalize the reduction to provide a tight $(2 - \varepsilon)$ factor hardness of approximating Densest At-Least-$k$-Subgraph, albeit under a stronger hypothesis which roughly states that Densest $k$-Subgraph is hard to approximate to within $k^{1 - δ}$ factor for any constant $δ> 0$. Once again, this extends naturally to the parameterized setting. Previously, $(2 - \varepsilon)$ factor inapproximability for DAL$k$S was only known under the Small Set Expansion Hypothesis (Bergner, 2013; Manurangsi, 2017), which does not apply to the parameterized version of the problem. Furthermore, we show that the exact version of DAL$k$S is W[1]-hard (parameterized by $k$).

Authors: Gil Halevi, Daniel Zhang, Jason Zhang

Given two sets of points A and B, $|A| = m$, $|B| = n$, the Chamfer distance from $A$ to $B$ is defined as $\operatorname{CD}(A,B) = \sum_{a\in A} \min_{b\in B} d(a,b)$, where $d$ is a distance metric. Chamfer distance is a popular measure of dissimilarity between two sets of points that has seen increasing usage in computer vision and information retrieval as a substitute for the more computationally demanding Earth Mover's distance. We propose a new problem, Chamfer distance under translation, defined as $\operatorname{CDuT}(A,B) :=\min_{t\in \mathbb{R}^d} \operatorname{CD}(A+t,B)$, where $A+t$ denotes the translation of every point in $A$ by $t$. Chamfer distance under translation is valuable in cases where translations capture aspects of the data unlikely to be relevant for dissimilarity, such as temporal, spatial, or other semantic information. For Chamfer distance under translation, we provide four algorithms: (1) an exact quadratic time algorithm in one dimension, (2) a near quadratic time ($2+\varepsilon$)-approximation algorithm in higher dimensions, (3) a $(1+\varepsilon)$-approximation algorithm with running time $\mathcal{O}(mn^2\varepsilon^{-(d+1)})$, and (4) a near-quadratic time $(1+\varepsilon)$-approximation algorithm for answering the decision version of $\operatorname{CDuT}$ given a separation assumption on $B$. We additionally explore the fine-grained complexity of $\operatorname{CDuT}$.

Authors: Andrej Risteski, Thuy-Duong Vuong

We study \emph{learning-to-sample} -- a basic algorithmic task underlying generative modeling -- for Ising models, a standard testbed for algorithmic ideas in both theoretical computer science and machine learning. Given i.i.d. samples of an unknown target distribution, the goal of learning-to-sample is to learn a computationally efficient generation procedure that produces new samples following approximately the same distribution. We construct a family of Ising models of constantly bounded-width which lie just beyond the spectral threshold $λ_{\max}(J)-λ_{\min}(J)=1$, and show that learning-to-sample for this family is computationally hard under standard cryptographic assumptions, even when the learner is given both polynomially many i.i.d. samples from the model and explicit access to its parameters. Combined with results of [AJKPV24,KLV25] showing tractability of learning-to-sample below the spectral threshold, this establishes a sharp computational phase transition at the spectral threshold. Moreover, combined with prior results on parameter learning for bounded-width Ising models [KM17,WSD19,VML20], this shows that learning-to-sample can be more difficult than parameter learning. Finally, we show that any efficient learner for these hard instances exhibits a natural memorization-hallucination dichotomy: the learner must either output configurations that, after a simple transformation, match the (transformed) training data or place substantial mass on configurations of negligible probability under the target distribution.

Authors: Komal Muluk

We consider a bilevel optimization problem in which the ground set is partitioned between two decision makers, a leader and a follower, whose optimization problems are interleaved. We study the Bilevel Independent Set problem, and its special case, the Bilevel Interval Selection problem, on different variants emerging from a combination of the type of leader's objective function, the type of follower's objective function, and the setting in which the follower reacts, i.e., either optimistically or pessimistically. Here we consider sum and bottleneck type objective functions. We investigate the computational complexity of all these variants for the Bilevel Independent Set problem, and sort them into their respective level of the polynomial hierarchy. Our results range from $\mathsf{P}$, $\mathsf{NP}$-completeness to $Σ_2^\mathsf{p}$-completeness. For the Bilevel Interval Selection problem, we give a dynamic programming algorithm running in time $\mathcal{O}(n^4\log n)$ for the variants in which the leader and the follower have objective functions of the sum type.

Authors: Eshwar Srinivasan, Ramesh Hariharasubramanian

In this work, we investigate the algorithmic aspects of two natural extensions of hereditary classes: the edge-apex class and the edge-add class, recently introduced by Singh and Sivaraman. These are defined as the graph classes obtained by at most one edge deletion or one non-edge addition, respectively, from a hereditary class $\mathcal{G}$. Building on earlier results showing that both classes remain hereditary and admit finite forbidden induced subgraph characterizations whenever $\mathcal{G}$ does, we focus on the Weighted Maximum Clique Problem (WMCP) and the Weighted Maximum Independent Set Problem (WMISP). We first present algorithms for WMCP and WMISP on both the edge-apex and edge-add classes of hereditary graph classes. Extending this framework, we introduce the notion of the $\mathcal{G}$-edge distance of a graph $G$, denoted by $ξ_{\mathcal{G}}(G)$, which quantifies how far $G$ is from the class $\mathcal{G}$ in terms of the minimum number of edge deletions or non-edge additions needed to transform it into a member of $\mathcal{G}$. By parameterizing with respect to this distance, we show that both WMCP and WMISP can be solved in $O^*(2^k)$ time on graphs whose $\mathcal{G}$-edge distance is $k$, provided these problems admit polynomial-time algorithms within the class $\mathcal{G}$. This result extends earlier algorithmic characterizations of the single edge-apex and edge-add classes to the more general setting of $k$-edge-distant graphs. By combining our general results with known properties of transitive graphs, we show that WMCP and WMISP can be solved in $O^*(2^k)$ time for graphs with transitive-edge distance $k$.

Authors: Ishant Garg

Succinct data structures use space close to the information-theoretic minimum while answering queries directly on the compressed representation. In this paper, we present a practical engineering study of rank and select queries on bit vectors. We evaluate a classic two-level block baseline (BlockBitVec), an asymmetric superblock implementation (FastBitVec), and an entropy-compressed representation (RRRBitVec) based on the Raman, Raman, and Rao (RRR) coding scheme. On Apple Silicon (M-series ARM architecture), we demonstrate a 1.4x speedup in rank queries through asymmetric 4096/256-bit block boundaries, with a rank index overhead of 7.8%. We investigate the empirical behavior of RRRBitVec and observe a symmetric density-dependent bell-curve for rank latency -- where queries at extreme densities (1% and 99%) run up to 39% faster due to offset elimination at boundary classes. We further show that RRRBitVec achieves a 4.9x speedup over classic binary-search select baselines, running in 33.7 ns at uniform density by using a superblock-level sampling index that restricts sequential scans to L1-cache lookups. All implementations are validated against a correctness fuzzer executing over 78 million assertions with no failures. Source code and test harnesses are publicly available.

Authors: Samuel B. Hopkins, Stefan Tiegel

The $2 \rightarrow q$ norm of a matrix $X \in \mathbb{R}^{n \times d}$ is defined as $\lVert X \rVert_{2 \rightarrow q} = \sup_{\lVert v \rVert_2 = 1} \lVert Xv \rVert_q$. We give polynomial-time multiplicative approximation algorithms for this norm when $q > 2$ (i.e. in the hypercontractive setting). This problem either directly captures or is closely related to long-standing open problems in combinatorial optimization and hardness of approximation (e.g. Small Set Expansion), quantum information (e.g. Best Separable State), and algorithmic statistics. Very little is known about what approximation factors we can achieve for this problem in polynomial time, even though such approximations have significant downstream consequences. Barak, Brandão, Harrow, Kelner, Steurer, and Zhou showed that no polynomial-time algorithm can achieve an approximation factor better than $2^{\sqrt{\log n}}$, assuming the Exponential Time Hypothesis (FOCS'12). On the other hand, a simple spectral algorithm gives a $d^{1/4}$-approximation as a baseline. We give, to the best of our knowledge, the first polynomial-time approximation algorithm beating this baseline by polynomial factors. For the important special case of $q = 4$ it achieves a $d^{1/8}$-approximation. All previous algorithms required additional assumptions on $X$, or only surpassed the baseline for small values of $n$. Moreover, we construct sum-of-squares certificates for the $2 \rightarrow q$ norm. This directly implies improved algorithms for robust mean and covariance estimation, robust regression, and clustering, when the data only satisfies a bound on its $q$-th moment.

Authors: David G. Harris, George Z. Li, Nitya Raju, Renata Valieva

Many optimization and scheduling problems can be abstracted in terms of a bipartite ``assignment graph" $G = (L \cup R, E)$, where the goal is to select exactly one edge for each right-node. For example, a right-node may correspond to a job, and a left-node to a possible machine assignment. A common strategy to solve such problems is to obtain a fractional relaxation $x_e$ for each edge $e$, and then have each right-node independently select an edge with probability $x_e$. However, this may cause the left-nodes to become unevenly loaded, leading to suboptimal solutions for some problems. To address this, a number of algorithms for dependent rounding with strong negative correlation have been developed, e.g. Bansal, Srinivasan & Svensson (2021), Im & Shadloo (2020), Im & Li (2023), Harris (2024), Naor, Srinivasan & Wajc (2025). We introduce a new method for this, which we call the \emph{Dirichlet mechanism}. It is based on having each left-node draw Dirichlet random variables for its edges, and then having each right-node select an edge based on these values. This achieves quantitatively stronger negative correlation than previous algorithms, and is also simpler since it avoids the need for a tie-breaking mechanism. We illustrate the mechanism with improved approximation ratios for two problems. For oblivious online dependent rounding, we achieve a $0.68$-approximation which improves upon the previous $0.652$-approximation of Naor, Srinivasan & Wajc (2025). For the problem of scheduling jobs on unrelated machines to minimize weighted completion time, we achieve a $1.387$-approximation which improves upon the $1.398$-approximation of Harris (2024). (A recent algorithm of Li (2025) based on iterated rounding also provides a $1.36$-approximation if the weights of each job are independent of machine.)

Authors: Vasiliy S. Shlyk

Integer sorts in OLAP engines often run on columns whose cardinality $K$ is much smaller than the array length $N$. After a group-by stage the intermediate key column has $K$ bounded by the number of distinct group keys, and even a column-store scan typically operates on dictionary-encoded categorical fields where $K$ never exceeds a few thousand. A comparison sort on such a column still pays $Θ(N \log N)$ comparisons, and a radix sort still pays $Θ(N \cdot B/b)$ byte passes, irrespective of $K$. This paper describes CAFS, an integer sort that does exploit it on x86-64 with AVX2. The algorithm combines a SIMD bucket sized to one cache line, a Chao1 cardinality estimator over 1024 strided samples (kept in a heap-allocated 40 KB open-addressing table), and an adaptive dispatcher backed by a spill safety guard. The hot loop is branchless and uses AVX2 cmpeq together with movemask and tzcnt to locate the matching lane. We benchmarked CAFS on a full-factorial grid of 58 array sizes $N$ from $10^3$ to $3 \cdot 10^7$ with dense $K$ schedules per $N$, producing 592770 timed runs against pdqsort, IPS4o, vqsort, ska_sort, and std::sort. In the $K \ll N$ band the throughput is 1.7 to 3.1x that of pdqsort, 1.7 to 3.5x IPS4o, and 1.2 to 2.3x vqsort. The operational crossover against pdqsort is at $K \approx 1.3 \cdot 10^5$; against ska_sort, $K \approx 8.14 \cdot 10^5$; against vqsort, $K \approx 6.7 \cdot 10^5$; and against IPS4o the curves only converge near $K = N$. Of the five baselines, only vqsort actually overtakes CAFS once the crossover is passed, which makes the vqsort threshold at $K \approx 6.7 \cdot 10^5$ the binding constraint on the operational range of CAFS.

Authors: Hong Li, Jianping Li, Wei Li, Runtao Xie, Xiaoxiao Yang

In this paper, we study the prize-collecting rural postman problem (PCRPP), a variant of the rural postman problem. Given a PCRPP instance consisting of an undirected graph whose edges have nonnegative lengths and nonnegative profits, together with a root vertex, the goal is to find a closed walk that starts and ends at the root vertex and minimizes the sum of its length and the profits of all edges that the walk does not traverse. A natural way to design an approximation algorithm for the PCRPP is to construct a prize-collecting traveling salesman problem (PCTSP) instance from the given PCRPP instance, apply an approximation algorithm to the PCTSP instance, and then convert the resulting PCTSP solution into a PCRPP solution. We show that this approach has an inherent factor-two barrier: even if the constructed PCTSP instance is solved exactly, the resulting PCRPP solution can have objective value arbitrarily close to twice the optimum value of the original PCRPP instance. Our main result is a polynomial-time approximation algorithm with approximation ratio strictly smaller than 1.6 for the PCRPP. On a public 118-instance benchmark set, the proposed algorithm has average and maximum optimality gaps of 3.39\% and 12.12\%, respectively.

Authors: Cong Ling, Hao Yan, Nicholas Zhao

In this work, we revisit the dual attack and GPV trapdoor sampling, focusing on the lattice Gaussian sampling term, which can be a significant bottleneck in the overall complexity. We show that this sampling step can be quantumly accelerated by combining the lower bound underlying Wang and Ling's analysis of Klein's algorithm with the quantum rejection sampling (QRS) framework proposed by Ozols et al. Specifically, this lower bound gives precisely the pointwise domination condition required for quantum rejection sampling when given coherent oracle access to a truncated Klein proposal distribution, which yields a quantum procedure for preparing the truncated dual $q$-ary lattice Gaussian with a quadratic reduction in the sampling complexity. The truncation radius is chosen so that the truncated distribution is negligibly close to the full lattice Gaussian in total variation distance. Substituting this sampler into the dual attack framework results in reduced overall attack-cost estimates. Compared with Pouly and Shen's modern dual attack under the same parameter choices, our estimates reduce the attack cost by \(9\), \(4\), and \(13\) bits for Kyber-512, Kyber-768, and Kyber-1024, respectively. We also report the corresponding estimates with modulus switching. Finally, by replacing the Markov chain Monte Carlo (MCMC) sampler with the QRS algorithm, we achieve a similar quadratic speedup in the GPV signing process.

Authors: Mengyuan Hu, An Zhang, Yong Chen, Zhikai Chen, Wei Ding, Guohui Lin, Jiaxuan Ma, Yue Sun

We study the problem of covering the maximum number of vertices in a graph by a collection of vertex-disjoint stars, each with a number of satellites in a given interval $[k, \ell]$, where $1 \le k < \ell$ and $\ell$ can be infinity. This is referred to as sequential {\sc $[k, \ell]$-Star Packing} problem. It is solvable in polynomial time when $k = 1$, but becomes strongly NP-hard when $k \ge 2$. In this paper, we propose either the first or an improved approximation algorithm for the following four sequential settings: 1) a $\frac {k+1}2$-approximation algorithm when $k \ge 3$ and $\ell = \infty$, improving the previous best ratio of $\frac {(k+1)^2}{2k+1}$; 2) a $\frac 43$-approximation algorithm when $k = 2$ and $\ell = \infty$, improving the previous best ratio of $\frac 32$; 3) the first $(1 + \frac \ell{\ell+1})$-approximation algorithm when $2 = k < \ell$; and 4) the first $(1 + \max\left\{\frac {k-1}2, \frac {(k+1) \ell}{3 (\ell+1)}\right\})$-approximation algorithm when $3 \le k < \ell$. Besides the main algorithmic techniques being local search coupled with amortized analysis, we observe augmenting configurations to bridge two distant neighborhoods for a local improvement operation. Additionally, the problem has been shown APX-hard when $k \ge 3$; we prove its APX-hardness for the last remaining case where $k = 2$.

Authors: Alexander He, Nana Liu, Mark M. Wilde

Fermi-Dirac machines were proposed recently as an approach to solving semidefinite optimization problems on quantum computers. Here, we reinterpret them as canonical quantizations of classical neurons. By viewing a classical neuron as an activation function applied to a parameterized classical Hamiltonian, we quantize this model by replacing classical variables with operators whose eigenvalues encode their possible values. This follows the standard approach to canonical quantization in quantum mechanics. Crucially, when the Hamiltonian consists of commuting operators, our construction reduces exactly to a classical neuron. More generally, our approach yields an activation observable, defined as an activation function applied to a parameterized quantum Hamiltonian. The output of this quantized neuron is a random variable with expectation value equal to that of the activation observable with respect to an input state. We develop efficient hybrid quantum-classical algorithms for evaluating outputs and gradients of our quantized neurons, enabling evaluation and training. These algorithms rely on basic primitives that include random sampling, Hamiltonian simulation, and the Hadamard test. We also quantize a whole host of other activation functions, including the smooth rectified linear unit (ReLU), sigmoid linear unit, Gaussian-smoothed ReLU, and Gaussian error linear unit (GeLU), which are known to be useful for deep learning applications. Numerical experiments indicate that neurons based on quantum Hamiltonians can learn functions that classical neurons cannot. We further define a computational decision problem based on Fermi-Dirac neurons and prove that it is BQP-complete, providing complexity-theoretic evidence against efficient classical simulation. Finally, we generalize our approach to continuous quantum variables and sketch two different ways of composing these neurons into networks.

Authors: Alex Crane, Pål Grønås Drange, Eli Friedman, Paul D. Hovland, Jan Hückelheim, Andrew Lyons, Yosuke Mizutani, Macéo Ottavy, Blair D. Sullivan

The algorithmic differentiation (AD) of mathematical functions can be interpreted as a sequence of vertex eliminations in an underlying directed acyclic graph. The problem of determining a minimum-cost elimination ordering, which we call Optimal Vertex Elimination, is NP-complete. Consequently, much effort has been devoted to the design of heuristics. Many of these heuristics are widely believed to perform well in practice, but this hypothesis has so far been difficult to test due to the lack of scalable exact methods. We design and engineer new integer programming formulations for Optimal Vertex Eliminatioin and for a related objective we call Minimum Edge Count. Our implementations scale to graphs one-to-two orders of magnitude larger than existing techniques, enabling the assembly of a corpus of medium-sized graphs for which optimal solutions are known. This corpus facilitates a study of existing heuristics, confirming that on real data popular methods achieve high quality solutions. We also make several theoretical contributions. We give a tight analysis of the forward and reverse modes of AD, and extend our techniques to provide a simple algorithm for Optimal Vertex Elimination with approximation ratio parameterized by the size of a minimum source-sink separator. On the complexity side, we give the first approximation lower bounds for both problems.

Authors: Ori Gurel-Gurevich, Asaf Nachmias, Sushant Sachdeva

We prove that for any unweighted graph on n vertices the L1 norm of a unit electric current between the endpoints of a random edge is at most 2 log n. Furthermore, we show that on any weighted graph the spectral norm of the entry-wise absolute value of the symmetric transfer-current matrix is at most 2 log n. This bound is tight up to constants and improves the O(log^2 n) bound from [Schild-Rao-Srivastava, SODA '18]. The initial proofs were generated by OpenAI's ChatGPT 5.5 Pro; the authors have verified and rewritten them to enhance readability and provide additional context.

This post is a map of the Simplex line of posts on Decentralized Thoughts. It is meant to be read as a chapter: first the core Simplex idea, then some of the main ways to vary it. A salient property of Simplex is that parties leave a view only with a value certificate or a skip certificate. This is in contrast to protocols like PBFT, HotStuff, Casper, and Tendermint, where...

By Ittai Abraham

Authors: Melissa Antonelli, Arnaud Durand, Rui Li

The paper proposes an implicit (i.e., machine-independent) complexity approach to studying computation by polynomial-size, constant-depth circuits with gates counting modulo a constant through the lens of discrete ordinary differential equations (ODEs). So far, recursion-theoretic characterizations have been provided for functions computed by circuits of constant depth, including gates counting modulo 2 and 6 only (i.e., for the classes FAC0[2] and FAC0[6], resp.). In this paper, it is shown that considering ODE schemas, rather than bounded recursion, allows for a more fine-grained analysis, leading to (uniform) characterizations for all classes FAC0[n] (n \in N), i.e. functions computed by circuits including counting modulo n gates. Inspired by the syntactic form of the ODE schemas, we go further in this direction and present first-order bounded theories for capturing provably total functions in each of these classes.

Authors: Jack Stade

We prove a PCP theorem for the existential theory of the reals, showing that MAX-ETR-INV is $\exists\mathbb{R}$-hard to approximate to within some constant factor. The existential theory of the reals (ETR) is a decision problem asking if there exists a set of real-valued variables satisfying some constraints involving polynomials and inequalities, and $\exists\mathbb{R}$ is the complexity class of problems polynomial-time reducible to ETR. Many important geometric problems are known to be $\exists\mathbb{R}$-complete. $\exists\mathbb{R}$-hardness results frequently work by a reduction from the $\exists\mathbb{R}$-complete problem ETR-INV, which asks if there is a an assignment of real variables each in the interval $[\frac12, 2]$ satisfying some constraints of form $x=1$, $xy=1$ and $x+y=z$. MAX-ETR-INV is a related optimization problem that asks, given a set of constraints of form $x=1$, $xy=1$, and $x+y=z$, for a feasible (that is, satisfiable with variables in $[\frac12, 2]$) subset of those constraints of the largest possible size. We show that there is some constant $ε>0$ such that it is $\exists\mathbb{R}$-hard to approximate MAX-ETR-INV better than a $1-ε$ factor. This means that even a non-deterministic polynomial-time algorithm can't approximate MAX-ETR-INV better than this factor unless $\exists\mathbb{R}=\text{NP}$. We also give a polynomial-time $8$-factor approximation algorithm and a non-deterministic-polynomial-time $2$-factor approximation algorithm for MAX-ETR-INV.

Authors: Samruddhi Pednekar, Supartha Podder

The approximate non-deterministic degree of a Boolean function $f$, denoted $\mathsf{ndeg}_ε(f)$ (written $\mathsf{N}_ε(f)$ for brevity), is the minimum degree of a real polynomial $p$ such that $0 \le |p(x)| \le ε$ whenever $f(x) = 0$, and $|p(x)| \ge 1$ whenever $f(x) = 1$. Unlike exact non-deterministic degree, which only requires the polynomial to be nonzero on $1$-inputs, this measure enforces a uniform gap: the polynomial must stay close to zero on all $0$-inputs and bounded away from zero on all $1$-inputs. The rational degree conjecture, open for over three decades, was recently resolved by Kothari, Kovacs-Deak, Wang, and Yang, who showed that for every total Boolean function $f$, \[ deg(f) \le \widetilde O\!\left(\operatorname{rdeg}(f)^3\right). \] In their paper, they explicitly propose a stronger conjecture: that approximate degree is polynomially bounded by $\mathsf{N}_ε(f)$ and $\mathsf{N}_ε(\overline{f})$ jointly, i.e., for every total Boolean function $f$ and every constant $0<ε<1$, \[ \widetilde{deg}(f) \le \operatorname{poly}(\mathsf N_ε(f), \mathsf N_ε(\overline f)). \] This conjecture, if true, would imply a polynomial version of the rational degree result and bring us closer to resolving de Wolf's longstanding non-deterministic degree conjecture. In this work, we make the first systematic progress on this problem, establishing the conjecture for several broad and natural function classes: monotone and unate functions, functions of bounded alternation number, symmetric functions, $k$-uniform hypergraph properties, and read-$k$ Disjunctive Normal Form (DNF) formulas.

Authors: Sumegha Garg, Songhua He, Periklis A. Papakonstantinou

This work initiates the study of memory-query tradeoffs for graph problems, with a focus on correlation clustering. Correlation clustering asks for a partition of the vertices that minimizes disagreements: non-edges inside clusters plus edges across clusters. Our first result is a tight query lower bound: to output a partition whose cost approximates the optimum up to an additive error of $\varepsilon n^2$, any algorithm requires $Ω(n/\varepsilon^2)$ adjacency-matrix queries. Under memory constraints, we show that even for the seemingly easier task of approximating the optimal clustering cost (without producing a partition), any algorithm in the random query model must make $\gg n/\varepsilon^2$ adjacency-matrix queries. Finally, we prove the first general graph model query lower bound for correlation clustering, where algorithms are allowed adjacency-matrix, neighbor, and degree queries. The latter two bounds are not yet tight, leaving room for sharper results.

Authors: Dongxin Guo

Large language models now write software, draft legal documents, and produce clinical notes, yet fundamental limits, from Turing and Arrow to the No Free Lunch theorems, shape what computation can do. This thesis turns such impossibility results from curiosities into design rules. Its flagship result proves an accuracy ceiling set by architecture alone: past a critical reasoning depth, no amount of training moves it, at any adapter rank, sample size, or loss function. Computable before deployment from layer count and embedding width, this Deterministic Horizon is measured between nineteen and thirty-one across twelve transformer architectures, and fine-tuning on optimal-length traces recovers under four percentage points. The mechanism is a capacity invariant of the residual stream, and an information-theoretic conversion yields super-exponential accuracy decay past the horizon. An unconditional circuit-complexity lower bound for modular exponentiation against constant-depth prime-modulus circuits complements this result. The same argument recasts across subfields: preference learning under any misspecified model jumps discontinuously in sample complexity; multi-stage retrieval pipelines require at least as many independent metrics as stages; standard truthful auctions fail for agents with prompt-dependent valuations; and zero-knowledge verification of neural inference pays a measured overhead of one hundred ten to one hundred ninety times per non-linear activation. Together these form a catalogue of sixteen specifications, each pairing a computable boundary, a quantified violation cost, and a constructive design rule: two compositions are proved, one pairing is an honest obstruction, and four remain open. The impossibility-specification methodology is offered for the generative research programme that trustworthy AI may need. Every fundamental limit of AI is also a design rule.

Authors: Ben Claydon, Richard Connor, Alan Dearle

Our context of interest is how binary locality sensitive hash (LSH) functions can be used to solve the approximate near neighbour (ANN) problem, which seeks to find the k closest elements of some dataset X to some further point q presented as a query. Binary locality sensitive function families H are sets of functions each which accept a point and return a binary value. A function is locality sensitive if and only if the output of the function is more likely to be equal (a 'hash collision') if two close vectors are used as input than if two far vectors are used. A data structure can be built by generating binary hash codes for each member of X, which are generated by drawing and applying one or more functions from H. When q is presented as a query, the same set of functions is applied to it and those elements of X with equal binary hash codes are retrieved. In this paper we introduce dynamic query modification. This process changes q at query time to form a new value c, which by theoretical and experimental analysis we prove has two significant advantages. Firstly, the hash output of c collides with near neighbours with a greater probability than q. Secondly, we show there is little chance of c failing to collide with any near neighbours; a property which we demonstrate is not true for q. To demonstrate the efficacy of the technique, we define a novel structure MQ-Forest, a modified version of RP-Forest. Both are binary LSH-based ANN mechanisms, but MQ-Forest dynamically estimates a value for c during the query process. We show that MQ-Forest reduces both build and query times by up to 40% when measured over several large, high-dimensional benchmark datasets.

Authors: Meysam Alishahi, Alexander Munteanu, Simon Omlor, Jeff M. Phillips

We prove optimal sampling bounds achieving $(1\pm\varepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions under various regularization terms. This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples. In particular, we prove $k^2/\varepsilon^2$ upper and lower bounds for $\|\cdot\|_2/k$ regularization, and $k/\varepsilon^2$ upper and lower bounds for $\|\cdot\|_1/k$ regularization. For $\|\cdot\|_2^2/k$ regularization, the sampling complexity depends mainly on a bounded derivative property: if $|g'(x)|\leq g(x)$, and $g(0)>0$, and $g$ is monotonic or convex, then it admits linear in $k$ sampling complexity; otherwise the general bound is $k^2/\varepsilon^2$. However, if $g(0)=0$, our results indicate that no dimension-free bounds are possible, and even sublinear bounds are ruled out. All upper bounds are complemented by matching lower bounds up to polylogarithmic terms. Moreover, our work relies conceptually and algorithmically on simple uniform or (squared) norm sampling and hereby improves over recent cubic $k^3/\varepsilon^2$ sensitivity sampling bounds of (Alishahi and Phillips, ICML'24). This is achieved by refined arguments involving higher moment bounds and empirical process analyses to avoid overcounting that appears in the de-facto standard VC-dimension and sensitivity framework.

Authors: Akash Kumar, Abhiruk Lahiri, C. Seshadhri

Consider a bounded-degree graph $G$ that belongs to a minor-closed family (such as planar graphs). Such a graph has a hyperfinite decomposition, wherein, for a sufficiently small $\varepsilon > 0$, one can remove $\varepsilon dn$ edges to obtain connected components of size independent of $n$. (As usual, $n$ is the number of vertices and $d$ is the degree bound.) In a seminal result, Hassidim-Kelner-Nguyen-Onak (FOCS 2009) introduced the partition oracle, a procedure that provides local access to a hyperfinite decomposition. The partition oracle computes the component containing an input vertex $v$ with query complexity (to $G$) independent of $n$. Remarkably, this is done without any preprocessing on $G$. The coordination is done purely through a shared random seed. Despite a line of work on optimizing the query complexity of partition oracles, there were no attempts to bound the size of the random seed. All existing partition oracles use a random seed of size $Ω(n)$, which technically implies a linear setup time. Any blackbox derandomization would likely need $Ω(\log^2n)$ uniform random bits. A natural question is whether the random seed can also have length independent of $n$. We prove the $poly(d\varepsilon^{-1})$-query partition oracles of Kumar-Seshadhri-Stolman can be implemented with a random seed of $poly(d\varepsilon^{-1}) \cdot \log n$ length. To get a deeper understanding on the randomness complexity, we consider a more general model where the vertex labels come from the universe $[N]$, where $N \geq n$. In this setting, we prove that any partition oracle even for cycles requires $ω_N(1)$ random bits.

Authors: Nicholas Zhao

Preparing quantum samples (QSAMPLES), coherent encodings of stationary distributions of reversible Markov chains, is a fundamental primitive in quantum sampling, particularly for quantum simulated annealing. A central limitation of existing phase-estimation-based frameworks is the ancilla qubit overhead. In this work, we present a new end-to-end framework requiring only one ancilla qubit in the working register. The key technical ingredient is a selective phase compiler circuit using one ancilla qubit, built from a generalized quantum signal processing (GQSP)-based projector onto the 1-eigenspace of the qubitized Szegedy walk. Embedding these selective phase compilers into the fixed-point amplitude amplification (FPAA) procedure and iterating yields a quantum algorithm that, given an initial state, oracle access, lower bounds on the overlaps between adjacent states, and lower bounds on the phase gaps, outputs a QSAMPLE within any desired trace distance and thus total variation distance. The query complexity scales inversely with the square roots of both the minimum overlap and the minimum spectral gap of the Markov chains across the cooling schedule, up to polylogarithmic factors. We also perform simulations to verify how our qubit and query complexity evolve with the trace distance, and how this work compares to the previous framework. These results establish two improvements over the previous framework by Wocjan and Abeyesinghe. First, the working-register ancilla cost is reduced to one. Second, by inserting our GQSP-based selective phase compiler into the FPAA procedure, we improve the QSAMPLE transport overlap dependence from inverse minimum overlap to inverse square-root minimum overlap, relative to their Grover pi-over-three fixed-point method. Finally, as a direct application, we apply the quantum algorithm to prepare a Gibbs QSAMPLE and obtain a rigorous complexity analysis.

Authors: Sander Borst, Max Springer

Online bipartite matching, where agents are known in advance but items arrive sequentially and must be irrevocably assigned, is fundamental to problems ranging from ride-sharing to online advertising. When agents belong to classes such as demographic groups or geographic regions, fairness demands equitable treatment across these groups. Recent work introduced class envy-freeness (CEF), a natural extension of the classical fair division notion: an algorithm is $α$-CEF if each class receives value at least an $α$ fraction of what it could extract from any other class's bundle. However, all known algorithms achieving constant-factor CEF guarantees attain utilitarian social welfare (total matching value) of at most $\frac{1}{2}$ times the optimum, far below the $1-\frac{1}{e} \approx 0.632$ achievable without fairness constraints. We resolve the open question of whether fairness necessitates this efficiency loss, by introducing threshold-based algorithms parameterized by $γ\in [0,1]$ that equalize allocations across classes until threshold $γ$, then maximize efficiency. For divisible matching, this yields simultaneous $(1-e^{-γ})$-CEF and $(1 - \frac{e^{γ-1}}{γ+1})$-USW guarantees; for indivisible matching, $\fracγ{2}$-CEF with the same USW. Setting $γ> 0$ produces the first algorithms beating $\frac{1}{2}$-USW while maintaining constant CEF. We complement this with a novel upper bound construction, proving no non-wasteful $α$-CEF algorithm can exceed $\frac{1 +α- e^{α-1}}{1+α}$-USW and correcting prior bounds that were vacuous for $α< 0.58$. Our upper bound nearly matches our algorithms' performance, giving the first substantive characterization of the price of fairness in online class matching.

Authors: Niels Holtgrefe, Jannik Schestag

Identifying a subset of taxa that maximizes Phylogenetic Diversity (PD) is a cornerstone of quantitative conservation planning. Traditionally, PD is defined over a phylogenetic tree in which leaves resemble present-day taxa and the branch lengths capture the estimated evolutionary distinctiveness. While PD maximization is computationally tractable on trees with unit costs, the problem becomes NP-hard when transitioning to phylogenetic networks or to budgeted versions in which protecting taxa incurs non-homogeneous costs. In this paper, we address these two challenges by providing definitions and a comprehensive analysis of three distinct variants of budgeted PD on networks. We conduct our study through the lens of a small structural parameter, node scanwidth (nsw), which measures the "tree-likeness" of a phylogenetic network. We show that two of the considered variants can be optimized in O*(2^nsw B^2) time, where B is the budget. For the computationally harder, third variant, we provide an algorithm to compute PD scores in O*(3^nsw) time. We further contribute the first exact algorithms to compute node scanwidth, recognizing that the utility of algorithms based on nsw depends on the ability to compute nsw and its corresponding decomposition. Our approaches integrate data reduction rules, dynamic programming, and an Integer Linear Programming formulation. We validate our theoretical results through extensive experiments on highly reticulated, simulated networks containing several hundred taxa, using heterogeneous costs. Our implementation computes PD scores and optimal nsw in fractions of a second, even on the most challenging instances. Furthermore, our budgeted optimization algorithms significantly outperform existing benchmarks for computing PD on networks, which were previously limited to unit-cost scenarios. The software makes analyses even on networks with a thousand taxa tracta...

Authors: Diptarka Chakraborty, Arya Mazumdar, Barna Saha, Alvin Hong Yao Yan

Ensuring fairness in algorithmic ranking systems is a critical challenge with significant societal implications for hiring, recommendations, web search, and data management. Standard methods for aggregating multiple preference orders into a consensus ranking may perpetuate and even amplify the lack of representation of underrepresented groups. To address this, recent research has focused on incorporating fairness constraints to ensure the presence of different groups in the top-$k$ positions of the final aggregate ranking. We study two fairness-aware variants under the well-known Spearman footrule, which corresponds to the $L_1$ distance between rankings. First, we address the practically salient task of computing a fair aggregate top-$k$ ranking -- crucial in settings like recommendations and hiring where selection is primarily based on the top-$k$ results -- and present the first optimal algorithm for this problem. Second, we consider fair (full) rank aggregation over all candidates (not specifically on top-$k$). We already know of a $3$-approximation for this fair rank aggregation variant (Wei et al., SIGMOD'22; Chakraborty et al., NeurIPS'22), whereas an exact algorithm exists for the corresponding unconstrained (unfair) version (Dwork et al., WWW'01). Closing the computational gap between fair and unconstrained rank aggregation has remained a tantalizing open problem. We make significant progress by giving a $2$-approximation algorithm for fair (full) rank aggregation, improving substantially over the previous $3$-approximation. Further, we complement our theoretical contributions with experiments on different real-world datasets, which corroborate our theoretical results and demonstrate strong empirical performance relative to state-of-the-art baselines.

Authors: Mugen Blue, Sungjin Im, Alexander Lindermayr

Learning-augmented algorithms have emerged as a powerful paradigm to surpass traditional worst-case lower bounds by integrating potentially noisy predictions. While this framework has seen success in online scheduling, existing work primarily optimizes job latency while relying on frequent, ``blind'' preemptions. This ignores the fundamental trade-off between algorithmic performance and preemption complexity. We provide the first systematic study of learning-augmented scheduling that curbs preemption while optimizing latency. We establish that the gap between theoretical latency bounds and preemption overhead can be bridged with solid analytical foundations. Our results include $O(1)$-competitive algorithms for single and unrelated parallel machines with only $O(1)$ preemptions per job under accurate predictions, with overhead scaling logarithmically with the prediction error. By providing the first bounded-preemption guarantees for unrelated and malleable machines, we extend the theoretical reach of the learning-augmented framework to more constrained and realistic settings. Finally, our algorithms are validated through experiments.

Authors: Clément L. Canonne, Yash Pote, Jonathan Scarlett, Joy Qiping Yang

We introduce the problem of \emph{entropy equivalence testing} for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution testing algorithm is now only required to distinguish, given samples from two unknown distributions $p,q$ and a parameter $\varepsilon \in(0,1/2]$, between $p=q$ and $|H(p)-H(q)| \geq \varepsilon$ (where $H$ denotes the Shannon entropy). We provide a time- and sample-efficient algorithm for this task, showing that the optimal sample complexity for this task can be significantly lower than that of closeness testing. As an application, we leverage this result to provide the first non-trivial testing algorithm for (standard) closeness of low-degree \emph{Bayesian networks}, which significantly improves on either the sample or time complexity of a baseline based on full learning.

Authors: Arnaud Carayol, Pablo Rotondo

In this article, we develop efficient sampling algorithms for random surjections from $[n]$ to $[k]$ for all $n \geq k$. We make no assumption about $n$ and $k$. In particular, we do not make the common assumption that the ratio $\frac{n}{k}$ is constant. All our guarantees are uniform in $n$ and $k$. Our first insight is that all the complexity in sampling random surjections is captured by sampling a smaller structure which we call the \emph{profile} of the surjection. More precisely, the profile associates to each occurring preimage size $s$ the number of preimages of size $s$. Using standard techniques, we show that the problem of sampling surjections reduces to sampling the profile with the induced distribution. This is partly explained by the fact that profiles are always sublinear, with at most $\sqrt{2n}$ entries in the worst case. We provide a complete set of algorithms to directly sample the \emph{profile} of a random surjection with the induced distribution, covering the full parameter space. These algorithms are shown to be optimal up to logarithmic factors in the expected size of the output. Our algorithms are based on exact-size Boltzmann samplers, which are standard rejection-based samplers. We partition the parameter space into three main regions. In each region, we optimize both the rejection rate and the cost of each sampling round. Profiles capture a number of relevant statistics of random surjections and might be of independent interest. In a related context, profiles have been recently studied by Devroye et al. for random mappings. As a spin-off result, we answer an open question from Devroye and Los '25 by providing an optimal algorithm also for the profiles of a random mapping when $k > n/\log n$. The results of this article are not only of theoretical interest but lead to samplers implementable in practice.

In a 1946 paper in the American Mathematical Monthly, Paul Erdős posed the Erdős Distinct Distance Problem and the Erdős Unit Distance Problem.

--------------------------------------------------------------------

THE ERDŐS DISTINCT DISTANCE PROBLEM

A nice high school math competition problem, if it were not fairly well known, is:

Show that for all sets of \(n\) points in the plane, there are at least \(0.5\sqrt{n}\) distinct distances.

A bit harder is to show that there exist \(n\) points in the plane where the number of distinct distances is \(O(\frac{n}{(\log n)^{1/2}})\). The points are the grid points of a \(\sqrt{n}\times\sqrt{n}\) integer grid. 

ADDED LATER:  The set of points is \(\{ (x,y) \in Z\times Z   \colon    1\le x,y\le \sqrt{n}   \} \)

Let \(g(n)\) be the minimum number such that, for every set of \(n\) points in the plane,
there are \(g(n)\) distinct distances. The above results (of Erdős) show that

\( \Omega(n^{1/2}) \le g(n) \le O(\frac{n}{(\log n)^{1/2}}) \)

Erdős made no conjecture about \(g(n)\) in that 1946 paper. However, later papers attribute to him one of two conjectures:

1) \( (\forall \epsilon)[g(n)\ge n^{1-\epsilon}]\)

or

2) \(g(n) = \Omega(\frac{n}{(\log n)^{1/2}})\)

Those papers incorrectly point to the 1946 paper for where he made those conjectures.  I suspect he made those conjectures later in talks or compilations of open problems.

This was a great problem in that there were many papers making progress on it, each one having new ideas. The current best result is that \(g(n) \ge \Omega(\frac{n}{\log n})\).  This result was obtained by Larry Guth and Netz Katz in 2011 and is, by far, the largest leap forward in progress on the problem.  Brass-Moser-Pach (2005) and later Pach-Sharir (2009) observed that existing techniques could never prove \(g(n) \ge \Omega(n^{8/9+\epsilon})\).  I've also heard the observation credited to Rusza. Guth and Katz invented (discovered?) new techniques to obtain their breakthrough.

See my webpage of all papers on the problem here or the Wikipedia page here

Takeaway: The Erdős Distinct Distance Problem saw decades of steady human progress and was eventually almost completely resolved without computer assistance.  I would not have emphasized without computer assistance one year ago.  Maybe not even one week ago.

----------------------------------------------

THE ERDŐS UNIT DISTANCE PROBLEM

Let S be a set of \(n\) points in the plane. Some of the distances between points of S may be 1. How many?  What is the maximum number of unit distances that can occur? Denote this by \(f(n)\). Erdős showed

\( n^{1+\Omega(1/\log\log n)} \le f(n) \le O(n^{3/2}) \).

The lower bound is obtained by using the grid points of a scaled version of the \(\sqrt{n}\times\sqrt{n}\) integer grid. See a writeup by ChatGPT,   here.  We note for later that this can be phrased as using the points in the Gaussian integers, \(Z[i]\).  

In the 1946 paper Erdős conjectured that, for all \(\epsilon\),  \(f(n) = O(n^{1+\epsilon})\).

Joel Spencer, Endre Szemerédi, and William Trotter in 1984 showed \(f(n) = O(n^{4/3})\).

Aside from the Spencer-Szemerédi-Trotter bound, there has been relatively little progress on either the upper or lower bound.

----------------------------------

CONTRASTING THE TWO PROBLEMS

Contrast: The Erdős Distinct Distance problem has seen extensive progress and a large literature. By contrast, although many papers were written on the Erdős unit distance problem, there was little improvement. That changed on May 20, 2026.

------------------------------------------

OPENAI PRODUCES A COUNTEREXAMPLE TO THE ERDŐS CONJECTURE

OpenAI recently produced a counterexample to Erdős's conjecture.  More precisely, OpenAI proved the following:

There exists \(\epsilon>0 \) and a sequence of point  sets \(P_i \subseteq R^2\) such that, letting \(|P_i|=n_i\):

a) \(n_i \rightarrow\infty\), and

b) for all \(i\), the number of unit distances in \(P_i\) is at least \(n_i^{1+\epsilon}\).

The  OpenAI announcement is here. The technical paper is here. 

Note that the author is OpenAI. There are no human co-authors.  However,(1)  Lije Chen used an internal OpenAI model and (2) Mark Selke and Metaab Sawhney verified correctness. (For a comment on the lack of human authors, see Sebastien Bubeck's comment below.) The \(\epsilon\) is not given though one could go through the paper and find it. It would be very small. 

After the initial AI-generated argument (or AI-assisted?) human mathematicians streamlined and clarified the proof. The result is a paper by Noga Alon, Thomas Bloom, W.T. Gowers, Daniel Litt, Will Sawin, Arul Shankar, Jacob Tsimermann, Victor Wang, and Melanie Matchett Wood  that explains the history, the proof, and their reactions to it. That paper is here. They obtain \(\epsilon \sim 6\times 10^{-38}\). 

Recall that Erdős's lower bound was obtained by using points in \(Z[i]\). The new result used more complicated number fields. Indeed, the degree of the number fields used goes to infinity.  For more details see the Alon et al. proof.  

Will Sawin wrote a paper where he obtained \(\epsilon=0.014114\). Quoting his paper:

To do this, we make explicit and sharpen every step of the argument. Interestingly, this rarely makes the argument much more complex. The total length of this paper is essentially the same as the original OpenAI writeup, though longer than the simplified version prepared by human authors [Alon et a.].

His paper is here

-------------------------------------------

 MY POINTS

1) The Erdős's Unit Distance problem is a well known and interesting conjecture, so this is not picking out some obscure problem.

2) AI-generated or AI-assisted? The announcement by OpenAI, and the Alon et al. paper, indicate that the proof is AI-generated.

Fellow blogger Gary Marcus disagrees and argues that it is AI-assisted.  See his post here. 

ADDED LATER: An interview with Gary Marcus is here.

I think this is a hard question, and perhaps there is more of a continuum.  However, I trust Alon et al., so I will go with AI-generated.

3) Humans were still needed to verify and  clean up the proof. In the future, we will all be grad students, verifying and cleaning up what AI outputs.

4) The final proof was readable. One concern about AI proofs is that they would be unreadable and hard to verify. That was not the case here.

5) The ideas needed for the solution already existed; however:

a) The right combination was hard to find.

b) The relevant techniques used, algebraic number theory, are not standard tools in combinatorial geometry.

c) It was widely believed that Erdős's conjecture was true.

d) Producing a counterexample seems less impressive than proving the theorem.  It would be of interest to see if OpenAI could prove the Guth-Katz result; however, that would not work now since Guth-Katz is already out there for OpenAI to see. Perhaps OpenAI should try to improve Guth-Katz. 


6) In the short term, this result and what it portends, is good: math problems we care about will be resolved with the help of AI, perhaps solely by AI. But in the long run we may lose the ability---or at least the patience---to do the proofs ourselves. Note that I am assuming that AI will have future successes---see item 10-ONE for a counterthought.

7) AI seems to be good at combining known concepts. Is it good at coming up with new ones? Are humans? The distinction between combining known ideas and coming up with new ones is very thin.

8) Two contrary lessons:

a) You should know many fields of mathematics so that you can use ideas from one field in another, like the AI did.

b) You should know some field of math really well so you may do something new in it that current AI could not have done.

9) If an AI produces a new treatment for cancer that is cheaper and better than what is known I do not think we will care that an AI did it (though we will have humans check it). Is mathematics similar? Do we care that an AI did it?  Medicine primarily values outcomes; Mathematics also values understanding. Does reading a proof that AI did give the same understanding as coming up with it yourself?  Can AI help with that as well?

10) I suggest two futures:

ONE: While this AI-generated (or AI-assisted) result is impressive, it will be a rare occurrence. This result was actually a counterexample. The needed math was known. The result was interesting. This is a perfect storm that we might not see again for a while.

TWO: Even before the AI revolution, when I came up with a math problem I wanted solved, I would seek help, perhaps too early. My curiosity far exceeds my ego.  Since AI makes it easy to get help, my fear is that eventually we will all be Bill Gasarch---scary.

By gasarch

Let $S\subseteq {\mathbb F}_2^u$ have size $n=2^\ell$, and let $h:{\mathbb F}_2^u\to {\mathbb F}_2^\ell$ be a uniformly random linear map. For $y\in{\mathbb F}_2^\ell$, write ${load}_h(y):=|h^{-1}(y)\cap S|$, and let $M(S,h):=\max_{y\in{\mathbb F}_2^\ell}\{load}_h(y)$ be the maximum load. Jaber, Kumar and Zuckerman (STOC 2025) proved that the expected maximum load of $h$ on $S$ is at most $16\log n/\log\log n$, matching the fully independent keys-into-bins scale up to constants. Their proof also gives the tail estimate \[ \Pr\left[ M(S,h)\ge R\frac{\log n}{\log\log n} \right] \le O\left(\frac{1}{R^{2}}\right). \] We record a base optimization in their exponential-potential method showing that binary linear hashing nearly matches fully independent hashing also at the level of the second-order maximum-load scale. For every $R>1$ satisfying $R\ell^{1-1/R}\ge D\ln\ell$, where $D$ is an absolute constant, we prove \[ \Pr\left[ M(S,h)\ge R\frac{\log n}{\log\log n} \right] \le O\left( \frac{(\log\log n)^2}{R^2(\log n)^{2-2/R}} \right). \] Integrating this tail yields \[ {\mathbb E}[M(S,h)] \le \left( 1+ (1+o(1)) \frac{\log\log\log n}{\log\log n} \right) \frac{\log n}{\log\log n}. \] Thus binary linear hashing matches fully independent hashing in the leading term and matches the dominant second-order correction up to a $1+o(1)$ factor. We also prove, by an independent self-contained argument, a sharp tail bound for one prescribed bucket: for fixed $y\in{\mathbb F}_2^\ell$, \[ \Pr[{load}_h(y)>2^a-2]\le \gamma^{-1}2^{-a^2}, \] where $\gamma=\prod_{j\ge1}(1-2^{-j})$. A subspace construction shows that this is asymptotically tight even in the leading constant as $a\to\infty$. However, this controls only a fixed bucket; a direct union bound over all buckets loses a factor $2^\ell$.

We study the parallel complexity of computing the arboricity of a graph, defined as the minimum number of forests into which its edges can be partitioned. For graphs of bounded treewidth, we present a simple dynamic programming–based parallel algorithm that constructs an optimal partition of the edges into forests. For graphs of bounded genus, we give an alternative and simple parallel algorithm for computing arboricity by adapting Goldberg’s method for finding dense subgraphs.

On mathematics, machines, and what the proof never held

When I was young, I learned about the great Sanskrit poet and playwright Kālidāsa, the author of Śakuntalā and other works whose beauty has survived across centuries. But the story I remember most about him is about a man sitting on a tree branch and cutting the very branch on which he sits. It was usually told as a joke about stupidity, but I could never hear it only that way. The man was absorbed in the motion of the blade, unable to see the branch beneath him. He was not failing at the task. He was doing exactly what he had set out to do, letting the task fill the whole field of attention.

Mathematics has always needed proof. Without it, a claim remains too dependent on the person who made it. Proof allows an insight to be checked by others, long after the circumstances of its discovery have disappeared. It is one of the most beautiful inventions of human thought.

But I have begun to wonder whether, over the centuries, something else happened alongside this beauty. 

Full essay: https://nisheethvishnoi.substack.com/

By nisheethvishnoi