Theory of Computing Report

This is Part 3 of a blogged essay “Steampunk Data Science.” A table of contents is here.

Shortly after Elmer McCollum was hired as a young faculty in agricultural chemistry at the University of Wisconsin, Edwin Hart recruited him to work on the single-grain experiment. Being a junior faculty member susceptible to the pressure from those more senior, McCollum reluctantly agreed to join the project. But McCollum knew from the get-go that the Single Grain Experiment was probably hopeless. How could they hope to isolate the differences between the grains if every experiment would require the half-decade needed to raise their herd of cows to maturity?

McCollum was trained as an organic chemist, and his limited experience in nutrition had been gleaned during his postdoctoral fellowship at Yale. As a go-getting young faculty member, he hit the books, purchasing all 37 volumes of the German “Yearbook on the Progress of Animal Chemistry.” There, he found numerous nutrition studies done in Germany on mice. McCollim had an epiphany. Clearly, the Wisconsin investigations into nutrition could be accelerated by switching from cows to smaller animals, thereby converting studies that were taking years to complete into ones that could be finished in a few months. But which animals would be most appropriate?

McCollum decided upon rats. Rats certainly grew much faster than cows. Rats were also much smaller. A researcher could keep dozens of cages in the same space required to house a cow. Also, for better or for worse, rats would eat almost anything you put in front of them. And few have sympathy for rodents being sacrificed for the sake of human knowledge.

For McCollum, it was settled: the Wisconsin Agricultural Experiment Station must immediately begin investigations on rats. He presented his plan to the Dean of the Agriculture School in 1907, shortly after the Single Grain Experiment had begun. McCollum’s lobbying met the same fate as Stephen Babcock’s earlier pleas for the single-grain experiment. The dean emphatically denied his request. He told McCollum he couldn’t imagine the trouble he’d be in had the citizens of Wisconsin discovered that he had allowed vermin to be grown at his field station on the government dime.

Undeterred, and with the encouragement of now emeritus faculty Babcock, McCollum decided to covertly run rat experiments anyway. He had grown up on a farm in Kansas, and his parents had paid him and his brother a bounty of a penny for each rat they could catch. So he put his farmboy skills to the test. Despite the dean’s denial, the Madison campus’ sprawling array of barns was already swimming with rats. McCollum trapped some of the locals and set up a clandestine animal laboratory. After several unfortunate encounters, McCollum determined that the wild rats were far too feral to keep in a lab.

McCollum needed nicer rats. He journeyed south to Chicago and bought a dozen tame white rats from a pet store. The pet rats proved far more manageable than the barn rats. From this initial dozen, McCollum bred a large rat colony with some combination of his research discretionary funds and his personal salary.

Now ready to experiment, McCollum returned to the European literature to find the best initial foray into nutrition science. Data visualization in nutrition was still in its infancy, but by the early 1900s, growth curves had become standard tools for understanding diet. An influential paper by Watson and Hunter analyzed various food diets for rats, feeding them restricted diets of either bread and milk, porridge and milk, rice, horse flesh, or ox flesh. In Figure 1, they plotted the average growth of the rats fed bread and milk and those fed porridge (oats cooked in boiled skim milk and water with a pinch of salt).

The thin line is the average weight in grams of the rats fed the bread and milk diet, while the thick line is the average weight in grams of the rats fed the porridge diet. The arrows denote the deaths of the rats. Watson and Hunter observed that the bread-and-milk diet resulted in uniformly healthy adolescent rats. In contrast, for whatever reason, young rats couldn’t live on only porridge, and all died in under 22 weeks.

Watson and Hunter never specify exactly what they mean by “bread.” Indeed, not every bread recipe is the same, and British bread likely differed from French or German bread in its grains, seeds, and other ingredients. From the experimental protocol in the paper, we can’t determine what exactly the bread contained that was lacking in the porridge. Whatever was in the bread and not in the oatmeal seemed essential for sustaining the growth of rats.

McCollum realized he needed a more fine-grained approach to isolating the nutrients necessary for rat growth. Using his skills as a chemist, he created “synthetic diets” that built food up from its basic building blocks. McCollum’s synthetic foods could be titrated to find the bare essentials required to sustain rats.

In his first paper on his rat colony, McCollum compared the nutritional value of some of his synthetic diets. He recorded the results in tables like these:

He fed some rats a diet based on some organic compounds and some inorganic phosphorus. He compared this synthetic diet to one with added hydrolyzed beef fat to make it tastier for the rats. McCollum’s assessment of the experiment was somewhat surprising: he concluded that palatability, that is, the tastiness of the diet, was the most essential factor in nutrition. In fact, he went as far as ruling out the possibility that poor growth could be attributed to the “lack of certain organic complexes in the food given, which the body was not able to supply through its synthetic power from the materials at hand.” This conclusion was astonishingly wrong.

I’ll tell you why in the next installment of this series, but let’s first try to understand how McCollum could have been so confused by his experiment. His data presentations certainly didn’t help. Though growth curves were commonplace by the time he had published this work, McCollum’s paper contained no plots. All the data are collected in unruly tables listing the weights of different rats under different diets. Even his experimental protocols were confusing. He decided to change the diet of Rat VII on day 53. McCollum describes that he made this dietary change for Rat VII because the animal ate more aggressively than the others, and wanted to find out whether the phosphorus was necessary for continued growth.

It’s possible that plotting the data may have revealed to McCollum the tenuousness of his conclusions. For example, in Figure 3, I plotted McCollum’s data (from Figure 2) in the style of Watson and Hunter, having each point denote the average weight of each rat in the lot.

In McCollum’s experiment, the control group was fed a combination of oats, corn, and wheat, like in the single-grain experiment. It is clear here that the two lots fed synthetic foods are doing much worse than rats fed normal food mixtures. Perhaps the differences between Lots 1 and 2 were due to unrelated traits of the individual rats in the study. With the data we have, it’s impossible to know.

Even though it wasn’t particularly convincing, McCollum still managed to find a journal to accept his first attempts at systematic experimental nutrition. Though we now know the results were not reproducible and the conclusions were way off, the publication got the ball rolling in American nutrition science. Within a few years, it would lead to a revolution in our understanding of food.

Subscribe now

Endnote: Though I heard many variants of McCollum’s legend when I was a professor at Wisconsin, I’ve based my account here mostly on McCollum’s autobiography, which paints the most favorable account of him. McCollum was a prickly guy, and his bucking the trend of the cow experiment did not make him many friends in Madison. Whereas Babcock and Harry Steenbock have buildings and streets and ice cream shops named after them, McCollum’s legacy is the Sprague-Dawley rat, developed at Wisconsin after McCollum had moved to Johns Hopkins, but still one of the most popular strains of laboratory rat in biology.

By Ben Recht

Authors: Dor Minzer

We discuss a recent line of research investigating inverse theorems with respect to general k-wise correlations, and explain how such correlations arise in different contexts in mathematics. We outline some of the results that were established and their applications in discrete mathematics and theoretical computer science. We also mention some open problems for future research.

Authors: Martin Durand

The Spearman footrule is a voting rule that takes as input voter preferences expressed as rankings. It outputs a ranking that minimizes the sum of the absolute differences between the position of each candidate in the ranking and in the voters' preferences. In this paper, we study the computational complexity of two extensions of the Spearman footrule when the number of voters is a small constant. The first extension, introduced by Pascual et al. (2018), arises from the collective scheduling problem and treats candidates, referred to as tasks in their model, as having associated lengths. The second extension, proposed by Kumar and Vassilvitskii (2010), assigns weights to candidates; these weights serve both as lengths, as in the collective scheduling model, and as coefficients in the objective function to be minimized. Although computing a ranking under the standard Spearman footrule is polynomial-time solvable, we demonstrate that the first extension is NP-hard with as few as 3 voters, and the second extension is NP-hard with as few as 4 voters. Both extensions are polynomial-time solvable for 2 voters.

Authors: Klara Mundilova, Oliver Gross

We study curves obtained by tracing triangle centers within special families of triangles, focusing on centers and families that yield (semi-)invariant triangle curves, meaning that varying the initial triangle changes the loci only by an affine transformation. We identify four two-parameter families of triangle centers that are semi-invariant and determine which are invariant, in the sense that the resulting curves for different initial triangles are related by a similarity transformation. We further observe that these centers, when combined with the aliquot triangle family, yield sheared Maclaurin trisectrices, whereas the nedian triangle family yields Limaçon trisectrices.

Authors: Tala Eagling-Vose, David C. Kutner, Felicia Lucke, Dániel Marx, Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen

Our main result is a full classification, for every connected graph $H$, of the computational complexity of Steiner Forest on $H$-subgraph-free graphs. To obtain this dichotomy, we establish the following new algorithmic, hardness, and combinatorial results: Algorithms: We identify two new classes of graph-theoretical structures that make it possible to solve Steiner Forest in polynomial time. Roughly speaking, our algorithms handle the following cases: (1) a set $X$ of vertices of bounded size that are pairwise connected by subgraphs of treewidth $2$ or bounded size, possibly together with an independent set of arbitrary size that is connected to $X$ in an arbitrary way; (2) a set $X$ of vertices of arbitrary size that are pairwise connected in a cyclic manner by subgraphs of treewidth $2$ or bounded size. Hardness results: We show that Steiner Forest remains NP-complete for graphs with 2-deletion set number $3$. (The $c$-deletion set number is the size of a smallest cutset $S$ such that every component of $G-S$ has at most $c$ vertices.) Combinatorial results: To establish the dichotomy, we perform a delicate graph-theoretic analysis showing that if $H$ is a path or a subdivided claw, then excluding $H$ as a subgraph either yields one of the two algorithmically favourable structures described above, or yields a graph class for which NP-completeness of Steiner Forest follows from either our new hardness result or a previously known one. Along the way to classifying the hardness for excluded subgraphs, we establish a dichotomy for graphs with $c$-deletion set number at most $k$. Specifically, our results together with pre-existing ones show that Steiner Forest is polynomial-time solvable if (1) $c=1$ and $k\geq 0$, or (2) $c=2$ and $k\leq 2$, or (3) $c\geq 3$ and $k=1$, and is NP-complete otherwise.

Authors: Arnaud Casteigts, Matteo De Francesco, Pierre Leone

In the racetrack acceleration model, proposed by Martin Gardner in 1973, each step consists of changing the position of the vehicle by a vector in $\mathbb{Z}^2$, with the constraints that two consecutive vectors differ by at most one unit in each dimension. We investigate three problems related to this model in arbitrary dimension in open space (no obstacles), where a configuration of the vehicle consists of its current position and the last-used vector. The three problems are the following. In Branching Cost (BC), given two configurations, the goal is to compute the minimum number of intermediate configurations (length of a trajectory) between the two configurations. Branching Trajectory (BT) has the same input and asks for a description of the corresponding trajectory. Multipoint Trajectory (MT) asks for an optimal trajectory that visits given points $p_1,\dots,p_n$ in a prescribed order, starting and ending with zero-speed configurations.\\ We revisit known approaches to solve BC in 2D, showing that this problem can be solved in constant time in any fixed number of dimensions $d$ (more generally, in $O(d \log d)$ time). We show that BT can also be solved in constant time for any fixed $d$, despite the fact that the length of the trajectory is not constant, by leveraging the fact that there always exists \emph{one} optimal trajectory compactly represented by $O(1)$ intermediate configurations. For MT, we collect theoretical and experimental evidence that the speed cannot be trivially bounded; local decisions may be impacted by points that are arbitrarily far in the visit order; and an optimal trajectory may require significant excursions out of the convex hull of the points. We still establish conservative speed bounds that a natural dynamic programming (DP) algorithm can exploit to solve reasonably large instances efficiently.

Authors: Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Sihan Liu

We study the basic task of mean estimation in the presence of mean-shift contamination. In the mean-shift contamination model, an adversary is allowed to replace a small constant fraction of the clean samples by samples drawn from arbitrarily shifted versions of the base distribution. Prior work characterized the sample complexity of this task for the special cases of the Gaussian and Laplace distributions. Specifically, it was shown that consistent estimation is possible in these cases, a property that is provably impossible in Huber's contamination model. An open question posed in earlier work was to determine the sample complexity of mean estimation in the mean-shift contamination model for general base distributions. In this work, we study and essentially resolve this open question. Specifically, we show that, under mild spectral conditions on the characteristic function of the (potentially multivariate) base distribution, there exists a sample-efficient algorithm that estimates the target mean to any desired accuracy. We complement our upper bound with a qualitatively matching sample complexity lower bound. Our techniques make critical use of Fourier analysis, and in particular introduce the notion of a Fourier witness as an essential ingredient of our upper and lower bounds.

Authors: Noam Goldberg, Danny Hermelin, Dvir Shabtay

We consider the robust permutation flowshop problem under the budgeted uncertainty model, where at most a given number of job processing times may deviate on each machine. We show that solutions for this problem can be determined by solving polynomially many instances of the corresponding nominal problem. As a direct consequence, our result implies that this robust flowshop problem can be solved in polynomial time for two machines, and can be approximated in polynomial time for any fixed number of machines. The reduction that is our main result follows from an analysis similar to Bertsimas and Sim (2003) except that dualization is applied to the terms of a min-max objective rather than to a linear objective function. Our result may be surprising considering that heuristic and exact integer programming based methods have been developed in the literature for solving the two-machine flowshop problem. We conclude by showing a logarithmic factor improvement in the overall running time implied by a naive reduction to nominal problems in the case of two machines and three machines.

Authors: John Jeang, Vladimir Podolskii

In the One-Fast-Many-Slow decision problem, introduced by Sheffield and Westover (ITCS '25), a scheduler, with access to one fast machine and infinitely many slow machines, receives a series of tasks and must allocate the work among its machines. The goal is to minimize the overhead of an online algorithm over the optimal offline algorithm. Three versions of this setting were considered: Instantly-committing schedulers that must assign tasks to machines immediately and irrevocably, Eventually-committing schedulers whose assignments are irrevocable but can occur anytime after a task arrives, and Never-committing schedulers that can interrupt and restart a task on a different machine. In the Instantly-committing model, Sheffield and Westover showed that the optimal competitive ratio is equal to 2, while in the Eventually-committing model the competitive ratio lies in the interval [1.618, 1.678], and in the Never-committing model the competitive ratio lies in the interval [1.366, 1.5] (SPAA '24, ITCS '25). In the latter two models, the exact optimal competitive ratios were left as open problems, moreover Kuszmaul and Westover (SPAA '24) conjectured that the lower bound in the Eventually-committing model is tight. In this paper we resolve this problem by providing tight bounds for the competitive ratios in the Eventually-committing and Never-committing models. For Eventually-committing, we prove Kuszmaul and Westover's conjecture by giving an algorithm achieving a competitive ratio equal to the lower bound of $\frac{1+\sqrt{5}}{2}\approx 1.618$. For Never-committing, we provide an explicit Task Arrival Process (TAP) lower bounding the competitive ratio to the previous upper bound of 1.5.

Authors: Tomer Adar

The $L_2$-norm, or collision norm, is a core entity in the analysis of distributions and probabilistic algorithms. Batu and Canonne (FOCS 2017) presented an extensive analysis of algorithmic aspects of the $L_2$-norm and its connection to uniformity testing. However, when it comes to estimating the $L_2$-norm itself, their algorithm is not always optimal compared to the instance-specific second-moment bounds, $O(1/(\varepsilon\|μ\|_2) + (\|μ\|_3^3 - \|μ\|_2^4) / (\varepsilon^2 \|μ\|_2^4))$, as stated by Batu (WoLA 2025, open problem session). In this paper, we present an unbiased $L_2$-estimation algorithm whose sample complexity matches the instance-specific second-moment analysis. Additionally, we show that $Ω(1/(\varepsilon \|μ\|_2))$ is indeed a per-instance lower bound for estimating the norm of a distribution $μ$ by sampling (even for non-unbiased estimators).

Authors: Alexander Lindermayr, Jens Schlöter

