Theory of Computing Report

I’ve recently been rereading Steven Levy’s “Hackers” with my daughter. Levy describes how Brautigan’s 1967 poem “All watched over by machines of loving grace”  was inspiring to the California  “Hardware Hackers” of the 1970s and organizations such as Community Memory. 

In 2026, the phrase “all watched over by machines of loving grace” conjures an image of humanity cradled in the arms of a powerful and aligned (“humanity loving”) AI: an AI benevolent dictator. Indeed in his essay titled “machines of loving grace”, Dario Amodei suggests (while acknowledging deep uncertainty) that one form of the future economy might be organized around AI systems (aligned to human values) that determine how to “give out resources … to humans based on some secondary economy of what the AI systems think makes sense to reward in humans.” This seems to place the AIs as parents who control and take care of the material needs of their human children and decide how to reward or punish them. To me, such an “AI parent” looks rather close to a benevolent dictator.¹

Regardless of whether you think AI as a loving parent is a good or bad outcome, Brautigan and (more importantly) the California hackers had quite a different and more decentralized vision. In the 1960s, computers were large machines made by companies such as IBM. They were hated by many on the left and considered part of the military industrial complex. But there was a group who combined leftist politics (or at least an anti establishment attitude) with a love of technology, and believed that computers could become tools of decentralization and liberation. To do that, the giant expensive computers would need to give way to small and cheap machines. This is what the “hardware hackers” were about, and this is the movement that led to the Apple II and the personal computer revolution.

Today, like the IBM mainframes of the 60s,  AI systems are large and expensive, and are  increasingly being integrated in military applications. Once again, many people on the left (and recently on the right as well) have strong hate and fear of this technology. While some apprehension may be justified, by refusing to engage with AI and acknowledge its capabilities, these constituencies are making themselves less relevant to shaping AI’s progress. Also, while the U.S. is leading the frontier, we are falling behind on open weights AI, and closed models are facing increasing restrictions. All of these trends do not bode well for a more decentralized future.

Scaling laws tell us that the way to increase intelligence is through ever more resources—- compute, data, power. Hence, unlike the 1970s, AIs are not getting smaller and more distributed, but rather bigger and in ever larger data centers. In his essay, Amodei described AGI as “a country of geniuses in a data center.” But who is the ruler of this country? Is it the AI company who owns the data center? The AI itself?

Given the trend toward bigger and more expensive systems, it is possible that the few parties that can afford such systems capture all of the economic value they generate. Furthermore, if AIs are more intelligent than us, the temptation to give them more control for economic or military advantages may be hard to resist. I worry that concentration of power, whether in the hands of a few entities or the AI itself, could be the “default path.” But this choice is not inevitable.  

I am as “bitter lesson pilled” and “scaling law pilled” as anyone. I agree that ultimately, intelligence is simply computation, regardless of whether it takes place over proteins or silicon, and increasing the computing units will increase intelligence. But this does not determine the social or economic outcome. Yes, AI systems will become more powerful and far more intelligent than we are. No, it doesn’t mean we need to accept AI dictators, benevolent or otherwise. Nor does it mean that only the government and a few labs should have access to advanced AI. We could go down the path of centralized control but we don’t have to do so. People, institutions and legislators can make choices on how to trade off efficiency, safety, and individual autonomy. They don’t have to sacrifice the latter for the former.

Some might claim that market and capitalism forces will drive people to cede control to AIs. But the economy is ultimately about what humans value. Humans are social animals and we give value to goods (e.g. gold) not because of their intrinsic value but because of how other humans value them. AI will radically change what we value, though it is hard to predict in what ways. I am not even sure that economic concepts such as productivity, labor, capital, and GDP will continue to make sense in the post AGI world. Physicists know that “more is different.” As scientists studied new scales, whether galactic or subatomic, they needed to invent new theories, from Newtonian physics to general relativity and quantum mechanics. Perhaps we would need a new type of economy.

Others might say that given its power, safety requires AI to be controlled by either the government, a “safety conscious” lab, or the aligned AI itself. The risks are real—  I work on AI safety myself. But we should also remember the long history of using threats to take away people’s freedoms. Some of these threats were real— there were actually many Soviet spies during the McCarthy period and the NSA dealt with real terrorist organizations during Snowden’s time there. But in hindsight we realized that the tradeoff wasn’t worth it. We should invest in safeguards but be empirical about both the risks and the efficacy of our methods. Trying to achieve perfect safety against all risks, real and imagined, is not only doomed to fail but will cost us our liberty in the process. 

AI’s risks can lead to an “ends justifies the means” mindset: the “good guys must win” and they or the “good AI” must be in charge. But if we want a human centered and decentralized future, then no one entity should be in charge. No party should have a monopoly on intelligence. That includes the AI itself: while we can and should train in guardrails, the personality of the model, as good as it is, is never a substitute for our democratic process.

The U.S. survived and thrived in the last 250 years not because our presidents have all been saints or geniuses, but because of our system of checks and balances. I hope that we can keep such a system in place for the next 250 years, and to ensure that we humans are free to pursue our happiness in the way we define it. This requires that the distribution of AIs power is “baked into the DNA” of how we build and deploy this technology. If we fail to do so, then just like bloody revolutions often lead to authoritarian regimes, we may not be able to get to a decentralized future via centralized means.

Acknowledgement: I decided to write this post following a discussion on AGI with Sam Altman. However, the views here are my own, and do not represent Sam, OpenAI, or Harvard.

Notes:

¹ As mentioned, Amodei admits uncertainty about the matter; See  also “The Adolescence of Technology”. There are many parts in both essays that I agree with.

By Boaz Barak

Last Monday we had  an afternoon session of the Annual Meeting of the Israeli Mathematical Society celebrating Micha Perles’ 90th birthday. The speakers were Nati Linial, me, Noga Alon,  Ron Adin, and Rom Pinchasi. There was a very nice attendance and quite a few former students of Micha came to the event.

Some photos

  

In the top row Micha with eleven former Ph. D. students and with five former women Ph. D. students. Below: lectures, greetings, and the audience.

The lectures Nati Linial, Adventures with polytopes

Abstract: To the best of my recollection, I first heard about polytopes only when I started to attend Micha’s seminar, but with time, I found myself studying them myself. Fondly remembering the many things that I learned from Micha, I will tell about my most recent foray into this realm.

The bi-stochastic matrices form a polytope, in which every permutation matrix is clearly a vertex. The Birkhoff-von-Neumann theorem says that this exhausts the list of vertices. An array of non-negative reals is called tri-stochasic if every row, column, and shaft in it sums to 1. These arrays form a polytope too, where every Latin squares is clearly a vertex. However, as we show, Latin squares are only a vanishingly small minority of the vertices.

Joint with Zur Luria and Maya Trakhtman arXiv:2604.09290. Nati’s Slides.

Gil Kalai, Reflections on some old problems and results

Abstract: I will describe some problems and results of Micha A. Perles, and his students about polytopes, convex sets and point configurations, from the seventies and eighties of the 20th century, and some progress made over the past decades.

My slides.

Noga Alon, Micha and shattering

Abstract: The Sauer-Perles-Shelah lemma is a fundamental result in extremal combinatorics with applications in discrete geometry, computional learning, probability, combinatorics, model theory, property testing, social choice, and more. After very brief comments about the original result, I will describe some recent variants and extensions.

Noga’s slides.

Ron Adin, Circular sorting

Abstract: What is the maximal number of steps required to sort n labeled points on a circle, by swapping points in adjacent positions? What if we swap adjacent values, rather than adjacent positions? What if we allow arbitrary (not necessarily adjacent) swaps?
These are circular analogues of well-known sorting problems, with applications in various computational sciences. We will describe exact results, as well as bounds, obtained using combinatorial, probabilistic and number theoretic methods.

Based on joint works with Noga Alon, Eli Bagno and Yuval Roichman. Ron’s slides.

Rom Pinchasi, 30 years later– on the occasion of the 90th anniversary of Micha Perles

Abstract: In honor of Micha Perles’ 90th anniversary we will bring some of the many anecdotes that were not mentioned by previous speakers. We will combine these fun and beautiful memories from 30 years ago with some research and results that constitute my own private memories with Micha. The 90th anniversary of Micha Perles is a milestone for many people in the community of discrete geometry and combinatorics. Could it also be the end of the classical era of mathematics in some sense? We will know the answer by the 100th anniversary of Micha Perles. I promise many more anecdotes then.

