Theory of Computing Report

As most readers have presumably heard by now, Paul Erdös’s Unit Distance Problem from 1946—one of the central open problems from the field of discrete geometry—has been solved by an internal OpenAI model. Erdös had conjectured that, given n points in the plane, at most n^1+o(1) pairs of them could be unit distance apart. Using high-powered results from algebraic number theory, GPT refuted this, constructing a set with n^1+ε unit-distance pairs, for ε ~ 10^-38. Shortly afterward, Will Sawin, a human (!), improved GPT’s construction to get ~n^1.014 pairs. Meanwhile, the best known upper bound remains n^4/3, improving Erdös’s n^3/2.

The entire process seems have been one-shot: my former student Lijie Chen simply gave GPT the problem, then GPT thought for a while and output a several-page argument that, on analysis by human experts, turned out to be correct. Of course there’s selection bias here; we’re not hearing as much about the hundreds of other problems GPT was given that it didn’t solve (isn’t that the case with humans too?). Clearly, too, GPT was helped by the facts that human mathematicians had wasted most of their time trying to prove Erdös right rather than looking for a counterexample, and that, even if they did look for a counterexample, they’d need to be experts in algebraic number theory to find this one, which hardly any discrete geometers are. So, maybe that suggests that AI, right now, is “merely” picking various medium-hanging fruits that human mathematicians missed for contingent reasons? With emphasis on the “right now.”

In a companion paper, OpenAI helpfully included commentary from Timothy Gowers, Noga Alon, Will Sawin, Daniel Litt, and many other experts, reflecting on the breakthrough, the path that GPT took to get to it (which can actually be seen by examining its chain-of-thought), and what this might mean for the future of mathematical research.

I heard the news maybe an hour after it broke, when some UT grad students came to my office to tell me. For what it’s worth: these students were morose, musing about how everything might soon be over for young scientists and mathematicians like themselves. I don’t know whether they’re right, but I feel like I should tell the truth about what their reaction was.

Then, a few days later, a team at DeepMind, including my UT Austin colleague Swarat Chaudhuri, announced that they were able to use a system called AlphaProof Nexus to settle nine more (!) Erdös problems, many of them in additive combinatorics, along with miscellaneous other open math problems. Notably, in this case the AI also fully formalized its proofs in Lean.

And then, just today, Jelani Nelson alerted me to a new CS theory paper, which solves a longstanding open problem about electrical flows on graphs using a proof from GPT5.5Pro.

It seems to me that we’re now over the top of this particular rollercoaster, and it will keep accelerating until we reach the bottom, wherever that might be. I don’t know whether to hope or dread that solutions to P versus NP and all our other great problems will be included in the ride—that our role, as human mathematicians, will be reduced to (at most) deciding which questions we find interesting and then understanding AI models’ answers to those questions.

But maybe that won’t happen. Maybe the new AI mathematicians will soon hit a wall, because they lack the uncomputable quantum gravity microtubules of Penrose and Hameroff, or some other magic human ingredient. The fantastical thing is that, one way or the other, we’re going to find out empirically before very long.

---

Readers may have also seen the news that multiple prizewinning entries in a short fiction contest called the Commonwealth Prize, give overwhelming indications of having been written by AIs. As Kelsey Piper puts it:

There are, let’s say, also some noticeable similarities in the prose style between the winning stories that were flagged for AI use. AI chatbots love metaphors and similes, and they often spit out ones that sound vaguely pleasing but are logically incoherent or ascribe properties to things that don’t make sense.

“The Serpent in the Grove” gave us, “The girl smiled like sunrise over a sink.” “The Bastion’s Shadow” says, “She carried it now in her bag, heavy as a charm.” “Mehendi Nights” describes something as “swaying against plaster like a warning bell.”

The Commonwealth Foundation, whose judges chose these stories, hasn’t exactly covered itself in glory—saying, on the one hand, that it strictly forbids AI use but on the other, that it will continue taking authors at their word that they didn’t use AI, no matter the immensity of evidence to the contrary. As many others have pointed out, judges more familiar with AI would’ve ironically been better placed to notice the signs of its use.

