This is a live blog of Lecture 4 of my graduate seminar “Feedback, Learning, and Adaptation.” A table of contents is here. The dramatic conclusion of Steampunk Data Science will appear later this week.

Though ostensibly chasing similar questions, the fields of artificial intelligence and control theory couldn’t be more temperamentally different. In AI, much like the rest of computer science, there’s a mindset to “just do stuff” and patch bugs as they come. There’s a spirit of tinkering and benchmaxxing, and the expectation that systems will get more robust as they get more capable. I mean, the AI Safety people seem to think that the way to get safe AI is to spend billions of dollars building a superintelligent AI. They say this out loud to anyone willing to listen.

Control theory, by contrast, wants you to learn non-self-adjoint operator theory before you think about building anything. If you’re designing an airplane or any other system where failure can lead to catastrophe, safety has to come first. And the path to safety is always more math.

Finding a nice middle ground between these two mindsets has been much harder than I’d like. And yet, the two fields connect at optimal control. The foundation of reinforcement learning (and its successor, recursive self-improvement) is optimal control. Modern control theory emerged in the Cold War planning of the 50s, where aerospace engineers developed optimal control to plot rocket trajectories. In class today, we’ll look at both perspectives and find why they not only can’t meet in the middle, but both leave us with rather unsatisfactory views of the role of optimization in sequential decision-making.

In its most grandiose formulation, one often adopted by rationalist AI maximalists, optimal control claims a universal model for making decisions in the face of uncertainty. You just need the right cost function and proper Bayesian updating.

This view falls apart once you move beyond the toy problems people nerd out about in online rationalist forums. Most problems have more stages than the Monty Hall problem. And once you have a modestly long horizon, exact solutions of optimal control problems are beyond impossible. We all quickly learn that with any reasonable complexity, you have to move from dynamic programming to approximate dynamic programming, meaning you are never sure if you are actually solving your original problem. Moreover, as soon as you have to incorporate measurement uncertainty and those clever Bayesian updates, the associated optimization problems are at best PSPACE-complete or at worst undecidable. You could try to argue to me that your POMDP problem isn’t PSPACE-complete, and enough iterations of GFYPO will find the answer. But this means that your superintelligent optimizer isn’t actually solving optimization problems. What it’s actually doing is anyone’s guess.

Perhaps we can retreat to the more modest view promoted in contemporary control classes. Optimal control is a nice scaffolding for engineering design. You get a framework to locally make sense of a huge parameter space. If you’re trying to tune multiple PID loops at once, you’d probably rather link things together with a Q and an R than a few dozen controller gains without a clear relation between them. But it’s a local framework (a small world framework, if you will), not a global system.

And the optimization framework often gives you some robustness. In the LQR problem, we know that if we find a control policy, it is stabilizing. We know that LQR gives us a way to bound the amount of errors we’ll accumulate if unmodeled noise perturbs the system. And we know that near-optimal solutions are often pretty good. Some early exciting work showed that LQR was robust to misspecification of the system model.

The gain margins, sadly, turned out to be a bit of a mathematical illusion. As soon as you incorporate the Bayesian reasoning that rationally summarizes the uncertainty in measurement, the policy becomes exceptionally fragile to model misspecification. This is Doyle’s famous “There Are None” example, and we’ll work through the details today.

You can incorporate robustness directly into the formulation, but this comes at its own computational and conceptual costs. Robust control is not easy and is seldom taught. My colleagues can correct me, but I’m not sure we ever teach it at Berkeley. Why is a topic for a future blog post.

So from both the maximalist RL perspective and the minimalist control perspective, we’re stuck…with LQR. Any other optimal control problem of reasonable complexity is intractable and inherently fragile to model mismatch and measurement uncertainty. This feels like a funny place to lay the foundation of an engineering philosophy!

So why would we build an entire system around optimization? I suppose I understand the promising allure of just writing down cost functions and having robots come out. But even people who don’t work on optimization know that there are always tradeoffs in designing systems and making decisions.1 If the goal is literally just “minimize cost,” we get cheap, fragile garbage out. We have to account for all the things we might care about, and write these explicitly into the cost, the constraints, or the solution heuristics.