Rom Pinchasi’s lecture had three parts. The first part was about the Kupitz-Perles conjecture (that I also mentioned more briefly in my lecture; see this post and this one). The second part was about Rom’s M. Sc. thesis about skips (דילוגים) in planar point configurations (but for time constraints, Rom skipped most of it.) The third part described Rom’s daring Program for proving Erdos distance one conjecture. (It is too late now, since the conjecture was refuted ; Seriously, it could still be useful if you want to prove the conjecture for, say, points in .

 

By Gil Kalai

Authors: Beniamin Bibrowski, Tomáš Masařík

Let $\mathcal F$ be a graph class that is closed under topological minors and 1-sums, has decidable membership, contains a triangle, and is not the class of all graphs. Recently, Lee, Liu, and Tsai [ICALP 2026] showed that the edge-decomposition problem into $k \geq 3$ elements of $\mathcal F$ is NP-hard. In particular, their general hardness reduction covers a long-standing problem on outerthickness (when $\mathcal F$ is the class of outerplanar graphs). On the other hand, it is well known that decomposing a graph into forests is polynomial-time solvable, as implied by work of Edmonds [J. Res. Natl. Bur. Stand. B. 1965]. In this paper, we take a first step toward determining the complexity of edge-decomposition problems into just two graphs (the case $k=2$). We consider the simplest possible graph class $\mathcal F$ satisfying the criteria above: the triangular forests, that is, graphs in which every 2-connected component is a triangle. We prove that determining whether a graph can be edge-decomposed into two triangular forests is NP-complete.

Authors: Omid Yaghoubi, Mikołaj Bojańczyk, Aliaume Lopez, Rafał Stefański

The goal of this paper is to propose a unifying model for Nerode-style characterizations of regularity across functions with different output domains. Building on Hauser's work in communication complexity, we generalize the setting by relaxing the computability assumptions and allowing non-Boolean output domains. We consider functions of type $Σ^* \to \domain$, where $Σ$ is a finite alphabet and $\domain$ is an arbitrary domain. For several domains, we show that the model coincides with known models of computation. We further conjecture that an analogous correspondence holds for other domains that currently lack a Nerode-style characterization of regularity, and we provide ample supporting evidence. In the model, an input string $w$ is split as $w = w_1 w_2$ and distributed between two cooperating parties, Alice and Bob, who exchange a constant number of messages to compute the value of the function. Each message is either an element of the output domain or a signal drawn from a finite set of signals, and the parties must produce the correct output for every admissible split $w = w_1 w_2$. We further extend the framework to infinite alphabets in the setting of nominal sets, and investigate its expressiveness on languages of words with atoms.

Authors: Jan Krajicek

Ilango (FOCS 2025) invented effectively zero-knowledge proofs, a new variant of zero-knowledge. We reformulate it in the language of logic and give simple proofs (under the same assumptions as Ilango (FOCS 2025)) of its existence and of the key property defined in Ilango (FOCS 2025) that it is "indistinguishable from true" (that property is in Ilango (FOCS 2025) a part of the definition of the prover, not its consequence). Using the theory of proof complexity generators we show that the concept can be turned it into a genuinely zero-knowledge proofs, assuming a conjecture from the theory about the existence of a hard generator and allowing the parties to share a common random string.

Authors: Phillip Kerger

We study the deterministic query complexity of minimizing a convex Lipschitz function over a $d$-dimensional Euclidean ball using only exact function values. At accuracy $Θ(d^{-1/2})$, the previously applicable lower bound was $Ω(d)$, inherited from the stronger full first-order oracle, while an upper bound from Protasov's value-only method requires $O(d^2\log^2 d)$ evaluations. By providing a lower bound of $Ω(\,\frac{d^2}{\log(d+1)})$ on the oracle complexity in this setting, we thereby close this gap dating back to 1996, up to polylogarithmic factors. Furthermore, we are able to lift this result to the mixed-integer setting: Mixed-integer convex optimization with $d$ continuous and $n$ discrete variables using function values requires $\tildeΩ(d^2\cdot 2^n)$ queries.

Authors: Chinonso Onah, Stuart Hadfield, Kristel Michielsen

We study the separation of geometric effects from quantum interference in quantum optimization algorithms. Constrained optimization problems such as routing, assignment, and scheduling are often encoded as product spaces of local variables, together with global feasibility penalties. The central algorithmic question we address is how a constraint-preserving mixing operator transports quantum amplitude across an exponential search space in the presence of local and global constraints. We develop a framework that separates three effects that are usually intermixed: amplitude transport, coherent interference among transported amplitudes, and problem-dependent classical postprocessing. We show that the mixing operator alone does not have a target-seeking ability. Concretely, the normalized distribution induced by its amplitude transport moves toward the distance profile of a uniformly random configuration. Thus, quantum sampling advantage may only arise when the phases of the many computational paths reaching a target configuration are sufficiently aligned for their amplitudes to reinforce. We show that, when the cost phases are engineered so that these paths add coherently, a number of circuit alternations growing only logarithmically with problem size suffices to convert the sum of their absolute contributions into a lower bound on the target amplitude, yielding a certified success probability independent of the ambient Hilbert-space dimension, the search-space size, or the feasible-set cardinality. We develop applications to problem-specific transpilation diagnostics, scalable hardware probes, constraint-induced classical maps of quantum-generated samples, the attribution of solution quality between the quantum distribution and classical post-processing in hybrid quantum-classical workflows and connections to distance-partitioned product spaces from classical coding theory.

Authors: Tahmina Khanam, Hamid Laga, Mohammed Bennamoun, Guanjin Wang, Ferdous Sohel, Farid Boussaid, Anuj Srivastava

We introduce a novel mathematical framework for analyzing and generating complex tree-shaped 3D objects, such as botanical trees and plants, which deform both in their 3D geometry and branching structure. Unlike previous works, which either consider only the skeletal structure of tree-like objects or approximate their 3D geometry using branch thickness, the proposed framework accurately models both the 3D geometry of the tree branches and the way they are interconnected. In this paper, we first generalize the Square Root Normal Fields (SRNF) representation, originally proposed for the statistical analysis of genus-0 surfaces, to tree-shaped 3D objects. We then treat tree-shaped 3D objects as points on a novel Riemannian tree-shape space equipped with a novel Riemannian metric that measures the amount of surface bending and stretching, and structural changes one needs to apply to one 3D tree-shape to align it with another. This way, deformations become trajectories in this novel tree-shape space. We analyze the theoretical properties of this novel tree-shape space and the corresponding metric and develop algorithms for computing point-wise and branch-wise correspondences and geodesic paths between complex 3D trees. We finally show how to use these building blocks for (1) computing statistical summaries, \ie means and modes of variation, of collections of tree-shaped 3D objects, and (2) synthesizing novel tree-shaped 3D objects by sampling from probability distributions fitted to a population of tree-shaped 3D objects. We demonstrate the performance and utility of the proposed framework on real and synthetic plants and botanical trees and show that it significantly outperforms the state-of-the-art.

Authors: Afonso S. Bandeira, Dmitriy Kunisky, Petar Nizić-Nikolac, Lucas Pesenti, Robert Wang

The hypergraph Moore bound conjectured by Feige (2008) controls the size of the smallest even cover in a $k$-uniform hypergraph in terms of the average density of hyperedges. An even cover is a set of hyperedges covering each vertex an even number of times, generalizing the notion of a cycle in a graph, so the size of the smallest non-trivial even cover provides a notion of hypergraph girth. Recent work starting from the breakthrough result of Guruswami, Kothari, and Manohar (2022) proved the conjecture up to polylogarithmic factors, whose exponents were later gradually improved. We give a simple proof of Feige's original hypergraph Moore bound conjecture for all even $k\ge 4$, with no superfluous polylogarithmic factors. Our proof roughly follows the proof of the graph Moore bound, but works with colored walks in a Kikuchi graph built from a hypergraph and controls their growth using a polynomial interpolation method.

Authors: Rudranarayan Kar, Praneet Kumar Patra, Diya Roy, Abhishek Sahu

Telephone broadcasting is a classical model for spreading information in a network. Given a connected graph $G(V,E)$ with source vertex $s$, each informed vertex may inform exactly one uninformed neighbor in every time step. The \textsc{Broadcasting} problem asks whether all vertices can be informed within $t$ steps; the minimum such value is the broadcast time $b(G,s)$. A related variant considers the worst-case source, $b(G)=\max_{u\in V} b(G,u)$. Both variants are NP-hard, and every $n$-vertex graph satisfies $b(G,s)\ge \log_2 n$. Fomin \textit{et al.}~\cite{fomin2023parameterized} recently gave FPT algorithms for this problem under several structural graph parameters. Instead of computing optimal broadcast schedules, we study faster approximation algorithms that produce valid schedules. We improve the $O^*(3^n)$ exact algorithm of Fomin \textit{et al.} to an $O^*((3-f(x))^n)$ algorithm with a $+x$ additive approximation, where $f(x)>0$ is a constant for every fixed $x$. We also give approximation algorithms on graphs of bounded vertex integrity, including a polynomial-time $+2k$ additive approximation algorithm. Complementing these positive results, we prove parameterized hardness for vertex cover above maximum matching ($\mathrm{VC}-\mathrm{MM}$), dominating set size, and graph diameter, indicating that FPT algorithms for these parameters are unlikely. Finally, we present a $+2$ additive approximation algorithm for distance-to-clique running in $O^*(2^{O(k\log k)})$ time, a $2$-factor approximation algorithm for distance-to-path running in XP time, and a polynomial-time algorithm for polar graphs.

Authors: Tommaso Cesari, Roberto Colomboni

We prove an effective-resistance bound for fixed-rank external-field measures. Let $d\ge2$ be an integer, let $m\in\{1,\ldots,d-1\}$. Let $w\in(0,+\infty)^d$, and let $\mathsf S$ be an $m$-element random subset of $[d]$ distributed according to the rank-$m$ external-field measure with weights $w$, i.e., \[\mathbb P(\mathsf S=S)=\frac{\prod_{i\in S}w_i}{e_m(w)},\qquad S\subseteq\{1,\dots,d\},\quad|S|=m,\] where \[e_m(w):=\sum_{\substack{T\subseteq\{1,\dots,d\}\\|T|=m}}\prod_{\ell\in T}w_\ell\] is the $m$th elementary symmetric polynomial in $w_1,\ldots,w_d$. Let $X:=(X_1,\dots,X_d)^\top$ be its indicator vector, i.e., \[X_i=\mathbb I\{i\in\mathsf S\},\qquad i\in\{1,\dots,d\}.\] Let $Σ:=\operatorname{Cov}(X)$, put $v_i:=Σ_{ii}$ for each $i\in\{1,\dots,d\}$, and let $\mathbf e_1,\ldots,\mathbf e_d$ denote the standard basis of $\mathbb R^d$. Our main result is that, for every $i\ne j$, \[(\mathbf e_i-\mathbf e_j)^\topΣ^\dagger(\mathbf e_i-\mathbf e_j)\le\frac1{v_i}+\frac1{v_j},\] where $Σ^\dagger$ is the Moore-Penrose pseudoinverse of $Σ$. As a consequence, if \[v:=(v_1,\ldots,v_d)^\top,\qquad D:=\operatorname{diag}(v),\qquad V:=\sum_{i=1}^dv_i,\] then, as a corollary, we obtain \[Σ\succeq\frac12\left(D-\frac{vv^\top}{V}\right),\] which establishes a factor-two relaxation of the normalized covariance bound conjectured by Anari, Haqi, and Ma. As a further corollary, combining our theorem with the recent framework of Anari, Haqi, and Ma yields a constant-stretch guarantee for correlated sampling on the hypersimplex without relying on the still-open normalized covariance conjecture assumed in their conditional result. Our result improves the logarithmic-in-$k$ stretch bound of Naor, Raju, Shetty, Srinivasan, Valieva, and Wajc to a constant and resolves the open question posed in their work.

Authors: Hans-Joachim Böckenhauer, Dennis Komm, Emanuel Skodinis, Moritz Stocker, Philip Whittington

We study the online proportional knapsack problem with two paid forms of recourse. Items arrive one by one and must be handled immediately, without knowledge of the future: an algorithm may pack an item $x$, reject it, or reserve it for possible later use at proportional cost $αx$; additionally, it may at any time remove previously packed items, at proportional cost $βy$ for each removed item $y$. Reservation and removal have each been analyzed in isolation, but their combination raises a natural question: is the better of the two mechanisms always optimal on its own, or is there a region in the parameter space spanned by $α$ and $β$ in which they genuinely enter into a symbiosis? So far, this question has only been answered for the special case of free removal ($β= 0$), leaving the vast majority of the parameter space unexplored. We close this gap, determining matching upper and lower bounds on the competitive ratio for every pair of cost parameters $(α, β)$ and revealing three qualitatively different regimes. In some regions, reservation alone already achieves the optimal ratio; in others, removal alone does. However, most interestingly, in the heart of the parameter space lies a symbiosis region in which combining both mechanisms is strictly better than either one on its own. The optimal algorithm in the symbiosis region is a natural blend of the two known single-mechanism strategies: postponing commitment by reserving until a threshold is reached, then packing greedily and revising via removal.

Authors: Yunbum Kook

Inspired by interior-point methods (IPM) for structured convex optimization, Kannan and Narayanan introduced the Dikin walk for sampling uniformly from polytopes in 2009. As in IPMs, the Dikin walk is affine-invariant, and its convergence is governed by the barrier geometry used to define its local proposal. They showed that the Dikin walk with the logarithmic barrier for a polytope in $\mathbb{R}^{d}$ with $m$ linear inequalities mixes in $md$ iterations. In 2017, Chen, Dwivedi, Wainwright, and Yu improved this to $d^{2.5}$ using a Lewis-weight barrier, and conjectured that the correct mixing time should be $d^{2}$. We make progress toward this conjecture by improving the previous $d^{2.5}$-mixing bound. For exponential sampling over a polytope, we prove that the Dikin walk with a scaled Lee--Sidford metric mixes from a warm start in $d^{2.25}$ iterations. This also yields an improved cold-start complexity via a known annealing framework. The main technical ingredient is improved average self-concordance of the Lee--Sidford metric, which gives high acceptance probability for the Metropolis filter along a random Dikin proposal. While previous analyses were effectively limited to second-order control due to technical difficulties, we develop a principled higher-order analysis. The proof combines a selective higher-order expansion of recursive bottleneck terms, a moving orthonormal-frame calculus for higher derivatives of the Lewis weights, and Wiener-chaos decompositions via multiple stochastic integrals to control the resulting Gaussian polynomials.

Authors: Thomas L. Draper, David G. Harris, Feras A. Saad

We develop an efficient online algorithm to sample a sequence of discrete random variables using an entropy source of i.i.d. fair coin flips, in a standard model of real computation where real-valued probabilities are represented by rational approximations. For any sequence $F_1, F_2, \dots$ of probability distributions, our sampler generates $n$ outputs $X_1 \sim F_1, \dots, X_n \sim F_n$ using at most $\mathbb{E}\left[H(F_1) +\dots + H(F_n)\right] + O(\log n)$ coin flips in expectation while carrying $O(\log n)$ bits of persistent space, where $H$ is the Shannon entropy. Under standard assumptions, we prove that the space used by our sampler to achieve this information-theoretically optimal entropy rate is asymptotically optimal. The key idea is to replace the global arithmetic-decoding sampling scheme of Han and Hoshi (1997) with a local discrete uniform state, yielding an exponential reduction in space for a given entropy loss. Our approach applies to distributions with irrational probabilities and countably infinite supports, generalizing recent randomness-recycling methods beyond finite rational distributions with bounded denominator.

Authors: Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, Konstantin Makarychev

We study phase transitions and algorithms for refuting CSPs arising in hierarchical clustering (as well as ranking, and ordinary CSPs). Here, $n$ variables are assigned to leaves of a tree, so as to satisfy $m$ constraints, specifying evolutionary relationships. Two canonical $NP$-hard optimization problems are Triplet and Quartet Reconstruction, where the input consists of triplets $xy|z$ or quartets $xy|zw$, and the goal is to find a tree $T^*$ maximizing agreement with constraints. Our main results are (as density $λ=m/n$ increases): 1. We show the existence and precisely locate the sharp threshold $λ^*\approx1.2277$ for Triplets (via closed-form solution). To the best of our knowledge, this is the first sharp threshold for the broad family of Phylogenetic CSPs. Moreover, we give a lower and upper bound for Quartets. 2. We provide strong refutation algorithms that certify that $val(T^*)\le5/9 + ε$, where $val(T^*)$ is the fraction of constraints satisfied by the (unknown) optimal tree. For triplets, our algorithm succeeds w.h.p if $m =Ω(n)$, and for quartets if $m = Ω(n^{3/2})$. 3. We obtain strongest possible refutations at slightly larger densities (for triplets $m=O(n^{3/2}\log ^3n)$, for quartets $m=O(n^2)$): we certify that $T^*$ is no better than a random assignment, i.e., $val(T^*)\le 1/3+ε$. In fact, we obtain strongest possible refutations for finite-alphabet CSPs with or without negations. Our refutations above are instantiations of our general theorem that applies more broadly to Phylogenetic and Ordering CSPs (and all CSPs failing to support $t$-wise independence), and generalizes the current algorithmic frontier on refuting random CSPs~\citep{allen2015refute}. A crucial difference here, unlike Boolean CSPs, is that there are no negated variables, so prior works relying on negations -- a source of randomness -- do not apply.

Authors: Han Luo, Ziyi Yang, Jingquan Luo, Ziruo Wang, Yuexin Su, Xiaoming Sun, Lvzhou Li, Tongyang Li

The Elliptic Curve Discrete Logarithm Problem (ECDLP) is a fundamental problem in cryptography, and reducing the resource requirements of quantum algorithms for solving ECDLP is an important goal. In this work, we present a space-efficient quantum algorithm for solving the ECDLP over prime fields, achieving an implementation with only $3n+6\lfloor \log_2 n \rfloor+O(1)$ logical qubits and $919n^3/\log_2 n+O(n^2)$ Toffoli gates, where $n$ is the bit-length of the prime. For a 256-bit prime-field curve, our construction requires only 835 logical qubits, reducing the previous best estimates of 1098 and 1175 logical qubits by Chevignard et al. [EUROCRYPT 2026] and Babbush et al. [ArXiv Preprint 2026], respectively. The key to our improvement is a new space-efficient reversible modular inversion circuit, which addresses the dominant space bottleneck in affine-coordinate point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing technique of Proos and Zalka by introducing length registers and location-controlled arithmetic to compactly store and update intermediate variables. We further optimize the reversible update procedures and construct the corresponding controlled arithmetic circuits, resulting in a modular inversion circuit implemented by only $2n+6\lfloor \log_2 n \rfloor+O(1)$ logical qubits and $195n^2+O(n\log_2 n)$ Toffoli gates. This modular inversion circuit together with mid-circuit measurements and classical feed-forward operations provides a space-efficient controlled affine point-addition circuit and a complete implementation of Shor's algorithm for ECDLP.

Authors: Satyabrata Jana, Shivesh K. Roy, R. B. Sandeep

Vertex splitting replaces a vertex (v) by two nonadjacent vertices whose neighborhoods together equal (N(v)). A split is \emph{exclusive} if these neighborhoods are disjoint and \emph{shallow} if no newly created vertex is split again. For a graph property (Π), \textsc{(Π)-Vertex Splitting} asks whether at most (k) splits can transform a graph (G) into one satisfying (Π). We continue the systematic study of this operation and settle several open problems. First, we prove that \textsc{Cograph Vertex Splitting} is \textsf{NP}-complete, even on graphs of girth at least 5, resolving a question of Firbas and Sorge (ISAAC 2024). More generally, \textsc{(P_t)-free Vertex Splitting} is \textsf{NP}-complete for every fixed (t\geq 4). We also prove that \textsc{Chordal Vertex Splitting} and \textsc{Unit-Interval Vertex Splitting} are \textsf{NP}-complete, resolving two questions of Abu-Khzam, Chakraborty, Isenmann, and Oijid (IWOCA 2026). Our hardness results extend to the exclusive and shallow variants. Assuming the Exponential Time Hypothesis, none of these problems admits an algorithm running in (2^{o(k)}n^{O(1)}) time; moreover, except for the unit-interval cases, none admits an algorithm running in (2^{o(n)}) time.

Authors: Carlos Bravo-Prieto, Weiyuan Gong, Antonio Anna Mele

Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be $Θ(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$, where $d_{\mathrm{in}}$ and $d_{\mathrm{out}}$ are the channel input and output dimensions, respectively, and $\varepsilon$ is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires $Ω(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$ queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound $O(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$. Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case $d_{\mathrm{in}}=1$. By contrast, coherent protocols with quantum memory achieve query complexity $Θ(d_{\mathrm{in}}^2 d_{\mathrm{out}}^2/\varepsilon^2)$. Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.

Authors: Vignesh Viswanathan

We present an $(e^{1/e} - c)$-approximation algorithm for maximizing Nash social welfare under additive valuations, for some constant $c > 0$. This result improves upon the previous best-known approximation factor of $e^{1/e}$ [Barman, Krishnamurthy and Vaish, EC 2018].

Authors: Jan Höckendorff, Felix Hommelsheim, Christian Sohler, Di Yue

The minimum spanning tree (MST) problem is one of the most basic optimization problems on metric spaces and graphs. We study the problem of computing a $(1+ε)$-approximation to the MST of an $n$-point metric space $(X, \mathbf{d})$ of doubling dimension $\mathrm{ddim}$. In doubling metrics, previous deterministic algorithms incur a running time with dependence $ε^{-O(\mathrm{ddim})}$. We give a deterministic algorithm that computes a $(1+ε)$-approximation to MST in time $2^{O(\mathrm{ddim})} n \bigl(\log n + ε^{-1} \log^4(1/ε)\bigr)$. For bounded doubling dimension, this improves the previous dependence on $ε$ from $ε^{-O(\mathrm{ddim})}$ to essentially linear in $ε^{-1}$. Moreover, as a special case, our result improves the previous best deterministic running time for bounded-dimensional Euclidean metrics due to Arya and Mount~[SODA'16] by almost a factor of $ε^{-1}$. We also show that, unlike in bounded-dimensional Euclidean spaces, MSTs in bounded doubling metrics can have arbitrarily large maximum degree, while every doubling metric nevertheless admits a $(1+ε)$-approximate MST of maximum degree $2^{O(\mathrm{ddim})}\log(1/ε)$.

Authors: Yang Hu, William Kuszmaul, Jingxun Liang, Stefan Walzer, Huacheng Yu, Renfei Zhou

Quadratic probing is one of the most widely used open-addressing hash-table schemes in practice, but after more than half a century, even its most basic performance guarantees remain poorly understood. In this paper, we revisit quadratic probing through the lens of a smoothed variant in which each key follows a random probe sequence where its $k$th probe is expected at offset $Θ(k^2)$. This is simultaneously a toy model for better understanding regular quadratic probing and a natural hashing scheme in its own right. We analyse smoothed quadratic probing for both Robin Hood ordering and anti-Robin Hood ordering and reveal a surprising separation: At load factor $1-\varepsilon$, anti-Robin Hood achieves an expected query time of $Θ(\log \varepsilon^{-1})$, which matches the conjectured expected average successful query time for regular quadratic probing, while Robin Hood falls short at $Θ(\varepsilon^{-1/2})$. Our analysis generalises to degree-$d$ probing for any $d \ge 1$ with expected query time $O(\max(\log \varepsilon^{-1}, \varepsilon^{1-2/d}))$ for anti-Robin Hood and $Θ(\varepsilon^{-1/d})$ for Robin Hood. Finally, we go beyond smoothed analysis: using the probabilistic method, we show that for every $d \ge 2$, almost every random fixed-offset degree-$d$ probing sequence achieves expected query time $O(\log \varepsilon^{-1})$ under anti-Robin Hood ordering, simultaneously over all admissible table sizes and load factors. Thus, while quadratic probing itself remains elusive, we prove that essentially all quadratic-probing-like fixed-offset schemes achieve the ideal performance under the anti-Robin Hood ordering.

Authors: Michał Szyfelbein, Dariusz Dereniowski

In this work, we study various graph partitioning problems under a general demand model. In each such task, we are given a graph $G=(V,E,c,w)$ with a capacity function $c\colon E\to \mathbb{N}$ and a demand function $w\colon V\times V\to \mathbb{N}$. Our main focus is the problem of finding a cut $(S, \bar{S})$ minimizing the quantity \[ ψ_w( S ) = \frac{c( S, \bar{S} )}{w( S, V )\cdot w( \bar{S}, V )}. \] Here, $c( S, \bar{S} )$ is the cost of edges between $S$ and the complement of $S$, $\bar{S}$, and $w( S, V )=w( S )+w( S, \bar{S} )$ is the sum of the internal demand within $S$, $w( S )$, and the demand between vertices of $S$ and $\bar{S}$, $w( S, \bar{S} )$. We call $ψ_w( S )$ the \emph{generalized conductance} of the cut $(S, \bar{S})$, and the task of minimizing $ψ_w( S )$ the Generalized Conductance Problem. Our main contribution is an algorithm with an $\mathcal{O}(\log n)$-approximation guarantee for this objective. Our result is achieved via a two-way reduction: first to the well-known Generalized $k$-Multicut Problem, and then to a constrained variant of the classic Sparsest-Cut Problem, with an additional upper-bound constraint on the amount of demand that may be cut. Moreover, we show that the above procedure can be used to obtain an $\mathcal{O}(\log n)$-bicriteria approximation for Graph Partitioning with Demands, where the goal is to find a minimum-cost subset of edges $C$ such that for every component $H$ of $G\setminus C$, $w( H )\leq ρ\cdot w( V )$. This, in turn, yields an $\mathcal{O}(\log n)$-approximation for Hierarchical Clustering with Demands, the problem of finding a hierarchy of cuts that partitions the graph into increasingly refined clusters. For multiplicative demand functions, we improve these guarantees to $\mathcal{O}(\sqrt{\log n})$ and for trees we get an $\mathcal{O}(1)$-approximation for all of our objectives.

Authors: Michał Szyfelbein, Dariusz Dereniowski

Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster becomes a singleton. We relax the halting condition of the recursive process to stop whenever the remaining cluster is a graph belonging to a class $\mathcal{F}$. We call this problem Hierarchical $\mathcal{F}$-Clustering and we measure the quality of any solution using adapted Dasgupta's clustering objective. We study two natural choices of $\mathcal{F}$: trees and graphs of bounded diameter. We present the first polynomial time $\mathcal{O}(\log n\cdot\log\log n)$ and $\mathcal{O}(\log n)$-approximation algorithms for clustering into trees and bounded diameter graphs respectively. Our main technical contribution is a framework for approximating such problems based on linear programming. In fact, we characterize graphs classes $\mathcal{F}$ for which our approach can be applied and show that it includes both trees and bounded diameter graphs. However, our ideas are not limited to them and might be useful for other structures as well. Broadly speaking, our framework applies whenever the corresponding flat clustering problem, which we call $p_{\mathcal{F}}$-Partitioning, admits a natural ILP formulation together with a rounding procedure with provable approximation guarantees. Intuitively, given a set of vertices called terminals, the problem is to find an edge set whose removal results in satisfying certain vertex-dependent structural predicate for each terminal. We then use these ingredients to build clustering trees with the aforementioned approximation guarantees. To complement these results, we show that both Hierarchical Clustering into trees and into bounded diameter graphs cannot be approximated within any constant factor under the Small Set Expansion Hypothesis.

Authors: Igor Pak, Daniel Soskin

We give an algebraic branching program of polynomial size which computes Cayley determinant of right quantum matrices. This is a rare example of an efficient computation of a noncommutative determinant, and the first such example for quantum groups. We extend the results to the $q$-Cayley determinant of $q$-right quantum matrices, as well as to their multiparameter generalization. The proofs are entirely combinatorial, as we relate Cayley, Moore and Valiant determinants using bijections/involutions on words. We then employ the celebrated determinant construction of Mahajan and Vinay (SODA'97), to obtain the results.

The recent breakthrough work of Chatterjee, Ghosh, Gurjar, Raj and Thierauf [CGGRT26] gives the first deterministic NC algorithm for the bipartite matching problem. They show how to detect as well as find perfect matchings in bipartite graphs in NC. In this note we present an arguably simpler-to-state variation of the NC detection criterion of [CGGRT26], with improved parameters.

• Another mathematics journal leaving its commercial publisher (\(\mathbb{M}\)), but with a twist: usually this is accomplished by a mass resignation of the editorial board. But in this case, Communications on Pure and Applied Mathematics is owned by the Courant Institute and was published by Wiley, so taking it in-house is just a matter of not renewing the contract. The causes of friction were increased publisher interference with editorial decisions (the usual), but also editor dissatisfaction with the publisher’s editorial management software.

• An American privacy emergency (\(\mathbb{M}\)): Cynthia Dwork on how new US government regulations forbidding the Census Bureau from masking its released data under differential privacy will give us less usable data, reduced protection against privacy-violating disclosures, or both. Cynthia also provides information about what you can do to help work against this.

• A reduced planar body with area greater than \(\pi\Delta^2/4\) (\(\mathbb{M}\)), new preprint by Scott Duke Kominers. Here, “reduced” is a concept for two-dimensional convex bodies that is closely related to having constant width. The directional width is the distance between parallel support lines, constant width means that all directional widths are the same, thickness means the minimum directional width, and reduced means that any convex body that is a proper subset has smaller thickness. So bodies of constant width are reduced but not necessarily vice versa. For instance both Reuleaux triangles and equilateral triangles are reduced; the first has constant width, the second does not. A structure theorem described in the paper states that reduced bodies have parts of their boundary with constant width and parts that are flat.

  Anyway, it had been conjectured that the formula in the title was the maximum area for a reduced body of thickness , with bodies attaining that area including the circular disk and quarter-disk. As evidence for the conjecture, it is true both for shapes of constant width and for polygons. But the paper describes a shape resembling a sharper wedge of a disk than a quarter, with a rounded apex, that slightly betters this area.

• Ed Pegg sent me the image below (\(\mathbb{M}\)) illustrating some of the minimal geometric independent dominating sets (small sets of grid points with no three in line to which no additional grid point can be added) from my EuroCG’21/CGTA’23 paper with Aichholzer and Hainzl, “Geometric dominating sets – A minimum version of the no-three-in-line problem”. See also Ed’s Wolfram community post about these sets.

  

• Geometric models by A. Harry Wheeler in the Smithsonian Institution (\(\mathbb{M}\)). Another set of Wheeler models that for some reason doesn’t appear in the main list: Dissected polyhedra transformable into other polyhedra. For more on Wheeler, see Wheeler’s Wikipedia biography

• Shachaf observes that, in the computable reals, you can find the values of a sorted list but you cannot determine its permutation, in response to another post claiming that sorting code that doesn’t explicitly discuss permutations is “awful”. But this raises questions about constructive type theory: how can you specify that this is a sorting algorithm without having a decidable notion of equality?

• Does anyone know a reference for the following easy theorem about estimating area by counting lattice points (\(\mathbb{M}\)), extending Nosarzewska’s inequality from convex to simply-connected regions?

  Let \(J\) be a region of area \(a\) bounded by a Jordan curve of length \(p\). Then:

  \[|a - \#(\mathbb{Z}^2\cap J)| = O(p+1).\]

  Proof: sweep a unit square around the boundary of \(J\); by Cavalieri’s principle the area of the swept region \(B\) is \(\le 1+p\sqrt 2\). Consider the Voronoi cells of the integer lattice; outside of \(B\) they are completely inside or completely outside \(J\). Therefore,

  \[\begin{align}a-1-p\sqrt 2&\le \operatorname{area}(J\setminus B)\\&\le \#(\mathbb{Z}^2\cap J)\\&\le \operatorname{area}(J\cup B)\\&\le a+1+p\sqrt 2.\end{align}\]

• Emacs org-mode adds support for using ltx-talk in \(\rm{\LaTeX}\) to produce accessible slides in tagged pdf format (\(\mathbb{M}\)).

• Two-sided ruler constructions (\(\mathbb{M}\)). A series of blog posts by David K. Butler on how to use an unmarked ruler with two parallel edges to do almost everything that you could do with a ruler and compass.

• Reformatted schedule for the International Congress of Mathematicians (\(\mathbb{M}\)) with MathJax abstracts that don’t require clicky popups to read, by M.-J. Dominus.

• OpenAI claims a very short proof of the cycle double cover conjecture (\(\mathbb{M}\)).

• Chris Staecker live-tweets the figures for an in-progress digital topology book, deliberately omitting any explanations of the figures.

• Terry Tao on Gilbreath’s conjecture (\(\mathbb{M}\)). The first difference sequence of the prime numbers starts 1, 0, 2, 2, 2, 2, 2, 2, 4, … . The second, third, and fourth difference sequences all start with 1, 2, 0, 0. The first numbers in each sequence must be odd and the rest even, but which odd number? Gilbreath and before him Proth conjectured that every difference sequence begins with 1. Merely having the same small gaps and parity properties as the primes does not suffice: see my old blog post “Anti-Gilbreath sequences” for sequences with these properties whose difference sequences have infinitely many non-1 starting values.

  The primes are thought to behave similarly to random sequences, so researchers have attacked the problem by studying prime-like random sequences. Past work by Chase shows that sequences whose gaps between consecutive elements are random with very slow growth (slower than the primes) almost surely have all but finitely many difference sequences beginning with 1. Now a new preprint by Chase, Tao, and Zach Hunter, using a structural characterization of anti-Gilbreath sequences related to my post, extends Chase’s work to a model of random sequences with geometrically distributed random gaps of sizes matching the prime numbers. It still doesn’t address the actual prime numbers but I think by matching their distribution better it provides strong evidence for the conjecture.

• How LLM nonsense is affecting Wikipedia: increased drama and increased volunteer workload triggered by “crap articles generated by LLMs, or people using LLMs to write extremely wordy, unhelpful replies to concerns about their behaviour”.

By David Eppstein

Herman Chernoff passed away on July 6, 5 days after turning 103. Ravi Boppana wrote a guest post about Chernoff's life for his 100th birthday. 

Let me talk about his most famous work, the Chernoff Bounds themselves.

If you have a coin that will be heads with probability \(p\), and you flip it \(n\) times, the expected number of heads is \(pn\). Informally Chernoff bounds says that for large \(n\) the number of heads will be quite close to \(pn\) with an exponentially small probability of being far away from \(pn\). For example, if you flip a coin with probability 30% chance of being heads 10,000 times, the probability that you will get at most 2500 heads is less than \(10^{-18}\).

More formally, for \(\delta \in (0,1)\), Chernoff's bound shows that

\[\Pr[|X - \mu| \geq \delta\mu] \leq 2e^{-\mu\delta^2/3}\]

for \(\mu = \mathbb{E}[X]\). I find the variation known as Hoeffding's inequality \[\Pr[|X - \mu| \geq t] \leq 2e^{-2t^2/n}\] easier to use for computational complexity.

Chernoff bounds play a major role in computational complexity, for example you can use Chernoff Bounds for probabilistic, quantum and interactive proof algorithms to reduce the error to exponentially small. That means using the union bound, a single random sequence will give the correct answer for all inputs, showing that BPP is in P/poly. 

Chernoff bounds are a key ingredient in the proof that MA (prover then verifier) is contained in AM (verifier then prover). Roughly you make the MA error so small that the same random coins work no matter what the prover might say. MA in AM plays a key role in the proof that NP in BPP implies PH in BPP which itself is necessary for Toda's theorem.

The proof of Chernoff bounds comes from a simple trick: Rather than bounding \(\Pr[X \geq a]\) directly via Markov's inequality on \(X\), you apply Markov to \(e^{tX}\) for a free parameter \(t > 0.\) Since \(e^{tX}\) is nonnegative,

\[\Pr[X \geq a] = \Pr[e^{tX} \geq e^{ta}] \leq \frac{\mathbb{E}[e^{tX}]}{e^{ta}},\]

and then you optimize over \(t\). The quantity \(\mathbb{E}[e^{tX}]\) is the moment generating function, and for a sum \(X = \sum_i X_i\) of independent variables it factorizes into \(\prod_i \mathbb{E}[e^{tX_i}]\). That factorization is what converts a linear tail bound into an exponential one, each independent term contributes multiplicatively, so the deviation probability shrinks like a product rather than a sum.

Chernoff did not think of himself as a theorist. 

People regard me as a theoretical statistician, but I’ve decided in recent years that I’m really an applied statistician. My theoretical insights have relied upon my work in thinking about applied problems.

A good lesson for us all.

By Lance Fortnow

Authors: Vaibhav Krishan, Sundar Vishwanathan

The class $ACC^0$ consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with $AND, NOT$ and $MOD_m$ gates, where $m$ is a natural number. At the frontier of our understanding lies a widely believed conjecture asserting that $MAJORITY$ does not belong to $ACC^0$. A few years ago, Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach towards this conjecture. Torus polynomials approximate Boolean functions when the fractional part of their value on Boolean points is close to half the value of the function. They reduced the conjecture that $MAJORITY \notin ACC^0$ to a conjecture concerning the non-existence of low degree torus polynomials that approximate $MAJORITY$. We reduce the non-existence problem further, to a statement about finding feasible solutions for an infinite family of linear programs. The main advantage of this statement is that it allows for incremental progress, which means finding feasible solutions for successively larger collections of these programs. As an immediate first step, we find feasible solutions for a large class of these linear programs, leaving only a finite set for further consideration. Our method is inspired by the method of dual polynomials, which is used to study the approximate degree of Boolean functions. Using our method, we also propose a way to progress further. We prove several additional key results with the same method, including lower bounds for approximating the $AND$ function, lower bounds when the approximating polynomial is symmetric, showcasing the power of our machinery.

Authors: Bruno Cavalar, Susanna F. de Rezende, Matthew Gray, Rahul Santhanam

We show the following hardness results for monotone learning and approximation of monotone circuit size: 1. Under the Randomised Exponential-Time Hypothesis (rETH), it requires time $n^{Ω(\log n)}$ to PAC-learn monotone formulas with $n$ input bits and size $s(n) = n$ by monotone circuits of size $n^{(\log n)^{1-ε}}$, for every $ε> 0$. 2. Under the Randomised Exponential-Time Hypothesis (rETH), for any $δ> 0$, there is a polynomially bounded function $m$ such that $m^{1-δ}$-multiplicatively approximating the minimum monotone circuit size of a monotone function consistent with a sequence of $m(n)$ labelled examples $\{(x_i, b_i)\}$ over $n$-bit inputs requires time $m^{Ω(\log(m))}$. Our results are shown by a novel application of lifting arguments in proof and communication complexity to hardness of monotone learning, by building on the seminal result of Atserias and Müller (J. ACM, 2020) on hardness of automating Resolution proofs.

Authors: Ho-Lin Chen, Xiang Huang

Current analog complexity theory, built on the General-Purpose Analog Computer (GPAC) model and polynomial ODEs, allows unbounded state variables -- an assumption that is physically unrealistic for chemical reaction networks and other laboratory-scale analog computers. We develop a bounded analog complexity theory in which all state variables remain in compact intervals and physical time (wall-clock time) is the only diverging resource. Our main technical contribution is bounded surrogate compilation, a compilation framework that transforms unbounded polynomial ODE systems into bounded ones while preserving computational limits and time-to-precision guarantees. We prove that if a system is compiled into a bounded system through our algorithm, the wall-clock time of the compiled system is polynomial in the arc length and physical time of the original system. We exhibit concrete constructions demonstrating fine-grained bounded time complexity -- a tunable polynomial-degree family, a Lambert-$W$-based system achieving $Θ(r\log r)$ time-to-precision (where $r$ is the desired precision parameter, in nats: $|x(t)-α|

Authors: Mikhail V. Volkov, Yinfeng Zhu

We determine which digraphs admit an edge labeling by letters from a finite alphabet such that the resulting labeled digraph is a completely reachable automaton. Such digraphs are recognizable in polynomial time; however, the problem becomes NP-complete when the size of the label alphabet is fixed. We also classify the digraphs for which every edge labeling results in a completely reachable automaton.

Authors: Avner Kantor

Snooker folklore holds that no single stroke can pocket all twenty-one object balls. We examine the claim in an idealized but fully specified model of billiard dynamics. Within the model we exhibit an admissible configuration of the twenty-two balls and a stroke of the cue ball that pockets all twenty-one object balls, and we show that the set of such strokes has positive Lebesgue measure in the natural shot space: total clearances are not flukes of measure zero but open events. For the regulation opening configuration we conjecture the same and explain both why a simulation cannot settle the conjecture by brute force and what kind of computation could settle it in principle. Monte Carlo experiments in the same model estimate the probability P(k) that a uniformly random stroke pockets exactly k balls; the observed decay of P(k), extrapolated conditionally on the conjecture, places the probability of a total clearance from the break far beyond anything observable. The folk claim is thus right in practice and wrong in principle, and the gap between the two is exactly the distance between measure zero and unobservably small.

Authors: Mark Jones, Jannik Schestag

Phylogenetic Diversity (PD) is a fundamental measure of biodiversity, originally defined on phylogenetic trees and widely used in conservation biology. Phylogenetic trees are often generalised to directed acyclic graphs, called phylogenetic networks. As such, a corresponding generalization of PD is needed. A natural generalization to edge-weighted phylogenetic networks is the all-paths measure, where the diversity of a set S of species (taxa) is defined as the total weight of all edges that lie on a path from the root to at least one species in S. While maximizing PD on trees can be solved in polynomial time, the corresponding problem on networks is NP-hard and difficult to approximate. We undertake a systematic parameterized complexity study of the Max-All-Paths-PD (MapPD) problem. We establish W[2]-hardness when parameterized by the number of species that are included in a solution, and W[1]-hardness for the number of species that are excluded. On the positive side, we show that the problem is fixed-parameter tractable with respect to the threshold of diversity and the acceptable loss of diversity. We further analyze how the network's proximity to a tree influences algorithmic behavior and present single-exponential fixed-parameter algorithms when parameterized by the number of reticulations and by the treewidth of the underlying graph. Finally, we present a polynomial kernelization for MapPD with respect to the number of reticulation edges.

Authors: Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda

We show that every planar graph with $n \geq 3$ vertices admits a 4-coloring in which each color is used on fewer than $n/2$ vertices. This bound is the best possible. Moreover, such a coloring can be found in $O(n \log n)$ time. We also extend these results to five or more colors and to graphs on general surfaces.

Authors: Stephan A. Fahrenkrog-Petersen, Aleksander Figiel, Darya Melnyk, Tijana Milentijević, Stefan Schmid

The stable marriage problem appears in many privacy-sensitive domains, for example in the National Resident Matching Program in the US. In such applications, preserving the privacy of users' preference lists is essential to prevent strategic manipulation, discourage misreporting, and comply with data protection regulations. In this work, we investigate privacy attacks on stable marriage algorithms. Assuming that the attacker (e.g., the hospitals) can repeatedly interact with the stable marriage algorithm, we demonstrate how such interactions can reveal private preferences of the non-malicious side (e.g., the residents). We show that the widely applied Gale-Shapley Matching Algorithm, where the proposers' side is malicious, is vulnerable to privacy attacks and all honest agents' preferences can be revealed. We further investigate which preference distributions of the honest, non-malicious side are susceptible to privacy attacks and show that the Gale-Shapley Matching Algorithm where the honest side proposes can preserve privacy in non-susceptible preference distributions. We extend our results to the decentralized setting and show that the attacker's side can infer all preference orderings. In an experimental evaluation, we test privacy attacks on synthetic and real-world data and show that real-world data is indeed susceptible to privacy attacks. This work underlines a need for new privacy-preserving stable marriage algorithms.

Authors: Elena Grigorescu, Shreya Nasa, Cameron Seth

The optimal sample complexity of testing if an $n$-vertex graph has an independent set of size $ρn$, or is $\varepsilon$-far from having an independent set of size $ρn$, was established to be $\widetilde{O}(ρ^3/\varepsilon^2)$, in a notable result by Blais and Seth (SICOMP 2025). In contrast, for $q$-uniform hypergraphs, there is a significant gap between the best known upper and lower bounds, and there has been no progress on the problem for the last two decades. In this work, we prove a new upper bound of $\widetilde{O}\!\left(\frac{qρ^{2q-3}}{\varepsilon^2 (q-2)!^2}\right)$ on the sample complexity of testing the $ρ$-independent set property. The previous best known upper bound was $\widetilde{O}\!\left(\frac{2^q q! ρ^{2q}}{\varepsilon^3}\right)$, due to Langberg (RANDOM 2004). This establishes the optimal dependence on $\varepsilon$ and gives an exponential improvement in the dependence on $q$. We prove our result via a new application of the hypergraph container method.

Authors: Sitan Chen, Weiyuan Gong, Qi Ye, Zhihan Zhang

Unlike in finite dimensions, quantum information in continuous-variable systems has the peculiar feature that without imposing physical constraints, the sample complexity of state tomography can be unbounded. Remarkably, this is even the case for state-of-the-art protocols for learning Gaussian states, which have finite-dimensional descriptions: the best known rates scale with $\log \log E$, where $E$ is the energy of the system. We prove this is not an artifact of existing analyses, but a fundamental limitation of the measurements used. We show: (1) Any protocol that uses Gaussian measurements, even entangled or adaptively chosen ones, must incur a $\log \log E$ dependence. This answers an open question posed by a number of previous works. (2) There is a smooth tradeoff between the number of rounds of adaptivity and the energy dependence, and we give a matching protocol achieving this interpolated rate. (3) With highly entangled, non-Gaussian measurements, one can learn $n$-mode pure Gaussian states with $O(n^2 / ε^2)$ samples, independent of $E$. This answers an open question posed by Chen et al. (4) A simple protocol based on the single-copy canonical phase POVM of Holevo and Helstrom learns single-mode pure Gaussian states with $O(1/ε^2)$ samples, again independent of $E$. Our results clarify the role of energy in bosonic state tomography and shed new light on the intriguing interplay between adaptivity, entanglement, and magic in quantum learning.

Authors: Siddharth Mitra, Vishwak Srinivasan, Xiuyuan Wang, Andre Wibisono

We show the Randomized Hamiltonian Monte Carlo (RHMC) algorithm has accelerated mixing time guarantees for sampling from log-concave probability distributions. RHMC proceeds by repeatedly simulating the continuous-time Hamiltonian dynamics for some random integration times, and resetting the velocity to be an independent Gaussian random variable between each simulation. We show that when the target distribution is log-concave and satisfies an $α$-Talagrand inequality (for example, if the target distribution is $α$-strongly log-concave), if we use a random integration time from either the triangular or the exponential distribution with mean $Θ(α^{-1/2})$, then RHMC converges exponentially fast in KL divergence, and the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(α^{-1/2} \log(\varepsilon^{-1}))$. We also show that when the target distribution is log-concave, if we use a sequence of random integration times from the triangular distribution with exponentially increasing means, then the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(\varepsilon^{-1/2})$. Our analysis relies on a bound on the average KL divergence along Hamiltonian dynamics, which is inspired by an analogous result on accelerated optimization methods based on Hamiltonian dynamics.

Authors: Peter Kiss, Mohammad Sharifi

We study the online preemptive matching problem, in which the edges of a graph arrive sequentially and the algorithm must maintain a matching by accepting or rejecting arriving edges and possibly discarding previously accepted ones. We prove a new upper bound of $0.5661$ on the competitive ratio achievable for the problem. This bound applies to arbitrary randomized algorithms, bipartite graphs and if we allow the algorithm to output a fractional solution. Our result improves upon the strongest previously known upper bound of $2-\sqrt{2} \approx 0.585$, due to Huang et al. [SODA'19]. Previous hardness constructions relied on edge sequences described by vertex arrivals where each arriving vertex reveals its edges to yet unvaried vertices. Under such sequences, Huang et al. showed that there exists a non-preemptive online algorithm with competitive ratio $\sim0.567$ (or $2-\sqrt{2}$ for fractional solutions). Consequently, our hardness construction is the first result which shows hardness for instances where the optimal algorithm employs preemption.

Authors: Moses Charikar, Jon Kleinberg, Chirag Pabbaraju

Motivated by the power of large language models, there has been renewed interest in the Gold-Angluin model of language identification in the limit, with an eye toward variants of the model that might overcome the negative results for its original formulation. Recent papers on this question have proposed looking at computational traces and annotations of training strings as a source of additional power for a learner, reflecting empirical regularities such as the way that commented source code is easier to learn from than arbitrary source code, and text annotated with algorithmically generated chain-of-thought tokens can be easier to learn from than the raw text itself. This recent work has shown positive results for language identification in the presence of such computational traces, but the traces in these positive results come from explicit automata-theoretic machine models that generate the language, where the underlying vocabulary of tokens for the traces is very large. In this paper, we address two fundamental issues left open by this line of work: can we achieve positive results with traces that use only a small alphabet, and can we define traces directly from the language itself, without requiring an underlying machine model that generates it? We establish positive results for both of these questions: for an arbitrary collection of languages, we show how to define computational traces that enable identification in the limit, using an alphabet of tokens that is linear in the size of the alphabet that the languages are defined over, and independent of any other properties of the languages.

Authors: David Aleman Espinosa, Sharat Ibrahimpur, Chaitanya Swamy

In recent years, much attention has been devoted to the study of optimization problems under norm-based objectives coming from the rich class of monotone, symmetric norms (and their generalizations). This work has however almost exclusively focused on covering problems, wherein one seeks to minimize the norm of the cost vector induced by a solution. We introduce and study the class of {\em norm-budgeted packing problems}, which are packing problems where the resource constraints underlying the packing problem are modeled via a {\em norm budget constraint} involving a {\em monotone, symmetric norm}. Formally, we have some elements with associated rewards and sizes, a downwards-closed collection of feasible solutions, and a budget $B$. Each solution induces a size vector, and the goal is to maximize the total reward subject to the norm-budget constraint $f(\text{size vector})\leq B$. The versatility of monotone, symmetric norms implies that a variety of classical packing problems can be captured under the umbrella of norm-budgeted packing problems. Moreover, the closure properties of monotone, symmetric norms, also enable one to encode multiple different norm-budget constraints via a single monotone, symmetric norm. We consider the norm-budgeted versions of a variety of canonical packing problems, including knapsack, matching, maximum-weight independent set in a $k$-set system, maximum generalized assignment problem (MaxGAP), and $k$-facility location, and develop a framework that allows us to obtain {\em constant-factor approximation guarantees} for these problems, and {\em PTASes for knapsack, and MaxGAP on identical and related machines}. We also develop constant-factor approximation algorithms for the {\em submodular} versions of some norm-budgeted packing problems, wherein the reward function is now specified by a monotone, submodular function.

Authors: Haripriya Pulyassary, Chaitanya Swamy

In $k$-clustering problems, we are given a metric space $(\mathcal{C}, d)$, and must choose a set $S$ of $k$ centers to open. Each client $j \in \mathcal{C}$ incurs an assignment cost, which is the distance between $j$ and center in $S$ that it has been assigned to. In this work, we study the \emph{minimum-norm $k$-clustering problem}, where we are given an arbitrary monotone symmetric norm $f$, and wish to open $k$ centers so as to minimize $f$(assignment-cost vector). This is a powerful generalization, encompassing many classical $k$-clustering problems including the $k$-median, $k$-means, and $k$-center problems. A simple and efficient algorithmic idea is that of \emph{adaptive sampling}, wherein we randomly choose the location of the next center to open with probability proportional to its ``cost" under the currently chosen set. While this has yielded fast algorithms for some $k$-clustering problem, little is known for settings \emph{without} ``min-sum" objectives. We devise the first adaptive-sampling-based bicriteria constant-factor approximation algorithm for general minimum-norm $k$-clustering, vastly expanding the scope of problems handled by adaptive sampling. For the special case of $\text{Top}_\ell$ norms, which form a building block of monotone symmetric norms, we show that adaptive sampling yields an $O(\log k)$-approximation algorithm.

Authors: Justin Dallant

Recent work of Ameli, Nederlof and Wang and of Dallant and Kozma introduced a framework for improving classical space--time tradeoffs for the Traveling Salesman Problem (TSP) and related permutation problems via extremal set systems with many maximal chains. In this note we observe that, for so called permutation problems whose outer aggregation is a minimum (such as TSP), the same framework admits a simple quantum analogue: instead of iterating over the covering family of set systems, we apply quantum minimum finding over the family. More precisely, let $P_S$ denote the optimal inverse normalized chain density among set systems of normalized size at most $S$. Then TSP admits a bounded-error quantum algorithm using $\widetilde O(S^n)$ QRAM space and \[ \widetilde O\!\left((S\sqrt{P_S})^n\right) \] time. The same argument applies to other minimization problems over permutations with a similar structure to TSP. Combining this observation with improved extremal set-system constructions of Andoni, Dallant, Kozma and Yu gives an explicit quantum space--time tradeoff curve, which beats the known quantum tradeoff by Caroppo et al. for all $1

Authors: Nima Anari, Aniket Das, Alireza Haqi

We study the parallel complexity of sampling from the high-temperature Ising mixed $p$-spin Gibbs measure, a canonical instance of a mean-field spin glass on the hypercube $\{\pm 1\}^n$. We propose two different algorithms for this problem, corresponding to two different regimes of accuracy. Our first algorithm is a parallel implementation of a Markov chain known as block dynamics, combined with an approximate rejection sampling step that uses an Ising model in a novel way as a proposal distribution to approximate the quadratic interaction terms of the $p$-spin Hamiltonian. For any $\varepsilon > 0$, this algorithm runs in $n^{\tfrac{1}{3}}\operatorname{polylog}(\tfrac{n}{\varepsilon})$ parallel time with $\operatorname{poly}(n, \log(\tfrac{1}{\varepsilon}))$ work, and outputs a sample whose law is $\varepsilon$-close to the $p$-spin measure in total variation distance. Our second algorithm uses Picard iterations to parallelize the Algorithmic Stochastic Localization (ASL) process of El Alaoui, Montanari, and Sellke (2025), and for any $\varepsilon > \varepsilon_n$, takes $\operatorname{polylog}(\tfrac{n}{\varepsilon})$ parallel time and $\operatorname{poly}(\tfrac{n}{\varepsilon})$ work to produce a sample that is $\varepsilon$-close to the $p$-spin measure in the normalized 2-Wasserstein metric. Here, $\varepsilon_n > 0$ is a threshold that goes to $0$ as $n \to \infty$. Our result constitutes a doubly exponential improvement in the $\varepsilon$ dependence of the runtime and an exponential improvement in the $\varepsilon$ dependence of the total work when compared to naïve ASL, whose runtime scales as $\exp(\operatorname{poly}(\tfrac{1}{\varepsilon}))$.

Authors: Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S, Daniel Lokshtanov

An independent set in a graph $G$ is a set of pairwise non-adjacent vertices. A tree decomposition of $G$ is a pair $(T, χ)$ where $T$ is a tree and $χ: V(T) \rightarrow 2^{V(G)}$ is a function satisfying two axioms: for every edge $uv \in E(G)$ there is an $x \in V(T)$ such that $\{u,v\} \subseteq χ(x)$, and for every vertex $u \in V(G)$ the set $\{x \in V(T) | u \in χ(x)\}$ induces a non-empty and connected subtree of $T$. The sets $χ(x)$ for $x \in V(T)$ are called the bags of the tree decomposition. The tree-independence number of $G$ is the minimum taken over all tree decompositions of $G$ of the maximum size of an independent set of the graph induced by a bag of the decomposition. A graph $H$ is an induced minor of a graph $G$ if a graph isomorphic to $H$ can be obtained from $G$ by vertex deletions and edge contractions. We prove that for every $t\in\mathbb{N}$ there exists an $ε> 0$ such that every graph $G$ either contains the complete bipartite graph $K_{t,t}$ or the wall $W_{t\times t}$ as an induced minor, or has tree-independence at most $O(2^{O((\log n)^{1-ε})})$. This leads to algorithms with running time $2^{n^{o(1)}}$, for a wide range of problems on $\{K_{t,t}, W_{t\times t}\}$-induced minor free graphs. Our result is a substantial generalization of existing bounds for the tree-independence and tree-width on various graph classes, and a partial resolution of the conjecture of Chudnovsky, E S, and Lokshtanov [Arxiv, 2025] that $\{K_{t,t}, W_{t\times t}\}$-induced minor free graphs have poly-logarithmic tree independence number. The generality comes at the cost of a sub-polynomial, rather than poly-logarithmic upper bound. Our result leads to a complete classification of induced-minor closed classes into ones that have sub-polynomial tree-independence, tree-independence equal to $\tilde{O}(\sqrt{n})$, and linear tree-independence.

Front-running is a pervasive and costly problem on blockchains. Users earn rewards by publishing functional transactions that keeps markets efficient, such as arbitrage. But an attacker can observe such a transaction before it is ordered and publish her own ahead of it, seizing the reward and eroding users’ incentive to issue these transactions at all. The problem is well known and has drawn sustained effort from both industry and academia,...

By Hongyin Chen, Xu Zheng, Jichen Li, Ittay Eyal

Of the many cursed segments of vertical video, few annoy me more than the cottage industry of lunatics ranting over screenshots of PubMed pages to claim authority for whatever therapy, training program, or peptide they are selling. These people are all full of shit. They promise to cure your pain, get you thin, and make you stronger. All through SCIENCE.

These influencers will tell you that the scientific is better than the not scientific, and might even go so far as to say that the remainder is pseudoscience or quackery. But we unfortunately live in a narrow-minded world where scientific too often means “proven efficacious in a systematic review of randomized controlled trials.” You’ll be hard-pressed to find anything in the realm of treating musculoskeletal limitations that fits the bill.

It’s hard to shoehorn these sorts of therapies into the starting requirements for randomized trials. We’d need to start with clean definitions of an intervention and an outcome. What would these be for the management of pain by physical therapy?

Let’s start with the intervention. If we are being dogmatic evidence-based practitioners, the intervention in any physical therapy trial is the invitation to have therapy. According to the intention-to-treat principle, the invitation is the only thing that can be randomized. We can’t look only at the people who comply with every instruction and make it to the end of the rigorous therapy regimen. The model patients who diligently comply might differ from those who don’t, and our statistical signal will be biased if we include only the former. The only way to avoid these selection biases is to count everyone who was randomized, regardless of what happens between randomization and the final assessment. Both committed patients and no-shows contribute to the measured average efficacy.1

But what does it even mean for patients to follow the protocol? Physical therapy is far more complex than taking a drug. There’s no simple unit of treatment applied. Each interaction with a physical therapist involves a conversation about how things have been going, a plan for moving forward, some sort of interactive intervention in the office, and a discussion about what to do once the patient goes home. Each step here introduces a new branch in a deep decision tree. And every PT I’ve interacted with has been different, even when performing similar range-of-motion tests or manual therapies. Moreover, the treatment of any session depends on the entire history of the treatment so far. On top of this, every physical therapist I’ve seen has assigned daily exercises to do between sessions. This is part of the treatment, too! There is no way to perfectly isolate and randomize a single component of these complex treatment protocols.

A multi-stage protocol is an exponentially large collection of interventions. I made this point on the blog a few weeks ago in the context of anticoagulant trials for heart disease: “If you want to compare the effect of three different timings and three different dosages of a single drug, you need nine arms in your trial. If you want to additionally see if a second drug is helpful, you need 18.” Physical therapy is arguably much more complex.2

What about the outcome? In drug trials, we might get grim, unambiguous, objective outcomes like mortality. In vaccine trials, we might get unambiguous outcomes, such as a PCR diagnosis. Unfortunately, in pain management, the outcome is necessarily subjective. You can measure changes in range of pain-free motion, but there is too much heterogeneity to definitively stake out what a good outcome would be. Instead, pain therapies are most commonly evaluated based on improvements on the Numeric Ranking Scale. Studies ask participants at admission how their pain is on a scale of 0 (no pain) to 10 (worst pain imaginable). They ask them again at the follow-up. Statistical protocol then dictates computing the mean of the differences in treatment and control and running a t-test. You can try to remove the heterogeneity in how people respond to these questions, but these adjustments are based on subjective clinician calls. No matter what you do, pain is hard to mathematize. Doing statistics on these “numbers” and coming away with strong conclusions is a fool’s errand.

Beyond the treatment and outcome, all sorts of investigator biases make randomized trials even messier. You can blind the patients and the clinicians who assess outcomes, but you can’t blind the people applying physical therapy. It’s impossible to say what effect this sort of bias has on the scientific record. Even when well-intentioned, a clinician who believes in PT can subtly give away the secret assignment to their patients during a session.

I’ve never read a single study in this space that’s been compelling, and I don’t know why we hope that a narrow view of therapy can help us out of it. This fuels the fire of debate with people using studies to attack each other’s practices. There are countless articles and videos castigating stretching, massage, or cupping as not backed by evidence. These are all denounced as pseudoscience by a medical establishment that prescribed OxyContin like candy for two decades. Boy do I have some bad news for people who think there is great evidence that opioids work for pain management.

If we want to understand best practices for “wellness,” we need a different language around it. Maybe this language will need to lean on biomechanical plausibility or biochemical pathways. That certainly wouldn’t hurt. But more importantly, the language will have to prioritize discussions of craft, practice, and the cultivation of expertise. Whatever the case, the narrow definition of evidence-based needs to be reimagined. Healthcare is far more than a collection of unambiguous interventions with unambiguous outcomes.

Subscribe now

By Ben Recht

Authors: Luyining Gan, Jie Han, Bin Wang

A $4$-uniform $2$-cycle in a $4$-uniform hypergraph of length $t$ is a cyclic ordering of $2t$ vertices $v_1v_2\cdots v_{2t}v_1$ such that $v_{2i+1}v_{2i+2}v_{2i+3}v_{2i+4}$ are edges for $0\le i\le t-1$ while the addition is modulo $2t$. For every $γ>0$ and large $n$, we characterize the $n$-vertex $4$-uniform hypergraphs such that every triple of vertices is contained in at least $(1/3+γ)n$ edges and admits a Hamilton $2$-cycle. Up to the error term $γn$, the assumption on the minimum codegree is best possible and verifies a conjecture of Garbe and Mycroft. As a consequence, this gives a polynomial-time algorithm that decides whether an $n$-vertex $4$-uniform hypergraph with minimum codegree $(1/3+γ)n$ contains a Hamilton $2$-cycle. This stands as a steep contrast to the graph case where such a hardness gap has size $o(n)$.

Authors: Pingshi Yu, Chengsong Tan, Nicolas Wu, Alastair Donaldson

Randomised testing is a widely-used approach to software validation, yet its theoretical foundations remain thin. In particular, the fundamental question of what it means for a set of inputs to be \emph{generable} has gone unanswered in both the literature and folklore. We present the first complexity-theoretic foundations for random generators in software testing. We model generators as Turing transducers that consume random bits and produce string-encoded outputs, and show that the theoretically generable languages coincide exactly with the recursively enumerable languages. This has direct implications for testing at the boundaries of decidability, such as compiler testing. For \emph{efficient} generation, we show that the polynomial-time generable languages lie within \textit{NP}, that certain \textit{NP}-complete languages admit efficient generators, and that -- under standard cryptographic assumptions -- there are languages in \textit{P} for which no efficient generator exists: the complexity of efficienct generation and of efficient decision are not the same. We show space-bounded complexity is the natural framework for generators producing \emph{correlated} samples, capturing methodologies such as coverage-guided fuzzing and symbolic execution. Beyond classification, we characterise efficient generability: a language has a polynomial-time generator iff it admits a \emph{certificate scheme} over a verifier -- so witness planting, the folklore technique behind generators to test SAT solvers, is in a sense the only route to efficient generation. On the design of property-based testing libraries, we prove no library can compositionally derive efficient generators from logical predicates involving conjunction or negation, under standard assumptions. However, restricted classes like \textit{NL} (equivalently, linear Datalog predicates) would admit such a compilation.

Authors: Christoph Hertrich, Moritz Stargalla

We study tropical circuits with scalar multiplication gates, that is, algebraic circuits whose gates implement $\max$, $+$, or multiplication with a positive constant. For such circuits, we prove exponential size lower bounds for computing maximum weight directed spanning trees and maximum weight bipartite perfect matchings. As a corollary, we obtain an exponential size separation between monotone and non-monotone maxout neural networks, which generalize the popularly used ReLU neural networks. One conclusion from this is that neural network models with enforced convexity constraints, such as input-convex neural networks (ICNNs), sometimes need to be exponentially larger than their unrestricted counterparts in order to express the same functions.