If only there were some sort of automated way to detect AI-generated text. Someone should really get on that problem, don’t you think?

---

But maybe we should just throw in the towel—as some of my colleagues have already done in the context of undergraduate projects? Maybe we should simply say that a good story is a good story, regardless of what manner of entity produced it?

As it happens, just last week I read my very first AI-written story that affected me as a story, to the extent that I wanted to read it more than once. This happened when I gave GPT5.5Pro the following simple prompt:

Write me a story about the most ancient Israelites that’s riveting like the stories of the Bible but that’s also consistent with all of the archeological evidence.

You can read the result here. One of my Facebook friends called it “disturbingly good,” and I share that assessment. Of course, I’m well aware that GPT could easily generate a thousand stories like this one—sampled from the same probability distribution—and then I could even do statistics on which tropes were the most common. This makes it feel silly to overindex on the first story that happened to be output, and yet somehow I did.

---

I feel like at this point, both the prophets of AI utopia like Ray Kurzweil, and of AI doom like Eliezer Yudkowsky, could be forgiven for asking: dude, will you listen to us YET? Do you still find it prudent to call this new form of terrestrial intelligence a stochastic parrot, a laughable fraud, or a fad that’s about to go away? Fear it all you want, hate it even, but at least respect it!

Which brings me to the other big AI news from the past week, namely that Pope Leo released his first encyclical, which is entitled “Safeguarding the Human Person in the Time of Artificial Intelligence.” I read it and … well, I certainly agreed with the theme that such a world-changing technology needs to be developed for the common good (as the Pope would have it, like the walls of Jerusalem), rather than for the profit or vanity of any one individual or company (in his analogy, like the Tower of Babel). I had quibbles with some of the other parts. Zvi Mowshowitz, as he often does, had a superb paragraph-by-paragraph analysis. Amusingly, there are indications that parts of the encyclical were written by AI.

To me, though, maybe the most notable part was that Chris Olah, who leads Anthropic’s interpretability team, was standing next to the Pope at the ceremony, and delivered his own remarks. I felt like Chris, who I met even before Anthropic existed, was a non-obvious yet inspired choice here, one of the rare figures in frontier AI whose technical and moral authority are both completely unimpeachable by anyone.

And so, at this momentous era for the human project, and no less of an authority than that of the Vicar of Christ himself, the Supreme Pontiff and the Successor of Peter, I hereby throw myself on the wisdom and mercy of … uhh, Chris Olah and his team at Anthropic.

Chris, if I am soon to share the earth with entities that can prove the Riemann Hypothesis and solve quantum gravity after 30 seconds of thought, then may you understand those entities well enough to cause them to be nice.

By Scott

Authors: Satoshi Kanno, Rei Nishimura, Hiroshi Yamauchi, Yoshi-aki Shimada

We propose a practical computational framework for detecting structural changes in parameter-dependent topological data. In many applications, such as time-series data analysis, anomaly detection, and monitoring of systems under changing control parameters, persistence diagrams describe the birth and death of topological features at each parameter value, but they do not fully capture how these features are reorganized over time. To address this limitation, we represent homological features by zero modes of the ordinary combinatorial Hodge Laplacian and track the corresponding feature spaces in a common ambient chain space. This allows us to compute curvature and holonomy as descriptors of local reorganization and accumulated memory in evolving topological structures. Curvature highlights parameter regions where homological features mix or change rapidly, while holonomy summarizes the net effect of such changes after a closed cycle. We also establish stability estimates showing that these descriptors are robust under perturbations of the Hodge Laplacian on regular regions. Numerical experiments on controlled time-dependent point-cloud data show that the proposed method detects tracking instability, distinguishes systems with nearly identical persistence diagrams, and captures cycle-level memory invisible to pointwise feature matching. These results suggest that zero-mode transport geometry can serve as a useful computational tool for analyzing dynamic topological data.

Authors: Florent Becker, Phillip Drake, Matthew J. Patitz, Ryder Smith