Ultimately, real robustness gets added in with engineering expertise rather than mathematical rigor. There’s no getting around the years of hard work in simulation and pilot programs before you can convince everyone your system is actually ready for prime time. Optimal control gives you a false sense of interpretability and rigor, and it’s important to be periodically reminded of its illusoriness.

Subscribe now

By Ben Recht

I give an alternative proof of the xor lemma which may provide a simple explanation of why xor-ing decreases correlation.

Goodhart's law: When a measure becomes a target, it stops being a measure.  

I was watching the show Masterminds where Ken Jennings is one of the Masterminds. Here is what happened: 

Brook Burns (the host): The only vice president in the 20th century with initials H.H. was Hubert Humphrey. Who was the only vice president in the 19th century with initials H.H?

Bill Gasarch shouting at the screen: Hannibal Hamlin, Lincoln's VP for his first term! This is really obscure so this may be a rare case where I get a question right that Ken Jennings does not know!

Ken Jennings: Hannibal Hamlin. 

Bill Gasarch: Darn! However, I suspect he studied lists of presidents and vice presidents for the purpose of doing well on Jeopardy and now other shows. My knowledge is more natural in that I read books on presidents and vice presidents (best book, maybe the only book,  on Vice Presidents: Bland Ambition).  My knowledge of it is different from his. I tend to think my knowledge is more legitimate, though it would be hard to make that statement rigorous. If on quiz shows they asked follow-up questions, that might help alleviate this problem, if it is indeed a problem.

Misc: 

Ken Jennings is a Mormon so he does not drink or know about drinks. However, before going on Jeopardy he studied drinks for the show.

Ken Jennings does know novelty songs and that is legit since novelty songs comes up rarely on Jeopardy so I doubt he studied them in his preparation for going on Jeopardy. 

a) He knew that Shel Silverstein wrote A boy named Sue which was sung by Johnny Cash

b) He knew that Johnny Cash did a cover of Shel Silverstein's I'm being swallowed by a boa constrictor.

c) During his streak there was a category on novelty songs. He got 4 out of the 5 correct, and the one he got wrong I could tell he really knew. I got them all right, and faster, but Ken Jennings gets my respect for his legit knowledge of novelty songs. See here for the questions and answers. 

Goodharts law (maybe): Jeopardy is supposed to be about what people know. Is it supposed to be about what people study? Does studying for it help you  for things other than quiz shows?

When I watch a quiz show and get a question right there are levels of legitimacy:

1) I know the area naturally. 

2) I saw the question and answer on a different show and and I then looked it up and know more about it. So this is now legit.

3) I saw the question and answer on a different show and just know it as stimulus-response with very little understanding. Example: Kelly Clarkson was the first winner on American Idol, but I have never seen the show and only vaguely know how it works.

4) I saw the question and answer on the show I am watching, the exact episode, and I am watching a repeat. Sometimes I know stuff I don't normally know and then say OH, I've seen this episode before. 

Back to my point:

Is Ken Jennings memorizing lists a less-legit form of knowledge? If so, how to make that statement rigorous?

Is this what AI does? See also Chinese Room since that's also about a device that gets the right answers but perhaps for the ''wrong'' reason. 

By gasarch

Authors: Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

Authors: Pavel Hubáček

Authors: Zihan Hao, Zikuan Huang, Qipeng Liu

Authors: Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, Morgan Shirley, Adi Shraibman

Authors: Nate Veldt, Thomas Stanley, Benjamin W. Priest, Trevor Steil, Keita Iwabuchi, T. S. Jayram, Grace J. Li, Geoffrey Sanders

Authors: Zohar Barak, Inbbal Talgam-Cohen

Authors: Jifan Shi, Jianyang Gao, James Xia, Tamás Béla Fehér, Cheng Long

Authors: Karolina Drabik, Maël Dumas, Colin Geniet, Jakub Nowakowski, Michał Pilipczuk, Szymon Toruńczyk

Authors: Erik van den Akker, Klaus-Tycho Foerster

Authors: Qian Li, Henan Liu, Heng Liu, Yuyi Wang

Authors: Majid Khabbazian

Authors: Sayan Bhattacharya, Ermiya Farokhnejad, Haoze Wang