We study the problem of preemptively scheduling jobs online over time on a single machine to minimize the total flow time. In the traditional clairvoyant scheduling model, the scheduler learns about the processing time of a job at its arrival, and scheduling at any time the job with the shortest remaining processing time (SRPT) is optimal. In contrast, the practically relevant non-clairvoyant model assumes that the processing time of a job is unknown at its arrival, and is only revealed when it completes. Non-clairvoyant flow time minimization does not admit algorithms with a constant competitive ratio. Consequently, the problem has been studied under speed augmentation (JACM'00) or with predicted processing times (STOC'21, SODA'22) to attain constant guarantees. In this paper, we consider $α$-clairvoyant scheduling, where the scheduler learns the processing time of a job once it completes an $α$-fraction of its processing time. This naturally interpolates between clairvoyant scheduling ($α=0$) and non-clairvoyant scheduling ($α=1$). By elegantly fusing two traditional algorithms, we propose a scheduling rule with a competitive ratio of $\mathcal{O}(\frac{1}{1-α})$ whenever $0 \leq α< 1$. As $α$ increases, our competitive guarantee transitions nicely (up to constants) between the previously established bounds for clairvoyant and non-clairvoyant flow time minimization. We complement this positive result with a tight randomized lower bound.

Authors: Kaixin Wang, Kaiqiang Yu, Cheng Long

The maximal biclique enumeration problem in bipartite graphs is fundamental and has numerous applications in E-commerce and transaction networks. Most existing studies adopt a branch-and-bound framework, which recursively expands a partial biclique with a vertex until no further vertices can be added. Equipped with a basic pivot selection strategy, all state-of-the-art methods have a worst-case time complexity no better than $O(m\cdot (\sqrt{2})^n)$}, where $m$ and $n$ are the number of edges and vertices in the graph, respectively. In this paper, we introduce a new branch-and-bound (BB) algorithm \texttt{IPS}. In \texttt{IPS}, we relax the strict stopping criterion of existing methods by allowing termination when all maximal bicliques within the current branch can be outputted in the time proportional to the number of maximal bicliques inside, reducing the total number of branches required. Second, to fully unleash the power of the new termination condition, we propose an improved pivot selection strategy, which well aligns with the new termination condition to achieve better theoretical and practical performance. Formally, \texttt{IPS} improves the worst-case time complexity to $O(m\cdot α^n + n\cdot β)$, where $α(\approx 1.3954)$ is the largest positive root of $x^4-2x-1=0$ and $β$ represents the number of maximal bicliques in the graph, respectively. This result surpasses that of all existing algorithms given that $α$ is strictly smaller than $\sqrt{2}$ and $β$ is at most $(\sqrt{2})^n-2$ theoretically. Furthermore, we apply an inclusion-exclusion-based framework to boost the performance of \texttt{IPS}, improving the worst-case time complexity to $O(n\cdot γ^2\cdotα^γ+ γ\cdot β)$ for large sparse graphs ($γ$ is a parameter satisfying $γ\ll n$ for sparse graphs).

Authors: Eduar Castrillo Velilla

The Cai--Fürer--Immerman (CFI) construction provides the canonical family of hard instances for the Weisfeiler--Leman (WL) hierarchy: distinguishing the two non-isomorphic CFI graphs over a base graph $G$ requires $k$-WL where $k$ meets or exceeds the treewidth of $G$. In this paper, we introduce $Δ^\ell$-DRESS, which applies $\ell$ levels of iterated node deletion to the DRESS continuous structural refinement framework. $Δ^\ell$-DRESS runs Original-DRESS on all $\binom{n}{\ell}$ subgraphs obtained by removing $\ell$ nodes, and compares the resulting histograms. We show empirically on the canonical CFI benchmark family that Original-DRESS ($Δ^0$) already distinguishes $\text{CFI}(K_3)$ (requiring 2-WL), and that each additional deletion level extends the range by one WL level: $Δ^1$ reaches 3-WL, $Δ^2$ reaches 4-WL, and $Δ^3$ reaches 5-WL, distinguishing CFI pairs over $K_n$ for $n = 3, \ldots, 6$. Crucially, $Δ^3$ fails on $\text{CFI}(K_7)$ (requiring 6-WL), confirming a sharp boundary at $(\ell+2)$-WL. The computational cost is $\mathcal{O}\bigl(\binom{n}{\ell} \cdot I \cdot m \cdot d_{\max}\bigr)$ -- polynomial in $n$ for fixed $\ell$. These results establish $Δ^\ell$-DRESS as a practical framework for systematically climbing the WL hierarchy on the canonical CFI benchmark family.

Authors: Leslie Ann Goldberg, John Lapinskas

In this paper we prove Aldous's conjecture from 1987 that there is no backoff protocol that is stable for any positive arrival rate. The setting is a communication channel for coordinating requests for a shared resource. Each user who wants to access the resource makes a request by sending a message to the channel. The users don't have any way to communicate with each other, except by sending messages to the channel. The operation of the channel proceeds in discrete time steps. If exactly one message is sent to the channel during a time step then this message succeeds (and leaves the system). If multiple messages are sent during a time step then these messages collide. Each of the users that sent these messages therefore waits a random amount of time before re-sending. A backoff protocol is a randomised algorithm for determining how long to wait -- the waiting time is a function of how many collisions a message has had. Specifically, a backoff protocol is described by a send sequence $\overline{p} = (p_0,p_1,p_2,\ldots)$. If a message has had $k$ collisions before a time step then, with probability $p_k$, it sends during that time step, whereas with probability $1-p_k$ it is silent (waiting for later). The most famous backoff protocol is binary exponential backoff, where $p_k = 2^{-k}$. Under Kelly's model, in which the number of new messages that arrive in the system at each time step is given by a Poisson random variable with mean $λ$, Aldous proved that binary exponential backoff is unstable for any positive $λ$. He conjectured that the same is true for any backoff protocol. We prove this conjecture.

Authors: Michał Szyfelbein, Dariusz Dereniowski