In abstract models of algorithmic self-assembly, synchronization between attachments has emerged as a crucial distinction between the classical asynchronous model (aTAM) and a new synchronous model, the syncTAM. This paper presents recent advances in gauging the additional power afforded by the syncTAM. While it is known that the syncTAM and the aTAM are each unable to fully simulate the other, this paper offers evidence that the syncTAM is computationally significantly more powerful than the aTAM, especially in the non-cooperative setting. The additional power of the non-cooperative syncTAM is witnessed by the following constructions, all impossible in the non-cooperative aTAM: a flagpole, a strict self-assembly of a variant of the discrete Sierpinski triangle, and the ability to build the same assemblies (modulo scale factor) as directed aTAM systems. The second topic is that of limited synchronization, wherein, when the number of attachments is smaller than some threshold $l$, they happen synchronously, but attachments in excess of that number must wait. In that context, the precise value of $l$ is crucial, and changes to that value prevent simulation and can change which shapes can be obtained.

Authors: Inès Benito, Johannes F. Lutzeyer, Benjamin Doerr

Baldwinian and Lamarckian evolution have existed for a long time in evolutionary algorithms (EAs) without ever dominating the academic literature or practical applications. In this work, we use modern empirical and theoretical methods to revisit Lamarckian and Baldwinian evolution and rigorously compare them with the generic Darwinian evolution. On the empirical side, we run a comprehensive suite of experiments on graphs from six different datasets from the recent GraphBench benchmark on Maximum Independent Set and Maximum Cut problems. Our results show that Baldwinian and Lamarckian evolution consistently outperform Darwinian evolution, confirming the great potential of local search augmented evolutionary algorithms. Notably, in the great majority of cases, all EAs outperform recent deep learning baselines and approach the performance of highly specialised heuristic and exact solvers. We furthermore report a high-performing set of generalist parameters for all studied evolution types that we hope will be of use to practitioners in future. On the theoretical side, we extend the existing Deceptive Leading Block benchmark to arbitrary block length and use tools from modern theoretical runtime analysis to prove upper and lower bounds on the expected runtime. For block lengths greater than two, Baldwinian evolution is asymptotically faster than Lamarckian which is asymptotically faster than Darwinian evolution. When accounting for the cost of the local search procedure in fitness evaluations, the ordering depends on the implementation with Baldwinian evolution staying fastest from small block lengths onwards, explaining its strong empirical performance.

Authors: Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato

We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities which can be found in parallel. Our main result is a disjunctive Positivstellensatz proving that we can keep the degree of each algebraic identity as low as the degree of the polynomial whose nonnegativity is in question. Based on this result, we construct a semidefinite programming based converging hierarchy of lower bounds for the problem of minimizing a polynomial over a compact basic semialgebraic set, where the size of the largest semidefinite constraint is fixed throughout the hierarchy. We further prove a second disjunctive Positivstellensatz which leads to an optimization-free hierarchy for polynomial optimization. We specialize this result to the problem of proving copositivity of matrices. Finally, we describe how the disjunctive sum of squares approach can be combined with a branch-and-bound algorithm and we present numerical experiments on polynomial, copositive, and combinatorial optimization problems.

Authors: Nikolai Maas

Multi-constraint hypergraph partitioning is a generalization of balanced partitioning, where the vertex set of a hypergraph is partitioned such that the inter-block connectivity of hyperedges is minimized while balancing the vertices with regard to $d$ distinct constraints. A prominent class of applications is data distribution tasks, where this allows to achieve good load balance for $d$ different kinds of resources and simultaneously minimize the communication volume. Although the best approaches for single-constraint partitioning are usually complex (multilevel) algorithms with many components, we show that replacing only one component already leads to high-quality multi-constraint partitions: the rebalancing step, which restores balance for a partition that has (hopefully) small connectivity but violates the constraints. We design a multi-constraint rebalancing algorithm based on greedy local search, proving that balance is always restored for $d=2$ and bounded maximum weight. The key is to ensure monotonically decreasing global imbalance by choosing an imbalance metric where there is always a balance-improving move available. Integrating our algorithm into the state-of-the-art partitioner Mt-KaHyPar, we demonstrate an 11.5\,\% geometric mean connectivity reduction compared to the next best competitor (Metis) and better reliability regarding partition balance, even though the majority of inputs is outside of the theoretical guarantee.