US-based academics are being required by the government and by their universities to make all online content accessible by April 24, and I think many of us have been running around trying to figure out what that means and how to do it. My university has been especially unhelpful, demanding compliance in vague terms but not telling us what standard they’re using and pointing only to Microsoft and Google’s web sites for guidance on how to improve accessibility for Microsoft and Google products. The relevant standard appears from the government links to be WCAG 2.1 AA. For those of us who have been using the LaTeX beamer package to create mathematical course lecture notes as pdf files, beamer cannot do this. The accessibility standards require tagged pdf and beamer does not have code to generate the tags correctly. But there is a solution: a replacement package, ltx-talk, that is mostly compatible with beamer. After some effort, I have succeeded in using ltx-talk to create slide decks that closely resemble my old beamer decks both in appearance and coding and that pass all automated accessibility checks in Acrobat. That makes now a good time to record what I have learned about going from beamer to accessible ltx-talk, before I forget it all again.

Online guides

I have found three helpful guides to accessible LaTeX (not specifically about ltx-talk): “Using LaTeX to produce accessible PDF” from the LaTeX tagging project, “A quick primer on modifying existing LaTeX for digital accessibility” by Richard Wong at Rice University, and “Creating accessible PDFs in LaTeX” from Overleaf. If you are using some unusual LaTeX packages or document classes, the LaTeX tagging project also maintains a useful list of the tagging status of LaTeX packages and classes. This includes the information that beamer cannot generate accessible tagged pdf but ltx-talk can. These links got me from a state of having no idea how to generate accessible pdf files from my slides to a state where I thought it might be possible, and helped me start setting up my files. Most of the rest was from carefully reading log files and accessibility reports and then experimenting to figure out what to change in order to make the errors and warnings go away.

This posting is not intended as a substitute for these guides, but rather as a collection of tips and tricks for converting beamer slide decks into accessible ltx-talk slide decks.

Compilation

To compile ltx-talk files and produce accessible tagged pdf files, you need to run lualatex instead of pdflatex. Sometimes you need as many as four runs: one run of lualatex to get an aux file with bibliography items, a run of bibtex, and then three more runs of lualatex before it stabilizes and stops telling you to run again because the labels have changed or because it miscalculated page numbers and added a dummy page. Check the log files for these things.

You also need to be running a very recent version of LaTeX, dated November 2025 or more recent. TeX Live 2025, released in March 2025, will not work. The new TeX Live 2026 pretest will. I use MacOS and have not figured out whether there is any way to access the TeX Live pretest on a Mac. Instead I have been using either Overleaf (through its Overleaf Labs feature) or a linux install on some departmental machines accessible to me via ssh. This already includes the ltx-talk package; you do not need to install it separately.

There are apparently incompatibilities between recent releases of LaTeX and the cleveref package. Fortunately, my slide decks do not use cleveref.

Preamble

The magic incantation at the start of your file is different, of course, because it’s a different package but also because tagged pdf needs a metadata command before the document class to set it up. The old incantation (for, say, a \(16\times 9\) target aspect ratio) was:

\documentclass[aspectratio=169]{beamer}

Instead, now it is:

\DocumentMetadata{
  lang          = en,
  pdfstandard   = {ua-2,a-4f},
  tagging       = on,
  tagging-setup = {math/setup=mathml-SE} 
}
\documentclass[aspect-ratio=16:9]{ltx-talk}

Change the lang = en line if you are writing in a different language than English. Wong suggests instead tagging-setup={math/setup=mathml-SE,math/alt/use}; I have no idea whether that would be an improvement.

The other important change in the LaTeX preamble works around what I think is a bug in ltx-talk. By default, it tags frame titles with an h4-level header tag. But there are no h1, h2, or h3-level header tags that it produces. This causes Acrobat’s accessibility checker to complain about header nesting. Maybe the right thing to do is to add some h1, h2, and h3-level tags, for instance on the title page, but I haven’t figured out how to do that. Instead, I changed the frame titles to h1, with

\tagpdfsetup{
  role / new-tag = frametitle / H1
}

The default appearance produced by ltx-talk is close to beamer with the structure skin, but not quite the same. You can change it in your LaTeX preamble but the documentation for how to change it is somewhat lacking. What worked for me is to look for code like DeclareTemplateInterface in ltx-talk.cls and to use \EditInstance to change it. For instance I use the code

\definecolor{ksblue}{RGB}{0,129,205}
\EditInstance{header}{std}{
  color            = ksblue,
  left-hspace      = 0cm plus 1fil,
  right-hspace     = 0cm plus 1fil
}