This work considers a number of optimization problems and reductive relations between them. The two main problems we are interested in are the \emph{Optimal Decision Tree} and \emph{Set Cover}. We study these two fundamental tasks under precedence constraints, that is, if a test (or set) $X$ is a predecessor of $Y$, then in any feasible decision tree $X$ needs to be an ancestor of $Y$ (or respectively, if $Y$ is added to set cover, then so must be $X$). For the Optimal Decision Tree we consider two optimization criteria: worst case identification time (height of the tree) or the average identification time. Similarly, for the Set Cover we study two cost measures: the size of the cover or the average cover time. Our approach is to develop a number of algorithmic reductions, where an approximation algorithm for one problem provides an approximation for another via a black-box usage of a procedure for the former. En route we introduce other optimization problems either to complete the `reduction landscape' or because they hold the essence of combinatorial structure of our problems. The latter is brought by a problem of finding a maximum density precedence closed subfamily, where the density is defined as the ratio of the number of items the family covers to its size. By doing so we provide $\cO^*(\sqrt{m})$-approximation algorithms for all of the aforementioned problems. The picture is complemented by a number of hardness reductions that provide $o(m^{1/12-ε})$-inapproximability results for the decision tree and covering problems. Besides giving a complete set of results for general precedence constraints, we also provide polylogarithmic approximation guarantees for two most typically studied and applicable precedence types, outforests and inforests. By providing corresponding hardness results, we show these results to be tight.

The Cayley-Bacharach theorem and its applications

Cosmin Pohoata’s new and beautiful blog post presents several combinatorial applications of the Cayley–Bacharach theorem. Let me also mention his earlier post, in which he gave a new proof of Jamison’s direction tree theorem: every finite noncollinear point set in admits a admits a direction tree—that is, a spanning tree whose edges have pairwise distinct directions.

In January, after a long break, Cosmin wrote another post presenting an entropy-based proof of an interesting product–sum theorem over finite fields.

Some direction trees from Jamison’s original paper

By Gil Kalai

This is Part 2 of a blogged essay “Steampunk Data Science.” A table of contents is here.

Though nutrition science of his time suggested otherwise, Stephen Babcock knew you couldn’t feed cows coal. He would devote his life to finding the best diet for cattle and, in the process, precipitate the discovery of vitamins.

In 1888, Babcock moved to Madison to chair the Department of Agricultural Chemistry at the University of Wisconsin. Agriculture was big business in Wisconsin, and the university was founded as a land-grant institution tasked with emphasizing research and education in agriculture as part of its core academic mission. We all now know Wisconsin as the dairy state, but in the mid-1800s, Wisconsin’s primary export was wheat. However, after seasonal blights and competition from more southernly midwestern states like Iowa, Wisconsin farmers began to shift their emphasis. By the turn of the century, 90% of Wisconsin farms reared dairy cows. By 1915, Wisconsin produced more dairy than any other state in the country.1

This transition to dairy farming was the product of an ambitious public-private partnership between the state’s farmers, government, and university. The university had a mandate to improve the economic and social conditions of Wisconsin. As part of this mission, they established an agricultural research station on the western edge of campus. You can still visit barns and silos. Though it sounds unusual today, the top biologists and chemists in the 1800s devoted major research efforts to improving agriculture.

A particularly important question for farmers was how to feed their livestock. Cows, in particular, are large, hungry animals and are expensive to feed. With the inherently low margins of farming, farmers wanted to spend as little on them as possible. A central research theme in 1800s Agricultural Chemistry was finding the least expensive diet that produced healthy, large cows that gave delicious milk and bore healthy offspring.

When Babcock arrived in Wisconsin, modern nutrition theory was in its infancy. Protein had been discovered in 1838, and most nutritionists understood that it was essential to a healthy diet. As often happens after a revolutionary discovery, the conventional advice from scientific experts focused too strongly on their newly discovered nutrient. Wilbur Atwater had devised a method to determine the available protein and caloric energy in foods based on nitrogen content. From this, nutritional guidelines were proposed to maximize protein at the cheapest price possible.

You couldn’t buy big tubs of whey isolate in 1887, and the table above lists some potential alternatives for the protein-conscious. Each quantity of food could be purchased for 25 cents in 1887 dollars.2 If price and protein were the only concerns and intestinal distress could be dismissed, a person would eat nothing but beans.

Having grown up on a farm himself, Babcock knew this conventional wisdom was suspect. He would ridicule Atwater and his colleagues, asking why we didn’t just feed cows dung or soft coal, as both cleared the bar for available energy and nitrogen content.

Farmers’ intuitions about feed suggested value in variety when it came to feeding cows. Babcock figured they must do this for a reason. Although these grains had similar macronutrients, no single grain would be sufficient for healthy animals. What would happen if cows were only fed single grains? If cows were only fed wheat, or only corn, or only barley, balanced so the protein and mineral content were the same, would this still yield thriving cattle?

Babcock pressured his dean to allow him to run an experiment. He proposed purchasing some young calves, raising them on single feeds, and comparing their development. The university had ample resources to tend and manage the cows, and Babcock would oversee the scientific reporting.

The dean balked. Such an interdisciplinary project would be nothing but a headache. He’d have to marshal support from the Animal Husbandry department, and they were demanding resources for their pet-breeding projects. Cows were expensive! Couldn’t Babcock pursue research on food chemistry without raising his own animals?

Though disappointed, Babcock found he could succeed in the lab without animals. In the next few years, he devised simple tests that would revolutionize dairy farming. His most famous discovery was a simple procedure to test the fat content of milk. This test could be done by civilians and allowed people to determine whether impurities had been added to the milk to dilute it or if someone had skimmed cream off the top. Moreover, farmers could use Babcock’s test to select cows that produced higher fat milk for breeding. In addition to his innovations, Babcock was an engaging, committed teacher and held forums with farmers to discuss best practices and current challenges. By 1900, Babcock had become a Wisconsin celebrity. He was a fixture in both the academic and farming circles across the state.3

Despite his extraordinary academic success and impact, Babcock never gave up on his single-grain experiment. He finally got his way in 1907 upon his retirement. Babcock was succeeded by Edwin Hart, who loved Babcock’s research proposal. Hart marshaled the resources for the experiment.

The university purchased 16 cows that were divided into four groups. Each of the groups of cows was fed a special diet. The first group was only fed corn, the second group only wheat, the third group only oats, and the fourth group an equal combination of the three grains. They then waited to see what would happen.

Subscribe now

By Ben Recht

Last week I had the pleasure of meeting Alex Bellos in Oxford. Among other things Bellos writes the Guardian Monday puzzle column. He gave me a copy of his latest book, Puzzle Me Twice, where the obvious answer is not correct. I got more right than wrong, but I hated being wrong. Here is one of those puzzles, Sistery Mystery (page 28), which is a variation of a puzzle from Rob Eastaway. 

Puzzle 1: Suppose the probability of a girl is 51% independently and uniformly over all children. In expectation, who has more sisters, a boy or a girl?

Go ahead and try to solve this before reading further.

In any family with both boys and girls, each boy will have one more sister than each girl. For example in a family with four girls, each boy has four sisters and each girl only has three. Thus boys have more sisters on average.

Wrong, it's exactly the same. To see this consider Alex, the sixth child of a ten-child family. The number of Alex's sisters is independent of Alex's gender. This is a pretty robust result, it doesn't depend on the probability of a child being a girl, or if we allow non-binary children, or if the distributions aren't identical, say the probability of a girl is higher for later kids in a family. All you need is independence.

So what's wrong with my initial intuition that in every family boys have more sisters than girls. Eastaway suggests this gets balanced by the families of a single gender, but this happens rarely for large families. Instead it's a variation of Simpson's paradox. The naive argument doesn't account for the fact that girls are overrepresented in girl-heavy families. Consider a family of two boys and eight girls. Each of the two boys has eight sisters but four times as many girls have seven sisters, which adds to the expected value more to the girls than the boys.

If you lose independence the solution may not hold, for example if we have identical twins. 

I'll leave you with one more puzzle.

Puzzle 2: Suppose you are in a country where each family has children until they get their first boy. In this country, do boys or girls have more sisters on average?

Answer below.

In Puzzle 2 we lose independence and if Alex is a girl, she's more likely to be in a family with many girls. Indeed if boys and girls have equal probability, when you work out the infinite sums in expectation a boy will have one sister and a girl will have two.

By Lance Fortnow

Authors: Amir Shpilka, Yann Tal

We study deterministic polynomial identity testing (PIT) and reconstruction algorithms for depth-$4$ arithmetic circuits of the form \[ Σ^{[r]}\!\wedge^{[d]}\!Σ^{[s]}\!Π^{[δ]}. \] This model generalizes Waring decompositions and diagonal circuits, and captures sums of powers of low-degree sparse polynomials. Specifically, each circuit computes a sum of $r$ terms, where each term is a $d$-th power of an $s$-sparse polynomial of degree $δ$. This model also includes algebraic representations that arise in tensor decomposition and moment-based learning tasks such as mixture models and subspace learning. We give deterministic worst-case algorithms for PIT and reconstruction in this model. Our PIT construction applies when $d>r^2$ and yields explicit hitting sets of size $O(r^4 s^4 n^2 d δ^3)$. The reconstruction algorithm runs in time $\textrm{poly}(n,s,d)$ under the condition $d=Ω(r^4δ)$, and in particular it tolerates polynomially large top fan-in $r$ and bottom degree $δ$. Both results hold over fields of characteristic zero and over fields of sufficiently large characteristic. These algorithms provide the first polynomial-time deterministic solutions for depth-$4$ powering circuits with unbounded top fan-in. In particular, the reconstruction result improves upon previous work which required non-degeneracy or average-case assumptions. The PIT construction relies on the ABC theorem for function fields (Mason-Stothers theorem), which ensures linear independence of high-degree powers of sparse polynomials after a suitable projection. The reconstruction algorithm combines this with Wronskian-based differential operators, structural properties of their kernels, and a robust version of the Klivans-Spielman hitting set.

Authors: Philip Z. Maymin

I prove that competitive market outcomes require computational intractability. If P = NP, firms can efficiently solve the collusion detection problem, identifying deviations from cooperative agreements in complex, noisy markets and thereby making collusion sustainable as an equilibrium. If P != NP, the collusion detection problem is computationally infeasible for markets satisfying a natural instance-hardness condition on their demand structure, rendering punishment threats non-credible and collusion unstable. Combined with Maymin (2011), who proved that market efficiency requires P = NP, this yields a fundamental impossibility: markets can be informationally efficient or competitive, but not both. Artificial intelligence, by expanding firms' computational capabilities, is pushing markets from the competitive regime toward the collusive regime, explaining the empirical emergence of algorithmic collusion without explicit coordination.

Authors: Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu

Locally Decodable Codes (LDCs) are error-correcting codes $C\colonΣ^n\rightarrow Σ^m,$ encoding \emph{messages} in $Σ^n$ to \emph{codewords} in $Σ^m$, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting. We prove an exponential lower bound on the length of Hamming RLDCs making $2$ queries (even adaptively) over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a ``phase-transition''-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits.

Authors: Mikael Vejdemo-Johansson

Sol LeWitt famously enumerated all the incomplete open cubes, finding 122 of these connected, non-planar subsets of the edges of the cube. Since then, while several projects have revisited the cube enumeration, no such enumeration has been published for any other interesting solid. In this paper we present work on enumerating all the incomplete open platonic solids, finding 6 tetrahedra, 122 cubes (just like LeWitt), 185 octahedra, 2\,423\,206 dodecahedra and 16\,096\,166 icosahedra.

Authors: Petr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, Ninad Rajgopal

We develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only $\mathcal{O}(\log(n))$ workspace, and use sublinear catalytic space matching the best-known space bounds of non-catalytic algorithms running in polynomial time. First, we design a polynomial time algorithm for directed $s$-$t$ connectivity using $n \big/ 2^{Θ(\sqrt{\log n})}$ catalytic space, which matches the state-of-the-art time-space bounds in the non-catalytic setting [Barnes et al., 1998], and improves the catalytic space usage of the best known algorithm [Cook and Pyne, 2026]. Furthermore, using only $\mathcal{O}(\log(n))$ random bits we get a randomized algorithm whose running time nearly matches the fastest time bounds known for space-unrestricted algorithms. Second, we design polynomial time algorithms for the problems of computing Edit Distance, Longest Common Subsequence, and the Discrete Fréchet Distance, again using $n \big/ 2^{Θ(\sqrt{\log n})}$ catalytic space. This again matches non-catalytic time-space frontier for Edit Distance and Least Common Subsequence [Kiyomi et al., 2021].

Authors: Roman Edenhofer

We prove a space-space trade-off for directed $st$-connectivity in the catalytic space model. For any integer $k \leq n$, we give an algorithm that decides directed $st$-connectivity using $O(\log n \cdot \log k+\log n)$ regular workspace and $O\left(\frac{n}{k} \cdot \log^2 n\right)$ bits of catalytic memory. This interpolates between the classical $O(\log^2 n)$-space bound from Savitch's algorithm and a catalytic endpoint with $O(\log n)$ workspace and $O(n\cdot \log^2 n)$ catalytic memory. As a warm-up, we present a catalytic variant of Savitch's algorithm achieving the endpoint above. Up to logarithmic factors, this matches the smallest catalyst size currently known for catalytic logspace algorithms, due to Cook and Pyne (ITCS 2026). Our techniques also extend to counting the number of walks from $s$ to $t$ of a given length $\ell\leq n$.

Authors: Ilias Diakonikolas, Daniel M. Kane

We study the complexity of smoothed agnostic learning, recently introduced by~\cite{CKKMS24}, in which the learner competes with the best classifier in a target class under slight Gaussian perturbations of the inputs. Specifically, we focus on the prototypical task of agnostically learning halfspaces under subgaussian distributions in the smoothed model. The best known upper bound for this problem relies on $L_1$-polynomial regression and has complexity $d^{\tilde{O}(1/σ^2) \log(1/ε)}$, where $σ$ is the smoothing parameter and $ε$ is the excess error. Our main result is a Statistical Query (SQ) lower bound providing formal evidence that this upper bound is close to best possible. In more detail, we show that (even for Gaussian marginals) any SQ algorithm for smoothed agnostic learning of halfspaces requires complexity $d^{Ω(1/σ^{2}+\log(1/ε))}$. This is the first non-trivial lower bound on the complexity of this task and nearly matches the known upper bound. Roughly speaking, we show that applying $L_1$-polynomial regression to a smoothed version of the function is essentially best possible. Our techniques involve finding a moment-matching hard distribution by way of linear programming duality. This dual program corresponds exactly to finding a low-degree approximating polynomial to the smoothed version of the target function (which turns out to be the same condition required for the $L_1$-polynomial regression to work). Our explicit SQ lower bound then comes from proving lower bounds on this approximation degree for the class of halfspaces.

Authors: Kimon Fountoulakis, David Martínez-Rubio

We study the degree-weighted work required to compute $\ell_1$-regularized PageRank using the standard one-gradient-per-iteration accelerated proximal-gradient method (FISTA). For non-accelerated local methods, the best known worst-case work scales as $\widetilde{O} ((αρ)^{-1})$, where $α$ is the teleportation parameter and $ρ$ is the $\ell_1$-regularization parameter. A natural question is whether FISTA can improve the dependence on $α$ from $1/α$ to $1/\sqrtα$ while preserving the $1/ρ$ locality scaling. The challenge is that acceleration can break locality by transiently activating nodes that are zero at optimality, thereby increasing the cost of gradient evaluations. We analyze FISTA on a slightly over-regularized objective and show that, under a checkable confinement condition, all spurious activations remain inside a boundary set $\mathcal{B}$. This yields a bound consisting of an accelerated $(ρ\sqrtα)^{-1}\log(α/\varepsilon)$ term plus a boundary overhead $\sqrt{vol(\mathcal{B})}/(ρα^{3/2})$. We provide graph-structural conditions that imply such confinement. Experiments on synthetic and real graphs show the resulting speedup and slowdown regimes under the degree-weighted work model.

Authors: Qiming Cui, Michael Dinitz

We revisit the central online problem of ski rental in the "algorithms with predictions" framework from the point of view of distributional predictions. Ski rental was one of the first problems to be studied with predictions, where a natural prediction is simply the number of ski days. But it is both more natural and potentially more powerful to think of a prediction as a distribution p-hat over the ski days. If the true number of ski days is drawn from some true (but unknown) distribution p, then we show as our main result that there is an algorithm with expected cost at most OPT + O(min(max({eta}, 1) * sqrt(b), b log b)), where OPT is the expected cost of the optimal policy for the true distribution p, b is the cost of buying, and {eta} is the Earth Mover's (Wasserstein-1) distance between p and p-hat. Note that when {eta} < o(sqrt(b)) this gives additive loss less than b (the trivial bound), and when {eta} is arbitrarily large (corresponding to an extremely inaccurate prediction) we still do not pay more than O(b log b) additive loss. An implication of these bounds is that our algorithm has consistency O(sqrt(b)) (additive loss when the prediction error is 0) and robustness O(b log b) (additive loss when the prediction error is arbitrarily large). Moreover, we do not need to assume that we know (or have any bound on) the prediction error {eta}, in contrast with previous work in robust optimization which assumes that we know this error. We complement this upper bound with a variety of lower bounds showing that it is essentially tight: not only can the consistency/robustness tradeoff not be improved, but our particular loss function cannot be meaningfully improved.

Authors: Robin A. Heinonen

The exact leading asymptotics of solutions to the symmetric linear search problem are obtained for any positive probability density on the real line with a monotonic, sufficiently regular tail. A similar result holds for densities on a compact interval.

Authors: Vinicius Tikara Venturi Date, Leandro Miranda Zatesko

The string repetitiveness measures $χ$ (the size of a smallest suffixient set of a string) and $r$ (the number of runs in the Burrows--Wheeler Transform) are related. Recently, we have shown that the bound $χ\leq 2r$, proved by Navarro et al., is asymptotically tight as the size $σ$ of the alphabet increases, but achieving near-tight ratios for fixed $σ> 2$ remained open. We introduce a \emph{2-branching property}: a cyclic string is 2-branching at order~$k$ if every $(k{-}1)$-length substring admits exactly two $k$-length extensions. We show that 2-branching strings of order~$k$ yield closed-form ratios $χ/r = (2σ^{k-1}+1)/(σ^{k-1}+4)$. For order~$3$, we give an explicit construction for every $σ\geq 2$, narrowing the gap to~$2$ from $O(1/σ)$ to $O(1/σ^2)$. For $σ\in \{3,4\}$, we additionally present order-$5$ instances with ratios exceeding~$1.91$.

Authors: Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou

We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While robust algorithms exist for insertion-only streams with only a polylogarithmic overhead in memory over non-robust algorithms, it was widely conjectured that turnstile streams of length polynomial in the universe size $n$ require space linear in $n$. We refute this conjecture, showing that robustness can be achieved using space which is significantly sublinear in $n$. Our framework combines multiple linear sketches in a novel estimator-corrector-learner framework, yielding the first insertion-deletion algorithms that approximate: (1) the second moment $F_2$ up to a $(1+\varepsilon)$-factor in polylogarithmic space, (2) any symmetric function $\cal{F}$ with an $\mathcal{O}(1)$-approximate triangle inequality up to a $2^{\mathcal{O}(C)}$ factor in $\tilde{\mathcal{O}}(n^{1/C}) \cdot S(n)$ bits of space, where $S$ is the space required to approximate $\cal{F}$ non-robustly; this includes a broad class of functions such as the $L_1$-norm, the support size $F_0$, and non-normed losses such as the $M$-estimators, and (3) $L_2$ heavy hitters. For the $F_2$ moment, our algorithm is optimal up to $\textrm{poly}((\log n)/\varepsilon)$ factors. Given the recent results of Gribelyuk et al. (STOC, 2025), this shows an exponential separation between linear sketches and non-linear sketches for achieving adversarial robustness in turnstile streams.

Authors: Eduar Castrillo Velilla

The Weisfeiler-Lehman (WL) hierarchy is a cornerstone framework for graph isomorphism testing and structural analysis. However, scaling beyond 1-WL to 3-WL and higher requires tensor-based operations that scale as O(n^3) or O(n^4), making them computationally prohibitive for large graphs. In this paper, we start from the Original-DRESS equation (Castrillo, Leon, and Gomez, 2018)--a parameter-free, continuous dynamical system on edges--and show that it distinguishes the prism graph from K_{3,3}, a pair that 1-WL provably cannot separate. We then generalize it to Motif-DRESS, which replaces triangle neighborhoods with arbitrary structural motifs and converges to a unique fixed point under three sufficient conditions, and further to Generalized-DRESS, an abstract template parameterized by the choice of neighborhood operator, aggregation function and norm. Finally, we introduce Delta-DRESS, which runs DRESS on each node-deleted subgraph G\{v}, connecting the framework to the Kelly-Ulam reconstruction conjecture. Both Motif-DRESS and Delta-DRESS empirically distinguish Strongly Regular Graphs (SRGs)--such as the Rook and Shrikhande graphs--that confound 3-WL. Our results establish the DRESS family as a highly scalable framework that empirically surpasses both 1-WL and 3-WL on well-known benchmark graphs, without the prohibitive O(n^4) computational cost.

Authors: Keigo Oka

The Unix command \texttt{find} is among the first commands taught to beginners, yet remains indispensable for experienced engineers. In this paper, we demonstrate that \texttt{find} possesses unexpected computational power, establishing three Turing completeness results using the GNU implementation (a standard in Linux distributions). (1) \texttt{find} + \texttt{mkdir} (a system that has only \texttt{find} and \texttt{mkdir}) is Turing complete: by encoding computational states as directory paths and using regex back-references to copy substrings, we simulate 2-tag systems. (2) GNU \texttt{find} 4.9.0+ alone is Turing complete: by reading and writing to files during traversal, we simulate a two-counter machine without \texttt{mkdir}. (3) \texttt{find} + \texttt{mkdir} without regex back-references is still Turing complete: by a trick of encoding regex patterns directly into directory names, we achieve the same power. These results place \texttt{find} among the ``surprisingly Turing-complete'' systems, highlighting the hidden complexity within seemingly simple standard utilities.

Authors: Julien Dallot, Yuval Emek, Yuval Gil, Maciej Pacut, Stefan Schmid

This paper introduces a new model for ML-augmented online decision making, called online algorithms with unreliable guidance (OAG). This model completely separates between the predictive and algorithmic components, thus offering a single well-defined analysis framework that relies solely on the considered problem. Formulated through the lens of request-answer games, an OAG algorithm receives, with each incoming request, a piece of guidance which is taken from the problem's answer space; ideally, this guidance is the optimal answer for the current request, however with probability $β$, the guidance is adversarially corrupted. The goal is to develop OAG algorithms that admit good competitiveness when $β= 0$ (a.k.a. consistency) as well as when $β= 1$ (a.k.a. robustness); the appealing notion of smoothness, that in most prior work required a dedicated loss function, now arises naturally as $β$ shifts from $0$ to $1$. We then describe a systematic method, called the drop or trust blindly (DTB) compiler, which transforms any online algorithm into a learning-augmented online algorithm in the OAG model. Given a prediction-oblivious online algorithm, its learning-augmented counterpart produced by applying the DTB compiler either follows the incoming guidance blindly or ignores it altogether and proceeds as the initial algorithm would have; the choice between these two alternatives is based on the outcome of a (biased) coin toss. As our main technical contribution, we prove (rigorously) that although remarkably simple, the class of algorithms produced via the DTB compiler includes algorithms with attractive consistency-robustness guarantees for three classic online problems: for caching and uniform metrical task systems our algorithms are optimal, whereas for bipartite matching (with adversarial arrival order), our algorithm outperforms the state-of-the-art.

Authors: Ria Stevens, Fangshuo Liao, Barbara Su, Jianqiang Li, Anastasios Kyrillidis

We approach the Max-3-Cut problem through the lens of maximizing complex-valued quadratic forms and demonstrate that low-rank structure in the objective matrix can be exploited, leading to alternative algorithms to classical semidefinite programming (SDP) relaxations and heuristic techniques. We propose an algorithm for maximizing these quadratic forms over a domain of size $K$ that enumerates and evaluates a set of $O\left(n^{2r-1}\right)$ candidate solutions, where $n$ is the dimension of the matrix and $r$ represents the rank of an approximation of the objective. We prove that this candidate set is guaranteed to include the exact maximizer when $K=3$ (corresponding to Max-3-Cut) and the objective is low-rank, and provide approximation guarantees when the objective is a perturbation of a low-rank matrix. This construction results in a family of novel, inherently parallelizable and theoretically-motivated algorithms for Max-3-Cut. Extensive experimental results demonstrate that our approach achieves performance comparable to existing algorithms across a wide range of graphs, while being highly scalable.

This is Part 1 of a blogged essay “Steampunk Data Science.” A table of contents is here.

In a back-and-forth with Ryan Briggs about the “crisis” of hiding null results in political science, Stephen Wild asked a loaded question.

“How different is the current situation from the past, whether it be 50 years ago or 150 years ago? Phrased in another, slightly more provocative way, what if it’s always been this way?”

In response, Ryan suggested that quantitative social science is very young and is getting better, and can be fixed. I’m not sure. Quantitative social science is only young by relative standards. You could argue the modern discipline starts after the French Revolution with academic bureaucrats like Adolphe Quetelet in the 1800s. Udny Yule was using linear regression to suss out the causation of poverty in 1900. John Maynard Keynes wrote about probabilistic methods for understanding society in the 1920s. The first application of machine learning techniques to the prediction of prison recidivism was in 1928.

While quantitative social science isn’t new, you could argue that we’ve reached a new crisis. Perhaps because of publish-or-perish incentives, science has reached new lows, where nothing is reproducible, and most published results are wrong. Researchers, journalists, and politicians alike complain that contemporary science faces a terrible reproduction crisis. People love writing meta-analyses like the one I wrote about last week. Psychology has been in crisis for a decade. Cancer research is in crisis. Machine learning is in crisis.

Conventional wisdom suggests that the reproduction crisis threatens the fundamental legitimacy of the sciences. Operatives in the United States federal government have been using this “crisis” as an excuse to slash science funding and attack universities. All of this panic begs Stephen’s question of when science used to be better. It implicitly suggests that there was a golden age when all published results were true, and scientists diligently reproduced each other’s work.

Is this true? Was reproduction a core element of prior scientific or engineering revolutions?

It’s not hard to find people decrying the demise of science throughout history. I wrote about when Science Magazine dedicated an entire editorial section to worrying about the public’s turn against science in 1957. The fifties were supposedly the wonder years. You want to go back even further? Read Charles Babbage complaining about the state of affairs in 1830.

Now, you might argue, like Ryan does, that better methods ameliorated these crises. That somehow doing science better fixed the fields. The null hypothesis significance test, the metascientist’s best friend, is barely one hundred years old. Is it true that the science of the 1800s was doomed and hopeless because they couldn’t run randomized controlled trials and compute p-values?

In the midst of the covid lockdowns, I also found myself intrigued by this question and started digging into how science was done before the formalization of statistics. How did we figure out which interventions worked before the null hypothesis test? I ended up dumping this research into a long essay about one of the most important discoveries in human-facings sciences of the early 20th century: vitamins.

Some discoveries have simple, pithy origins, like finding mold in a petri dish. But discovering the body’s need for vitamins took decades, as physicians, biologists, and chemists assembled evidence from an array of confusing empirical findings from many distant parts of the world. There were dozens of erroneous hypotheses put forward as truths in the literature. There were sloppy data practices and poorly documented experimental protocols. But through this confusion, clarity eventually coalesced into a completely new understanding of diet and disease.

I wrote this up about four years ago, but I’ve never figured out how to publish it. Initially, I thought it would be a core part of my book on automated decision making, The Irrational Decision (preorder now! It helps the substack), but the vitamin story ended up being too much of a prequel. The discovery of vitamins happened two world wars before the development of the computer. It happened a decade before the formalization of statistics. That it’s one of the last major discoveries of the pre-data scientific age is why I find the story so fascinating.

Since The Irrational Decision comes out in two weeks, it feels appropriate to put out the prequel now. My plan is to interleave two threads: I’ll continue my liveblogging of class, and I’ll tell the story of the history of vitamins as a quintessential case study of the human-facing sciences before the mathematical formalization of statistical inference.

The discovery of vitamins and deficiency diseases shows how a chaotic lack of reproducibility might be core to science itself, and that we were quite capable of making sense of the natural world before we had access to spreadsheets and statistics software. I’ll try to convince you that none of our fancy modern machinery would have helped at all. Both then and now, there are no formal paths to discovery.

Subscribe now

By Ben Recht

We study deterministic polynomial identity testing (PIT) and reconstruction algorithms for depth-$4$ arithmetic circuits of the form \[ \Sigma^{[r]}\!\wedge^{[d]}\!\Sigma^{[s]}\!\Pi^{[\delta]}. \] This model generalizes Waring decompositions and diagonal circuits, and captures sums of powers of low-degree sparse polynomials. Specifically, each circuit computes a sum of $r$ terms, where each term is a $d$-th power of an $s$-sparse polynomial of degree $\delta$. This model also includes algebraic representations that arise in tensor decomposition and moment-based learning tasks such as mixture models and subspace learning. We give deterministic worst-case algorithms for PIT and reconstruction in this model. Our PIT construction applies when $d>r^2$ and yields explicit hitting sets of size $O(r^4 s^4 n^2 d \delta^3)$. The reconstruction algorithm runs in time $\textrm{poly}(n,s,d)$ under the condition $d=\Omega(r^4\delta)$, and in particular it tolerates polynomially large top fan-in $r$ and bottom degree $\delta$. Both results hold over fields of characteristic zero and over fields of sufficiently large characteristic. These algorithms provide the first polynomial-time deterministic solutions for depth-$4$ powering circuits with unbounded top fan-in. In particular, the reconstruction result improves upon previous work which required non-degeneracy or average-case assumptions. The PIT construction relies on the ABC theorem for function fields (Mason-Stothers theorem), which ensures linear independence of high-degree powers of sparse polynomials after a suitable projection. The reconstruction algorithm combines this with Wronskian-based differential operators, structural properties of their kernels, and a robust version of the Klivans-Spielman hitting set.

Authors: Ondřej Ježil, Dimitrios Tsintsilidas

Student-Teacher Games are a model of computation in which a computationally restricted Student attempts to produce a string satisfying a refutable property, while an all-powerful Teacher refutes incorrect candidates by providing counterexamples. By the classical result of Krajíček, Pudlák, and Takeuti [KPT90], such games capture the witnessing of $\forall\exists\forall$-formulas in bounded arithmetic. In this paper, we introduce subclasses of total search problems in the polynomial hierarchy, classified by the number of rounds and candidate answers per round required for a Student at the corresponding level to solve them. Assuming the polynomial hierarchy does not collapse, we separate these classes for different number of rounds and queries. As applications we obtain the following results: (a) We study theories of bounded arithmetic axiomatized by fine-grained variants of length induction and bounded collection. We prove a general witnessing theorem connecting their $\forall\exists\forall$-consequences to the appropriate classes of Student-Teacher Games. Under the non-collapse of the polynomial hierarchy, we separate these theories. (b) These conditional separations resolve two open problems in bounded arithmetic: one by Buss and Ressayre [Bus85, CK93] on the strength of bounded collection, and one by Pollett [Pol97] on the difference between strict and non-strict double length induction. (c) Finally, we extend the unprovability of circuit upper bounds due to Krajíček and Oliveira [KO17] to the theory $PV_1+BB(Σ^b_1)$, and the unprovability of strong co-nondeterministic circuit lower bounds due to Pich and Santhanam [PS21] to the theory $PV_1+LLIND(sΣ^b_1)$. By the preceding separations, both theories strictly extend $PV_1$ assuming $NP\nsubseteq P/poly$.

Authors: A. R. Balasubramanian, Vitor Greati, Revantha Ramanayake

For substructural logics with contraction or weakening admitting cut-free sequent calculi, proof search was analyzed using well-quasi-orders on $\mathbb{N}^d$ (Dickson's lemma), yielding Ackermannian upper bounds via controlled bad-sequence arguments. For hypersequent calculi, that argument lifted the ordering to the powerset, since a hypersequent is a (multi)set of sequents. This induces a jump from Ackermannian to hyper-Ackermannian complexity in the fast-growing hierarchy, suggesting that cut-free hypersequent calculi for extensions of the commutative Full Lambek calculus with contraction or weakening ($\mathbf{FL_{ec}}$/$\mathbf{FL_{ew}}$) inherently entail hyper-Ackermannian upper bounds. We show that this intuition does not hold: every extension of $\mathbf{FL_{ec}}$ and $\mathbf{FL_{ew}}$ admitting a cut-free hypersequent calculus has an Ackermannian upper bound on provability. To avoid the powerset, we exploit novel dependencies between individual sequents within any hypersequent in backward proof search. The weakening case, in particular, introduces a Karp-Miller style acceleration, and it improves the upper bound for the fundamental fuzzy logic $\mathbf{MTL}$. Our Ackermannian upper bound is optimal for the contraction case (realized by the logic $\mathbf{FL_{ec}}$).

Authors: Wei Feng, Haiyong Zheng

We propose a template-driven triangulation framework that embeds raster- or segmentation-derived boundaries into a regular triangular grid for stable PDE discretization on image-derived domains. Unlike constrained Delaunay triangulation (CDT), which may trigger global connectivity updates, our method retriangulates only triangles intersected by the boundary, preserves the base mesh, and supports synchronization-free parallel execution. To ensure determinism and scalability, we classify all local boundary-intersection configurations up to discrete equivalence and triangle symmetries, yielding a finite symbolic lookup table that maps each case to a conflict-free retriangulation template. We prove that the resulting mesh is closed, has bounded angles, and is compatible with cotangent-based discretizations and standard finite element methods. Experiments on elliptic and parabolic PDEs, signal interpolation, and structural metrics show fewer sliver elements, more regular triangles, and improved geometric fidelity near complex boundaries. The framework is well suited for real-time geometric analysis and physically based simulation over image-derived domains.

Authors: Chris Gartland, Mikhail Ostrovskii, Yuval Rabani, Robert Young

We prove that the distortion of any embedding into $L_1$ of the transportation cost space or earth mover distance over a $d$-dimensional grid $\{1,\dots m\}^d$ is $Ω(\log N)$, where $N$ is the number of vertices and the implicit constant is universal (in particular, independent of dimension). This lower bound matches the universal upper bound $O(\log N)$ holding for any $N$-point metric space. Our proof relies on a new Sobolev inequality for real-valued functions on the grid, based on random measures supported on dyadic cubes.

Authors: Aditya Acharya, Auguste Henry Gezalyan, David M. Mount, Danesh Sivakumar

The forward and reverse Funk weak metrics are fundamental distance functions on convex bodies that serve as the building blocks for the Hilbert and Thompson metrics. In this paper we study Voronoi diagrams under the forward and reverse Funk metrics in polygonal and elliptical cones. We establish several key geometric properties: (1) bisectors consist of a set of rays emanating from the apex of the cone, and (2) Voronoi diagrams in the $d$-dimensional forward (or reverse) Funk metrics are equivalent to additively-weighted Voronoi diagrams in the $(d-1)$-dimensional forward (or reverse) Funk metrics on bounded cross sections of the cone. Leveraging this, we provide an $O\big(n^{\ceil{\frac{d-1}{2}}+1}\big)$ time algorithm for creating these diagrams in $d$-dimensional elliptical cones using a transformation to and from Apollonius diagrams, and an $O(mn\log(n))$ time algorithm for 3-dimensional polygonal cones with $m$ facets via a reduction to abstract Voronoi diagrams. We also provide a complete characterization of when three sites have a circumcenter in 3-dimensional cones. This is one of the first algorithmic studies of the Funk metrics.

Authors: Haitao Wang

Chan [JACM, 2010] gave a data structure for maintaining the convex hull of a dynamic set of 3D points under insertions and deletions, supporting extreme-point queries. Subsequent refinements by Kaplan, Mulzer, Roditty, Seiferth, and Sharir [DCG, 2020] and Chan [DCG, 2020] preserved the framework while improving bounds. The current best result achieves $O(\log^2 n)$ amortized insertion time, $O(\log^4 n)$ amortized deletion time, and $O(\log^2 n)$ worst-case query time. These techniques also yield dynamic 2D Euclidean nearest neighbor searching via duality, where the problem becomes maintaining the lower envelope of 3D planes for vertical ray-shooting queries. Using randomized vertical shallow cuttings, Kaplan et al. [DCG, 2020] and Liu [SICOMP, 2022] extended the framework to dynamic lower envelopes of general 3D surfaces, obtaining the same asymptotic bounds and enabling nearest neighbor searching under general distance functions. We revisit Chan's framework and present a modified structure that reduces the deletion time to $O(\log^3 n \log\log n)$, while retaining $O(\log^2 n)$ amortized insertion time, at the cost of increasing the query time to $O(\log^3 n / \log\log n)$. When the overall complexity is dominated by deletions, this yields an improvement of roughly a logarithmic factor over previous results.

Authors: László Kozma, Michal Opler

Matrix multiplication is a fundamental task in almost all computational fields, including machine learning and optimization, computer graphics, signal processing, and graph algorithms (static and dynamic). Twin-width is a natural complexity measure of matrices (and more general structures) that has recently emerged as a unifying concept with important algorithmic applications. While the twin-width of a matrix is invariant to re-ordering rows and columns, most of its algorithmic applications to date assume that the input is given in a certain canonical ordering that yields a bounded twin-width contraction sequence. In general, efficiently finding such a sequence -- even for an approximate twin-width value -- remains a central and elusive open question. In this paper we show that a binary $n \times n$ matrix of twin-width $d$ can be preprocessed in $\widetilde{\mathcal{O}}_d(n^2)$ time, so that its product with any vector can be computed in $\widetilde{\mathcal{O}}_d(n)$ time. Notably, the twin-width of the input matrix need not be known and no particular ordering of its rows and columns is assumed. If a canonical ordering is available, i.e., if the input matrix is $d$-twin-ordered, then the runtime of preprocessing and matrix-vector products can be further reduced to $\mathcal{O}(n^2+dn)$ and $\mathcal{O}(dn)$. Consequently, we can multiply two $n \times n$ matrices in $\widetilde{\mathcal{O}}(n^2)$ time, when at least one of the matrices consists of 0/1 entries and has bounded twin-width. The results also extend to the case of bounded twin-width matrices with adversarial corruption. Our algorithms are significantly faster and simpler than earlier methods that involved first-order model checking and required both input matrices to be $d$-twin-ordered.

Authors: Gabriel Bathie, Paul Huber, Guillaume Lagarde, Akka Zemmari

We study the sensitivity of the Lempel-Ziv 77 compression algorithm to edits, showing how modifying a string $w$ can deteriorate or improve its compression. Our first result is a tight upper bound for $k$ edits: $\forall w' \in B(w,k)$, we have $C_{\mathrm{LZ77}}(w') \leq 3 \cdot C_{\mathrm{LZ77}}(w) + 4k$. This result contrasts with Lempel-Ziv 78, where a single edit can significantly deteriorate compressibility, a phenomenon known as a *one-bit catastrophe*. We further refine this bound, focusing on the coefficient $3$ in front of $C_{\mathrm{LZ77}}(w)$, and establish a surprising trichotomy based on the compressibility of $w$. More precisely we prove the following bounds: - if $C_{\mathrm{LZ77}}(w) \lesssim k^{3/2}\sqrt{n}$, the compression may increase by up to a factor of $\approx 3$, - if $k^{3/2}\sqrt{n} \lesssim C_{\mathrm{LZ77}}(w) \lesssim k^{1/3}n^{2/3}$, this factor is at most $\approx 2$, - if $C_{\mathrm{LZ77}}(w) \gtrsim k^{1/3}n^{2/3}$, the factor is at most $\approx 1$. Finally, we present an $\varepsilon$-approximation algorithm to pre-edit a word $w$ with a budget of $k$ modifications to improve its compression. In favorable scenarios, this approach yields a total compressed size reduction by up to a factor of~$3$, accounting for both the LZ77 compression of the modified word and the cost of storing the edits, $C_{\mathrm{LZ77}}(w') + k \log |w|$.

Authors: Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, Clement Svendsen

In this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a close to $(\log|H|)^{3/2}$ dependence on the size of the hypothesis class $H$. Our proof uses several novel techniques and works by defining a particular Cayley graph associated with $H$ and analyzing a suitable random walk on this graph by examining the spectral properties of its adjacency matrix. Furthermore, we show an almost matching upper bound for the lower bound instance, meaning if a stronger lower bound exists, one would have to consider a different instance of the problem.

Authors: Keigo Oka, Naoki Inaba, Akira Iino

You find a stain on the wall and decide to cover it with non-overlapping stickers of a single identical shape (rotation and reflection are allowed). Is it possible to find a sticker shape that fails to cover the stain? In this paper, we consider this problem under polyomino constraints and complete the classification of always-coverable stain shapes (polyominoes). We provide proofs for the maximal always-coverable polyominoes and construct concrete counterexamples for the minimal not always-coverable ones, demonstrating that such cases exist even among hole-free polyominoes. This classification consequently yields an algorithm to determine the always-coverability of any given stain. We also show that the problem of determining whether a given sticker can cover a given stain is $\NP$-complete, even though exact cover is not demanded. This result extends to the 1D case where the connectivity requirement is removed. As an illustration of the problem complexity, for a specific hexomino (6-cell) stain, the smallest sticker found in our search that avoids covering it has, although not proven minimum, a bounding box of $325 \times 325$.

Authors: Bhaskar DasGupta, Katie Kruzan

In recent years extensions of manifold Ricci curvature to discrete combinatorial objects such as graphs and hypergraphs (popularly called as "network shapes"), have found a plethora of applications in a wide spectrum of research areas ranging over metabolic systems, transcriptional regulatory networks, protein-protein-interaction networks, social networks and brain networks to deep learning models and quantum computing but, in contrast, they have been looked at by relatively fewer researchers in the algorithms and computational complexity community. As an attempt to bring these network Ricci-curvature related problems under the lens of computational complexity and foster further inter-disciplinary interactions, we provide a formal framework for studying algorithmic and computational complexity issues for detecting critical edges in an undirected graph using Ollivier-Ricci curvatures and provide several algorithmic and inapproximability results for problems in this framework. Our results show some interesting connections between the exact perfect matching and perfect matching blocker problems for bipartite graphs and our problems.

Authors: Avinandan Das

This paper investigates the semi-streaming complexity of \textit{$k$-partial coloring}, a generalization of proper graph coloring. For $k \geq 1$, a $k$-partial coloring requires that each vertex $v$ in an $n$-node graph is assigned a color such that at least $\min\{k, °(v)\}$ of its neighbors are assigned colors different from its own. This framework naturally extends classical coloring problems: specifically, $k$-partial $(k+1)$-coloring and $k$-partial $k$-coloring generalize $(Δ+1)$-proper coloring and $Δ$-proper coloring, respectively. Prior works of Assadi, Chen, and Khanna [SODA~2019] and Assadi, Kumar, and Mittal [TheoretiCS~2023] show that both $(Δ+1)$-proper coloring and $Δ$-proper coloring admit one-pass randomized semi-streaming algorithms. We explore whether these efficiency gains extend to their partial coloring generalizations and reveal a sharp computational threshold : while $k$-partial $(k+1)$-coloring admits a one-pass randomized semi-streaming algorithm, the $k$-partial $k$-coloring remains semi-streaming intractable, effectively demonstrating a ``dichotomy of one color'' in the streaming model.

Authors: Jakub Ruszil, Artur Polański, Adam Roman, Jakub Zelek

The article studies edge coverage for control flow graphs extended with explicit constraints. Achieving a given level of white-box coverage for a given code is a classic problem in software testing. We focus on designing test sets that achieve edge coverage \textit{while respecting additional constraints} between vertices. The paper analyzes how such constraints affect both the feasibility and computational complexity of edge coverage. The paper discusses five types of constraints. POSITIVE constraints require at least one test path where a given vertex precedes another. NEGATIVE constraints forbid any such test path. ONCE constraints require exactly one test path with a single occurrence of one vertex before another. MAX ONCE constraints allow such precedence in at most one test path. ALWAYS constraints require every test path containing a given vertex to also contain another vertex later on the same path. Each type models a different test requirement, such as mandatory flows, semantic exclusions, or execution cost limits. We investigate the computational complexity of finding a test set that achieves edge coverage and respects a given set of constraints. For POSITIVE constraints, the existence of an edge covering test set is decidable in polynomial time by extending standard edge coverage constructions with additional paths for each constraint. For NEGATIVE, MAX ONCE, ONCE, and ALWAYS constraints, the decision problem is NP-complete. The proofs rely on polynomial reductions from variants of SAT. The NP-completeness results hold even for restricted graph classes, including acyclic graphs, for all these four constraints. Finally, we study the fixed-parameter tractability of the NEGATIVE constraint. Although the general problem is NP-complete, the paper presents an FPT algorithm with respect to the number of constraints.

Authors: Paul Paschmanns, Vera Traub

The Steiner Tree problem asks for the cheapest way of connecting a given subset of the vertices in an undirected graph. One of the most prominent linear programming relaxations for Steiner Tree is the Bidirected Cut Relaxation (BCR). Determining the integrality gap of this relaxation is a long-standing open question. For several decades, the best known upper bound was 2, which is achievable by standard techniques. Only very recently, Byrka, Grandoni, and Traub [FOCS 2024] showed that the integrality gap of BCR is strictly below 2. We prove that the integrality gap of BCR is at most 1.898, improving significantly on the previous bound of 1.9988. For the important special case where a terminal minimum spanning tree is an optimal Steiner tree, we show that the integrality gap is at most 12/7, by providing a tight analysis of the dual-growth procedure by Byrka et al. To obtain the general bound of 1.898 on the integrality gap, we generalize their dual growth procedure to a broad class of moat-growing algorithms. Moreover, we prove that no such moat-growing algorithm yields dual solutions certifying an integrality gap below 12/7. Finally, we observe an interesting connection to the Hypergraphic Relaxation.