Authors: Abhishek Sahu

The \emph{Separation Lemma} is a simple yet powerful tool, akin to the well-known \emph{Isolation Lemma}, that guarantees the uniqueness of certain set sums. Bandopadhyay et al.\ introduced this lemma to establish lower bounds for the \ALP problem with respect to certain structural parameters, relying on random weight assignments in the process. The lemma's applicability extends well beyond that specific work, especially in proving hardness results. However, while effective, these hardness results inherently rely on probabilistic assumptions. In this work, we give a fully \emph{deterministic} construction for the weight assignment required by the Separation Lemma. We provide formal proofs of correctness, explicit examples, and show how deterministic weights can replace randomized ones, thereby derandomizing existing hardness results for path-packing problems. Our exposition highlights a clear progression from the original randomized foundations to deterministic constructions and their practical implications.

Authors: Ali Abbasi, Eli Friedman, Leana Golubchik, Samir Khuller, Marco Paolieri

Given a graph $G$ of $n$ nodes partitioned into facilities and customers, the $r$-edge interdiction covering problem (REIC) is to remove up to $r$ edges so as to maximize the total weight of customers disconnected from all facilities, which is called the covering objective function. While REIC is known to be NP-complete for general graphs, Fröhlich and Ruzika show that the problem can be solved in polynomial time when $G$ is a tree, providing an $O(n^7 r)$-time algorithm. We give an efficient $O(nr^2)$-time dynamic programming algorithm for REIC on trees that is fixed-parameter linear in $n$. Evaluating our solution on a benchmark of randomly generated tree networks with baselines of the Fröhlich and Ruzika algorithm and the Gurobi integer program solver, we demonstrate that in practice, our algorithm is both significantly faster and less sensitive to network topology and size. We extend our algorithm for REIC to graphs of bounded treewidth, a well-studied family of sparse graphs that generalizes trees, and obtain a matching runtime of $O(nr^2)$. We also consider the $r$-facility interdiction covering problem (RFIC), a novel variant of this network interdiction problem where the goal is to remove up to $r$ facilities to maximize the covering objective function over disconnected customers. We show that RFIC is NP-complete by observing it generalizes the small set bipartite vertex expansion problem (SSBVE), also known as the minimum $p$-union problem. We give an $O(nr^2)$-time algorithm for RFIC on trees, which also gives an $O(n^3)$-time algorithm for SSBVE on trees.

Authors: Yewei Yuan, Michele Minervini, Mark M. Wilde, Nana Liu

Principal component analysis (PCA) is traditionally implemented through a covariance or kernel matrix, leading-eigenvector extraction, and hard rank-$k$ projection. These steps can be computationally costly in high-dimensional and quantum-data settings, sensitive to small eigengaps, and unnecessary when downstream tasks only require principal-subspace scores. Such score-based objectives are important in applications such as anomaly detection, spectral-energy profiling, and other postselection tasks. To address these needs, we introduce a measurement-based soft PCA framework replacing the hard top-$k$ projector with an entropy-regularized Fermi--Dirac filter. This filter is the unique optimizer of an entropy-regularized variational formulation of PCA and converges to the classical PCA projector in the zero-temperature limit. This filter has a direct interpretation as a quantum measurement, which naturally suggests a quantum approach. For centered covariance operators represented by quantum feature states, a single fixed circuit, together with threshold calibration, accesses all optimal filters for different rank budgets or retained-variance levels without rank-dependent circuit updates or eigenvector recovery. For new inputs, the same calibrated quantum circuit yields soft principal subspace scores, spectral energy profiles, and postselected filtered states. The required centering of both training and test data is performed coherently inside the quantum protocol, which is particularly important for quantum data where no classical feature vectors or centered Gram matrix are directly available. By reframing PCA as a calibrated measurement task, this framework bypasses the need for iterative eigenvector extraction and achieves a dimension-independent sample complexity $O(η^{-2})$ for normalized fractional-rank or retained variance scoring at additive accuracy $η$.

Authors: Gavin Brown, Ephraim Linder, Mahbod Majid, Vikrant Singhal