to change the color of frame titles and center them. I also use

\renewcommand{\labelitemi}{ {\footnotesize\color{ksblue}$\blacktriangleright$}}
\renewcommand{\labelitemii}{ {\scriptsize\color{ksblue}$\blacktriangleright$}}

to make big triangular itemize bullets like beamer, instead of the default little circular ones. (So far I have only converted slides with two levels of itemize nesting.)

Figures

In the article content, the easiest change to explain but the most time-consuming one, for me, is adding alt-text to all images. The syntax is straightforward: \includegraphics[alt={Alt text goes here}]{filename}. I have seen big online debates on what alt-text should describe and how detailed it should be. The important thing to remember is that you’re not trying to describe the image in vivid-enough detail that an AI image generator could make a copy of it. The purpose of these things is to substitute for the image when people use a screenreader to convert your slides into spoken text. So it should be concise enough that it doesn’t interrupt the flow of the text when spoken but informative enough that people using a screenreader don’t miss out on the meaning. For complicated mathematical examples that can be a big ask.

I had one figure, created as a pdf file by Adobe Illustrator, that triggered a flate decode error in lualatex. The same image had worked correctly in pdflatex and beamer. The compilation continued with a warning but the figure did not render correctly in the compiled file. I could not figure out why. The only workaround I could find was to save it as a different pdf version in Illustrator.

Environments

Getting ltx-talk to run required a few changes elsewhere in my LaTeX files. I was using \begin{frame}{Title of frame}, and ltx-talk has an option to make that work, but by default it doesn’t. Instead you need to use \begin{frame}\frametitle{Title of frame}. Using unicode characters such as an en-dash in a frametitle leads to a “unreferenced destination” error; code them in ASCII (in this case a double hyphen) instead.

Columns need to be delimited by \begin{column}{size}…\end{column} instead of starting them by \column. (Also the spacing between columns is different between beamer and ltx-talk so you may need some reformatting to get them to look good.) And the same thing about using an environment rather than a command applies to some formatting things like \flushright: it won’t cause a LaTeX error but it will cause the tagging to get mismatched with a warning message at the end of the log. Then you have to work through your file trying to figure out which slide caused the mismatch.

If you use verbatim environments, beamer needed to mark this by \begin{frame}[fragile]. This still works in ltx-talk but with a different syntax, \begin{frame*}. If you use tabular environments, you need to tell LaTeX which rows of your table are header rows. See the accessibility guides linked above.

Formulas

There is lua code somewhere that generates mathml tags for the mathematical formulas (I think this is the main reason that you need to use lualatex). It is not as robust as LaTeX itself. Using code like \bigl and \bigr will cause a tagging mismatch; use \left and \right instead and let LaTeX choose for itself how big to make the parentheses. Using \dots inside math often does not work at all, and in one case using $\dots$ inside a tabular environment caused lualatex to crash hard. Use \ldots or \cdots instead. Also, I think using mathematics inside \text inside more mathematics caused a tagging mismatch; don’t nest them like that. This code will also generate files with names of the form *-luamml-mathml.html; add that pattern to your .gitignore file.

I had one deck (discussing the Ackermann function) containing the expression \(\approx 2\times 10^{19728}\). This caused lualatex to freeze. The only hypothesis I can find is that it looks like a formula whose numerical value can be calculated and that the mathml conversion code was trying to calculate it, using a slow exponentiation algorithm.

Sections

If your deck has 21 or more slides, Acrobat will complain if it doesn’t also have bookmarks for navigation within sections of the deck. I did this using \pdfbookmark[1]{Bookmark name}{Bookmark name} at the start of each section. Maybe there is a better way. This would be a good place to put more higher-level header tags than the H4 frame titles, if I knew how.

Many of my slide decks have bibtex bibliography sections. I don’t generally show these when speaking but I want them to be part of the pdf files of my slide decks that I distribute. I like to use natbib for this (plus the doi package to make the external links and dois work properly). But natbib never worked correctly in beamer; I needed to add the code \newcommand{\newblock}{} to the preamble to make it work. In ltx-talk, I also needed to add \newcommand{\thebibliography}{\relax} before loading natbib. Then you can just put your bibliography within one of the frames. A problem I have not found a good workaround for is that beamer allows multi-frame bibliographies with \begin{frame}[allowframebreaks]. However, ltx-talk does not and reading its documentation reveals that its developer is very hostile to long bibliographies (such as would arise in a talk incorporating a literature review). The only workaround I have found is to use a small-enough font size (in some cases \tiny) to allow the whole bibliography to fit on one slide. This is mildly problematic with respect to accessibility but better than truncating the bibliography because it overflows the slide.

(Discuss on Mastodon)

By David Eppstein

• Joe Halpern (1953–2026) (\(\mathbb{M}\)). A leader in the mathematical reasoning about knowledge, founder of the Computing Research Repository (later the CS branch of arXiv), and recipient of the Gödel Prize and Dijkstra Prize.

• A single-line drawing that is simultaneously an open knight’s tour of a 99x99 chessboard and a 3x3 Latin square.

• The circle packing theorem (\(\mathbb{M}\)): every planar graph can be represented by the tangencies of a system of non-overlapping circles. This theorem was proved by Koebe in 1936, and popularized in the 1980s by Fields medalist William Thurston as a discrete analogue to conformal mapping and uniformization. Its Wikipedia article was created by Oded Schramm in 2008, not long before his untimely mountaineering death. In his own research, Schramm found deep analogies between random walks on circle packings and Brownian motion. My interests in circle packing relate to its use in drawing graphs, constructing polyhedra for given graphs, modeling soap bubble foams, and finding planar separators. And others have found even more varied applications from the study of discrete symmetry groups of hyperbolic space to methods for visualizing the functional areas of the human brain, spread out into a flattened map. Now a Good Article on Wikipedia.

• Discussion involving Terry Tao on security vulnerabilities in the Lean theorem prover (\(\mathbb{M}\)). Importing an untrusted module can result in running arbitrary code.

• Two new papers on near-linear shortest path search in dense graphs with negative edge weights (\(\mathbb{M}\)). I don’t know the story here, but when parallel papers claiming the same strong result come out simultaneously on arXiv, it’s usually not a coincidence. The papers are:

  • “An \(n^{2+o(1)}\) time algorithm for single-source negative weight shortest paths”, Sanjeev Khanna & Junkai Song, arXiv:2602.16638

  • “Bellman-Ford in almost-linear time for dense graphs”, George Z. Li, Jason Li, & Junkai Zhang, arXiv:2602.16153

• I recently posted about archive.today (also archive.is, archive.ph, archive.fo, archive.li, archive.md, and archive.vn) using its archive links to launch a ddos attack against a blogger they accused of doxing them (\(\mathbb{M}\)). That attack triggered Wikipedia (at least, the English part) to discuss banning archive.today links, and the ensuing discussion turned up evidence that (as part of the same dispute with the same blogger) archive.today had also tampered with its archived content to falsify certain names in old archived links. This led to a quick close of the discussion and a consensus to remove all archive.today links from Wikipedia. For the same reasons I have removed all archive.today links from my blog, where I had been occasionally using them as a convenient way to access paywalled content. I suggest that others remove their links as well, lest you unwittingly become part of additional ddos attacks and falsification.

• National Institute of Standards and Technology appears to be squeezing out “foreign-born researchers” (\(\mathbb{M}\)). The language used here is especially concerning: we should not be hobbling our research institutions by limiting their researchers to being US citizens, but requiring US birth goes far beyond even that.

• Subdivisions of a triangle into smaller similar triangles lead to new substitution tilings of the plane based on the plastic and superplastic constants (\(\mathbb{M}\)). Ed Pegg, Wolfram Insights.

• One-line 3d-printable Schönhardt polyhedron (\(\mathbb{M}\)).

• “Google just keeps getting dumber”. The link goes to a screenshot of a Google Books page for the book Topics in Topology by Stevo Todorčević, displaying the plot summary “a thirteen-year-old with a talent for throwing loops and who lives on a ranch with his father and grandfather yearns for a roping horse”.

• According to the Bonnet theorem (\(\mathbb{M}\)), describing the surface distances and principal curvatures of a smooth 2d surface is enough to determine a local embedding of the surface (an immersion) into 3d. A related result by H. Blaine Lawson and Renato de Azevedo Tribuzy shows that using mean curvature instead of the principle curvatures is almost enough: for a smooth compact surface and non-constant mean curvature, there can be at most two immersions. The recent paper “Compact Bonnet pairs: isometric tori with the same curvatures” (Bobenko, Hoffmann & Sageman-Furnas, Pub. Math. de l’HÉS 2025) shows that the case of two immersions can actually happen: there are pairs of immersed tori in 3d with different shapes in 3d but the same surface distances and mean curvatures. Recently described in Quanta: “two twisty shapes resolve a centuries-old topology puzzle”.