We study efficient differentially private algorithms for estimating monotone statistics, i.e., statistics that are monotone under the addition of new observations. The starting point for our investigation is subsample-and-aggregate: a classical paradigm that partitions the dataset into blocks, estimates the statistic on each block, and then privately aggregates the estimates.While practical and generically applicable, this approach is quite data-hungry. We improve upon this framework for the class of monotone statistics -- compared to subsample-and-aggregate, our algorithms save a factor of $t$ in sample complexity and pay a factor of $e^t$ in running time, where $t>0$ is a tunable parameter. We complement our results with a query-complexity lower bound, showing that our algorithms are essentially optimal for this task. As an application, we obtain improved results for private eigenvalue estimation, private loss estimation, and privately estimating a single parameter of a high-dimensional model, e.g., in linear regression.

Authors: Jingbo Liu

We study the query complexity of sampling from high-dimensional Gaussian distributions using gradient information. In the standard oracle model, exact gradients expose only matrix-vector products with the precision matrix, leading to polynomial approximation barriers and a characteristic \(\sqrtκ\) dependence on the condition number. We show that this barrier disappears when the sampler is allowed to query \emph{smoothed scores}, namely gradients of the logarithms of the Gaussian-convolved densities. For a Gaussian target with precision matrix \(Λ\), a smoothed-score query at noise level \(τ\) gives access to the resolvent \((Λ+τ^{-1}I)^{-1}\). Combining geometrically spaced noise levels with sinc-quadrature rational approximation, we obtain a sampler with $q=O\!\left(\bigl(\logκ+\log(e\sqrt d/δ_{\rm TV})\bigr)\log(e\sqrt d/δ_{\rm TV})\right)$ smoothed-score queries for total variation error \(δ_{\rm TV}\), improving the condition-number dependence from \(\sqrtκ\) to logarithmic. We also study finite-bit gradient oracles. Using coordinatewise quantization of the transformed smoothed-score answers and a final dithering step, we obtain a sampling scheme whose total communicated gradient information is polylogarithmic in \(κ\); in particular, for fixed dimension and accuracy, the bit complexity is \(O(\log^2κ)\). To complement these upper bounds, we introduce a channel-synthesis, or reverse-Shannon, converse technique for sampling lower bounds. This converts total-variation simulation guarantees into communication requirements and yields an \(Ω(\logκ)\) lower bound on the required gradient information. Together, these results identify smoothed scores as a provably more informative oracle for sampling and give nearly matching upper and lower bounds for its finite-bit complexity.

Authors: Sergei Tikhonov, Arsen Vasilyan

We study the problem of computationally efficient proper agnostic learning of multidimensional concept classes under the Gaussian distribution. In this setting, given i.i.d. labeled samples from an unknown distribution over $\mathbb{R}^d \times \{\pm 1\}$ whose marginal on $\mathbb{R}^d$ is Gaussian, the goal is to output a hypothesis from a target class $\mathcal{F}$ whose 0-1 loss is within $ε$ of that of the best classifier in $\mathcal{F}$. We give the first efficient proper agnostic learning algorithm for arbitrary Boolean functions of $K$ halfspaces under Gaussian marginals. Our algorithm runs in time $d^{O(K^2 \log(1/ε)/ε^2)} + (K/ε)^{O(K^3/ε^{2.5})}$. Prior to our work, the only known algorithm for $K \geq 2$ was brute-force search, with run-time exponential in $d$. Moreover, the dependence of our run-time on the dimension $d$ matches that of the best known improper learning algorithm, namely $d^{\widetilde{O}(K^2/ε^2)}$. For the special case of a single halfspace ($K=1$), the best previous run-time was $d^{O(1/ε^4)} + (1/ε)^{O(1/ε^6)}$. Our algorithm improves this to $d^{O(1/ε^2)} + (1/ε)^{O(1/ε^{2.5})}$. Once again, the dependence on $d$ matches that of the best known improper algorithm, namely $d^{O(1/ε^2)}$. Furthermore, the dependence of our run-time on the dimension $d$ is essentially optimal in the statistical query model.