• Flip distance of triangulations of convex polygons / rotation distance of binary trees is NP-complete (\(\mathbb{M}\)). A new arXiv preprint by Joseph Dorfer answers a well-known problem that was implicit in the STOC 1986 work of Sleator, Tarjan, and Thurston on the extreme values of flip distance / rotation distance and already explicit by 1988 in the (incorrect) claim of a polynomial time algorithm by Křivánek (see Theorem 7).

• Josh Millard investigates the number of tilings of a square by 1x2 rectangles of varying sizes.

By David Eppstein

Error-correcting codes are a method for representing data, so that one can recover the original information even if some parts of it were corrupted. The basic idea, which dates back to the revolutionary work of Shannon and Hamming about a century ago, is to encode the data into a redundant form, so that the original information can be decoded from the redundant encoding even in the presence of some noise or corruption. One prominent family of error-correcting codes are Reed-Solomon Codes which encode the data using evaluations of low-degree polynomials. Nearly six decades after they were introduced, Reed-Solomon Codes, as well as some related families of polynomial-based codes, continue to be widely studied, both from a theoretical perspective and from the point of view of applications. Besides their obvious use in communication, error-correcting codes such as Reed-Solomon Codes are also useful for various applications in theoretical computer science. These applications often require the ability to cope with many errors, much more than what is possible information-theoretically. List-decodable codes are a special class of error-correcting codes that enable correction from more errors than is traditionally possible by allowing a small list of candidate decodings. These codes have turned out to be extremely useful in various applications across theoretical computer science and coding theory. In recent years, there have been significant advances in list decoding of Reed-Solomon Codes and related families of polynomial-based codes. This includes efficient list decoding of such codes up to the information-theoretic capacity, with optimal list-size, and using fast nearly-linear time, and even sublinear-time, algorithms. In this book, we survey these developments.

I don’t have time to write a full post right now, but hopefully this is self-explanatory.

Regardless of their broader views on the AI industry, the eventual risks from AI, or American politics, right every person of conscience needs to stand behind Anthropic, as they stand up for their right to [checks notes] not be effectively nationalized by the Trump administration and forced to build murderbots and to help surveil American citizens. No, I wouldn’t have believed this either in a science-fiction movie, but it’s now just the straightforward reality of our world, years ahead of schedule. In particular, I call on all other AI companies, in the strongest possible terms, to do the right thing and stand behind Anthropic, in this make-or-break moment for the AI industry and the entire world.

By Scott

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

Lafayette Mendel, Elmer McCollum’s post-doc mentor at Yale, was intrigued by his mentee’s foray into the chemistry of nutrition. Even if the results were puzzling, Mendel saw great potential in the controlled synthetic food experiments in rodents. Mendel recruited Thomas Osborne and Edna Ferry to synthesize dozens of diets for rats and compile their results in a two-volume monograph. They focused on providing the bare backbone macronutrients of carbohydrates, fats, and proteins, but purified the food to be as basic as possible.

One of the Yale team’s key insights was comparing the relative value of diets by tracking rat growth against a baseline of “normal” growth. They drew on the rat studies of Henry Donaldson, Elizabeth Dunn, and John Watson, who used rats to understand the development of the nervous system. Donaldson et al. had weighed dozens of rats at different developmental stages and recorded the average and extreme weights of their samples. This is the average weight of Donaldson, Dunn, and Watson’s rats over time:

This normal growth curve eliminated the need for control groups when studying rat diets: a good diet would hit the curve, a bad diet would miss it. Osborne, Mendel, and Ferry first used it to disprove McCollum’s palatability hypothesis. They found a diet that the rats readily devoured but could not sustain normal growth. It consisted of hordein (a type of gluten), starch, agar, lard, and “protein-free milk.” Delicious. The milk was boiled and processed to remove fats and proteins, leaving behind milk sugars and other substances that were unknown at the time.

Even though the rats ate their fill of this mixture, their growth was terribly stunted.

The Yale team plotted the growth of individual rats, rather than the averages of multiple rats. With such individualized studies, they could also demonstrate the effectiveness of dietary changes. Here is another prototypical paper from their research monograph.

The rat was fed multiple diets over its life. The experiment begins with a mixed food diet and then switches to a purified food. Soon after the dietary switch, the rat’s growth reverses, and it rapidly loses weight. Clearly, there is something deficient with the purified food. This sort of single-subject temporal experimentation let them hone in on which of the many food substances we eat are necessary for survival. What would we call this today? A “within-subject crossover design?” What’s the p-value? Whatever the case, other chemists and biologists were convinced there was something important going on in these studies, and the work won Osborne and Mendel a Science paper. They would be credited with the discovery of essential amino acids.

F. Gowland Hopkins, a nutrition researcher at Cambridge who had discovered the amino acid tryptophan, happened across their work in those illustrious pages and realized that he had already conducted similar experiments years earlier. Hopkins hadn’t written up his rat diet findings because he suffered an illness that had taken him out of the lab. Likely, he also hadn’t realized the significance of his findings until seeing Osborne and Mendel’s write-up. Wanting to join in on the party, Hopkins rushed to write up his earlier experiments and sent them to The Journal of Physiology. Figure 2 in that paper arguably won him the Nobel Prize.

In this experiment, there were two groups, each with eight rats. Each dot in the plot is the average weight of the group on a particular day (the x-axis is days, the y-axis is grams). The white dots correspond to rats fed only bread. The black dots correspond to rats fed bread and a tiny amount of milk. The rats with the milk supplement grew dramatically faster than those fed bread alone. Just like the Yale team, Hopkins had performed a crossover study. At day 18, he swaps the diets of the two groups. Subsequently, the milk-fed rats stopped growing on their milk-free diet. In sharp contrast, the rats fed bread only started to grow once Hopkins gave them some milk.

Hopkins’ paper includes a detailed appendix that shares much of the raw data plotted in the paper’s figures. For the plot above, he does not share the complete growth series for each rat, but he does list the rat weights at days 0, 18, and 50. Using the weights at days 0 and 18, I can create a more modern display of the data, revealing the variation within the groups rather than just representing the averages. In Figure 8, I plot the percentage growth from day zero for each rat, splitting them into the groups fed milk and those not fed milk.

Each dot here corresponds to the percentage growth of an individual rat. The shaded region corresponds to the middle half of the data. The line in the shaded region is the median of the data. The lines outside the box denote the extremes of the data. Without milk, all of the rats grew less than 20% over the 18 days. With milk, every rat grew more than 60%. Scientists didn’t need a hypothesis test to see that something incredible was in the milk.

Meanwhile, back in Madison, Elmer McCollum was stressed out. Not only was he confused by his early experiments, but he was embarrassed by the refutation of his work by Mendel’s team. He was distracted by the oppressive obligations of faculty life, found teaching an unwelcome burden, and resented being tasked with working on the cow experiment. Ah, the professor life. On top of all this, he would admit later that he was not naturally gifted at caring for his rats. The combination left his rat studies far less productive than he had hoped.

The missing catalyst arrived in 1909. Marguerite Davis had recently moved back to Madison to care for her father after the death of her mother. Davis had completed her bachelor’s degree at Berkeley and hoped to continue some form of graduate study while also looking after her dad. She told McCollum she’d be willing to do freelance research with him so she could learn biochemistry. McCollum agreed, and Davis began to learn the ways of the lab. Davis quickly noted that McCollum, though proficient at catching rats, was terrible at keeping them. His colony was struggling and in general disarray. She offered to care for them, and McCollum was overjoyed to pass off the rat-keeping responsibility. Davis not only enjoyed the work but also had a talent for running the experiments. Within a year, McCollum and Davis would publish revolutionary findings in the biochemical foundations of nutrition.

McCollum and Davis tried to figure out what exactly was missing from the protein-free milk of the Yale experiments. They devised a procedure to isolate the critical component by centrifuging egg yolks in an ether bath to separate a key fat-soluble material. They found that this isolated substance was itself sufficient to trigger rat growth.

Here’s a typical example of their experimental results, which they presented in the same style as Mendel and collaborators.