Some of the discussion online has been about how not to use AI in making academic talks (see, e.g., this post by Jessica Hullman). A junior researcher asked my opinion on using AI to help make slides and posters. I shared my thoughts with them, and I thought it was worth writing down in a more organized fashion.

I’ll first give my take on the value of making talks by hand (which I don’t think I’m terrible at). I’ll then comment on how AI could fit into the process well or poorly. I will say that I’m not (yet?) a wizard at using AI to enhance my talks, so don’t come here expecting pro tips (except, spoilers, that the process of writing itself is immensely important). Since AI is a fast-moving topic, note that this post was originally written in May 2026, but I don’t think that the general principles here are very dependent on current AI capabilities.

Making talks by hand

Roughly speaking, the contents of a talk can be decomposed into three levels. From highest to lowest level, they are:

• The story you’re telling the audience
• The contents of each slide
• The words you actually say

Before you even make a single slide, you should already have a good idea of the story of the talk, which is your overarching narrative. This includes things like, what is the motivation for studying this problem, which are the important related works to mention, what technical results to highlight, etc.

Designing the story is the single most valuable part in preparing any talk, both in terms of your intellectual engagement with your own research and making sure you give a coherent and educational talk. Every one of these details requires thought and consideration. Why should people care about this problem? What examples illustrate the problem cleanly and intuitively? Which technical results are the most interesting, and how should they be simplified for the purpose of a talk?

Note that all of these story design choices are highly subjective. There is no “one talk” to give about a particular result, and two co-authors of the same paper may prepare and give totally different talks. That type of variance is fine and by design. A talk is meant to give your own perspective on the research results, and that should come through in the story you choose to tell. This is why you shouldn’t rely too heavily on slides from talk already given by a co-author: it’s their story, it doesn’t have to be yours.

The process of designing your story will also help you understand your own results better. Thinking about how to motivate a problem will help you discover new connections. Thinking about a simple example will help you understand the nature of the phenomenon you’re demonstrating. Thinking about which results to present and how to do it (e.g., what to simplify) will help you distill the core technical ideas in your work. The important part is not only the final content on your slides, but the thinking and your process to get there.

Once you design and internalize your story, it will be useful in other settings as well. For example, if you haven’t written the paper yet, it will make the introduction and technical overview much easier to write. And if someone asks you to explain your result impromptu, you’ll be able to do so more clearly.

Thus far, our discussion has been about designing the story. I often find that, when you have a sufficiently clear story in your head, writing it down is very easy. But there is another disconnect, between the words and pictures on the slides and the actual words you say. This is where practice and rehearsal comes in: you’ll frequently find that the most natural way to present a slide is entirely different than what you put down in the first place, and you have to go back and refine the slide afterwards (and potentially iterate). This is another reason why using someone else’s slides is a common pitfall: the way that is natural for you to present a result is not the same way that is natural for them.

It’s not the main point of this post, but a brief comment on delivery. It should be clear to the audience that you care about what you’re presenting about. After all, if you don’t care, why should they? This is of course challenging for some people, who are not naturally charismatic or are afraid of public speaking. But this is a core part of academic research, so it will benefit you to improve at it.

As a final point here, in case it’s not obvious, why is giving good talks an important thing to do? In some sense, being a researcher is being an influencer. Research is inherently an attentionally-driven field. You can have the most brilliant ideas and results, but if no one knows about or understands them, then the value of the research is a fraction of what it could be. A talk focuses all the attention on you and your results, so make the most of the spotlight when you have it.

How can AI help?

I’ll start by outlining ways that AI can hurt you when preparing talks, but end with some suggestions on how it can help you make better talks than you made before.

Using AI too broadly can be disastrous. Suppose you use it to design your entire talk. Then you are completely skipping the sometimes-painful but essential process of coming up with the story. You won’t understand your research as deeply. You won’t have internalized it as you would have if you sweated through it, and you won’t be able to explain the research as clearly in settings when you don’t have AI at your fingertips.

I’ve talked with people who are very anti-AI for writing technical content, due to the value of thinking through the details, but are OK with using AI for helping make talks, since (in their opinion) it’s not the “real” part of research. I disagree strongly with the latter: good communication is an essential part of research, and (hopefully as I’ve argued above) thinking about how to communicate something well is an essential part of the technical component of research.