For the first period, when the rat was young, McCollum and Davis fed the rat salt, protein, fats, and a little bit of carbohydrates. For the second period, they removed the fat. In this second period, the rat’s weight eventually plateaus. Then, in period three, they added the fat-soluble compounds from the egg yolk. Whatever this stuff was, it sufficed to reignite the rat’s growth.

They found this pattern remarkably repeatable. On the simple synthetic diets of only pure protein (casein), sugar (lactose), carbohydrates (starch and dextrine), and fats (lard), the rats displayed striking symptoms of malnourishment. They would languish and develop crusty buildup in their eyes. They wouldn’t mate. Adding the ether extract of egg yolk consistently cured the poor growth in these rats and fully restored them to normal.

McCollum and Davis considered five case studies of rats and their associated growth curves sufficient evidence of a major discovery. They wrote:

We have seen this prompt resumption of growth after a period of suspension result from the introduction of ether extract of butter or of egg in about thirty animals and are convinced that these extracts contain some organic complex without which the animals cannot make further increase in body weight, but may maintain themselves in a fairly good nutritive state for a prolonged period.

This fat-soluble compound turned out to be Vitamin A.

Subscribe now

By Ben Recht

In this work, we establish the first separation between computation with bounded and unbounded space, for problems with short outputs (i.e., working memory can be exponentially larger than output size), both in the classical and the quantum setting. Towards that, we introduce a problem called nested collision finding, and show that optimal query complexity can not be achieved without exponential memory. Our result is based on a novel ``two-oracle recording'' technique, where one oracle ``records'' the computation's long outputs under the other oracle, effectively reducing the time-space trade-off for short-output problems to that of long-output problems. We believe this technique will be of independent interest for establishing time-space tradeoffs in other short-output settings.

Authors: Clément Carbonnel

Authors: Peter Borg, Yair Caro

Authors: Michael Stephen Fiske

Authors: David Dirnfeld, Fabien Delattre, Pedro Miraldo, Erik Learned-Miller

Authors: Eduardo Paluzo-Hidalgo, Yuichi Ike

Authors: Amir Abboud, Ron Safier, Nathan Wallheimer

Authors: Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara

Authors: Joseph Dorfer

Authors: Alkis Kalavasis, Anay Mehrotra, Manolis Zampetakis, Felix Zhou, Ziyu Zhu

Authors: Karl Bartolo, Peter Borg, Magda Dettlaff, Magdalena Lemańska, Paweł Żyliński

Authors: Henrik Reinstädtler, Christian Schulz, Nodari Sitchinava, Fabian Walliser

Authors: Yaseen Abd-Elhaleem, Michal Dory, Oren Weimann

Authors: Kleitos Papadopoulos

Authors: Alexander Zlokapa, Bobak T. Kiani

Authors: Isaac D. Myhal, Oliver Serang

Authors: Yongjian Zhan

Authors: Faruk Alpay, Levent Sarioglu

We introduce spiky rank, a new matrix parameter that enhances blocky rank by combining the combinatorial structure of the latter with linear-algebraic flexibility. A spiky matrix is block-structured with diagonal blocks that are arbitrary rank-one matrices, and the spiky rank of a matrix is the minimum number of such matrices required to express it as a sum. This measure extends blocky rank to real matrices and is more robust for problems with both combinatorial and algebraic character. Our conceptual contribution is as follows: we propose spiky rank as a well-behaved candidate matrix complexity measure and demonstrate its potential through applications. We show that large spiky rank implies high matrix rigidity, and that spiky rank lower bounds yield lower bounds for depth-2 ReLU circuits, the basic building blocks of neural networks. On the technical side, we establish tight bounds for random matrices and develop a framework for explicit lower bounds, applying it to Hamming distance matrices and spectral expanders. Finally, we relate spiky rank to other matrix parameters, including blocky rank, sparsity, and the $\gamma_2$-norm.

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.

Continue on to Part 4.

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

Authors: Martin Durand

Authors: Klara Mundilova, Oliver Gross

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

Authors: Arnaud Casteigts, Matteo De Francesco, Pierre Leone

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

Authors: Noam Goldberg, Danny Hermelin, Dvir Shabtay

Authors: John Jeang, Vladimir Podolskii

Authors: Alexander Lindermayr, Jens Schlöter

Authors: Kaixin Wang, Kaiqiang Yu, Cheng Long