Using AI too heavily also discards a lot of you from your talks. People came to the talk not only to hear about the research, but for your perspective on the research. The authenticity is very important (and, I believe, will only become more important over time).

This ties into another point, about delivery, where it is important to show that you care about your research. The easiest way to show you don’t care about your research is to dump slop slides (i.e., only lightly edited AI outputs) at your audience. You expect me to believe this is something you care at all about if you can’t spend just a few hours preparing a decent talk? It also signals that you have no respect for your audience. If I catch you presenting slop slides, you will correspondingly lose a lot of my respect for a long time.

AI can also result in slides that have a big disconnect in the content on the slides versus what you would actually say. It’s effectively like having someone else give you their slides. The “AI’s voice” is likely to be entirely different from yours. You can of course refine and iterate on them, but at that point, you might as well just make the slides yourself.

So with this said, what can AI be useful for? AI can be help by giving a second opinion on things. Maybe you’ve done the thinking yourself already (which, as mentioned before, is the important part), and you want to see if there’s any other perspectives you didn’t consider. It might suggest some other ideas that you already thought of and discarded, or other new ones that you hadn’t considered. But you should really think of it as being a second opinion, your own perspective and preferences should still dominate.

AI can also help make content that you wouldn’t have the time or the skills to make before. For example, AI can help make high-quality visualizations, animations, and interactive demos. These tools can help communicate an underlying technical idea much better than just words, but could previously have been too difficult to actually create.

AI models are not going away. You should use them to make your talks better: communicate and express your underlying message in a way you would not have been able to do before. But you should not use them in a way that makes your thinking or your talks worse: stealing away your valuable thoughts, removing what makes you you from your talks, or embarrassing yourself in front of your professional colleagues.

By Gautam

I participated today in the successful Ph.D. defense of Nikolas Patris, a student of my newly-tenured colleague Ioannis Panageas. Nikolas has been working on problems of learning Nash equilibria of games and more generally finding saddle points of smooth functions, a crossover area between theoretical computer science and machine learning. His results are theoretical but his papers on them are in machine learning conferences:

• “Exponential Lower Bounds for Fictitious Play in Potential Games”, NeurIPS 2023, arXiv:2310.02387
• “Computing Nash Equilibria in Potential Games with Private Uncoupled Constraints”, AAAI 2024, arXiv:2402.07797
• “Learning Nash Equilibria in Rank-1 Games”, ICLR 2024
• “Improved Bounds for Online Facility Location with Predictions”, AAAI 2025
• “(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games”, ICML 2026, arXiv:2601.23248

The main theme of his thesis and defense was that games can have a nice structure and still not be efficiently learnable. He started with a positive result from ICLR 2024: if the difference of the two payoff matrices of a two-player game has rank one, then the problem of finding an approximate equilibrium strategy can be reduced to a one-dimensional search over a parameterized family of zero-sum games, and approximately solved in very few iterations by an algorithm that alternates between trying to learn how to play one of these zero-sum games, and adjusting the parameter to find a game in the parameterized family that more accurately approximates the rank-one game the algorithm is really trying to solve. Rank zero is just the case of zero-sum games themselves, and for rank two it is already \(\mathsf{PPAD}\)-complete to find an equilibrium.

Next in the defense, he discussed exponential lower bounds for certain game-learning strategies. He started with cooperative games in which both players have equal payoffs; in these it is trivial to find the right strategy from a game matrix but it is still interesting to understand how quickly one can converge using simple iterative methods that do not know the matrix explicitly. He started with fictitious play in which each player chooses the move that would have the best average payoff against the previous move history. In work from NeurIPS 2023, using a game matrix containing a hidden spiral path of improving payoffs, he showed that this strategy takes factorial time to make each successive step along the path and therefore factorial time (in the number of game options) to converge to an approximately-optimal strategy. He summarized this idea, that averaging the entire past history produces a significant slowdown in convergence time, as “history creates inertia”. The same factorial slowdown also applies to “follow the regularized leader”, a family of learning algorithms with smoother dynamics that involve mixed rather than pure game strategies (ICML 2026).

In \(n\)-player games with two options per player, the slowdown is even worse. Here, the two-dimensional payoff matrix of a symmetric two-player game is replaced by a hypercube of payoffs (with equal payoffs to all players) with a dimension for the two choices of each player. Instead of a spiral path, Nikolas observed that a hidden path of improving payoffs could be realized using a solution to the “snake in the box problem”, asking for the longest induced path in a hypercube. Solutions to this problem, for an \(n\)-dimensional hypercube, have length \(\Omega(2^n)\), although the optimal constant of proportionality remains unknown. Plugging in the factorial slowdown for each step along the path, for both fictitious play and follow the regularized leader, gives a doubly exponential lower bound on the convergence time (ICML 2026). However, here the multidimensional payoff matrix has exponential size, so the slowdown is only singly exponential in the description complexity of the game instance. This motivates an interesting and unsolved variation of the snake-in-the-box problem: is it possible to find an exponentially long induced path in the hypercube so that determining whether a hypercube vertex is on the path, and if so how far along the path it lies, can be computed in polynomial time? If so it would give a concisely-represented multiplayer game with convergence time doubly exponential in the representation size.

Even more generally, he considered follow the regularized leader as a method for finding saddle points of smooth functions and showed that, in this general context, it does not even reach stationarity.

Nikolas has still not settled on what to do next; he has a good postdoc offer but also has some conflicting geographic constraints. Regardless, he has produced a strong dissertation, and I was especially impressed at how clearly he explained these concepts that were in many cases not very familiar to me. Congratulations, Nikolas, and also, congratulations, Ioannis!

(Discuss on Mastodon)

By David Eppstein

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: Hamid Shafieasl, Jeff M. Phillips

We introduce a rotation-invariant representation of planar shapes. In particular, this representation encodes shapes as vectors such that the Euclidean distance between them serves as a valid shape distance. For standardized, star-shaped objects, we can deterministically create a sketched vector of dimension $O(1/\varepsilon)$ in $O((1/\varepsilon) \log (1/\varepsilon))$ time that approximates this shape distance to within $\varepsilon$. Moreover, because the representation is a standard Euclidean vector, we can directly and efficiently perform various data analyses, such as nearest neighbor search and clustering, in shape space, inherently invariant to the rotation of the shapes. We demonstrate this through a series of simple experiments. The key technical contribution operates on functions over $\mathbb{S}^1$, which we use to encode standardized objects. The most general rotation-invariant representation of these functions works through a map to an infinite-dimensional function space, parameterized by an offset parameter. By analyzing special discretized cases of these functions, we show that the representation is strictly injective up to the desired rotation and a mirror-flip-type operation we call \emph{reverse of complement} (RoC). While RoC status can be controlled by how the function is defined, it is inherent to the representation and required to be handled in the analysis. Regardless, the vectorized representation is robust to small shape perturbations, and hence discretizing the angles leads to the efficient approximation and algorithm.

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.

Authors: Michael Dinitz, Bob Dong

``Algorithms with predictions'', or ``learning-augmented algorithms'', has proved to be an extremely useful paradigm for combining machine learning with traditional algorithms. One of the textbook settings for this is searching a sorted array. Without a prediction, classical binary search takes $O(\log n)$ queries, while with a prediction we can use ``doubling binary search'' to find the target key using $O(\log η)$ queries, where $η$ is the error of the prediction measured as the absolute value of the difference between the true location and the predicted location. Since an array is just a path graph, in this paper we ask whether similar bounds can be achieved for search on even slightly more general graphs: trees. We show first that the high-level answer is ``no'': there is no search algorithm that uses $O(\log η)$ queries, where $η$ is now the graph distance between the predicted location and the true location. However, as our main result, we show that such bounds can be achieved on trees which are ``path-like'' in that they have low \emph{pathwidth}. In particular, we prove that there is a search algorithm which uses at most $O(k \log η)$ queries, where $k$ is the pathwidth of the tree. We also prove a lower bound showing that our algorithm has existentially optimal query complexity. Finally, we show experimentally, on real-life inputs, that our algorithm has query complexity which is notably better than the simple non-prediction-based algorithm.

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.