Theory of Computing Report

In this post present a very good interview of Scott Aaronson with Yuval Boger of QuEra, in which Scott gives a detailed and thoughtful account of his view of my position. Scott nicely characterizes the position I put forward early on as follows:

“There has to be some principle of correlated noise that comes on top of quantum mechanics and somehow screens off quantum computation”

Indeed, my previous post described, with the benefit of time perspective, conjectures I made about correlated noise twenty years ago. If correct, they would pose major obstacles to quantum computers. The fact that these conjectures remain undecided after twenty years may give us some indication of the time scale required both for progress in building quantum computers and for understanding whether quantum computation is possible at all.

Today, in the first part of the post I quote Scott’s view of my position, and in the second part I offer my responses. 

Let me mention two points I made that are relevant in broader scientific contexts. 

• In my view, carefully checking experimental claims—especially major ones—is an important part of scientific work. 
• As a general rule, raw data for such experiments should be publicly available.

While I do not always agree with Scott on the technical level, I find Scott’s answer perfectly reasonable. Over the decades—and especially in the past seven years—some of Scott’s references to my position were hostile, mocking or offensive, so I am glad that he chose a different path in this interview.

A fictitious scene generated by AI of Yuval, Scott, and me having a friendly discussion about quantum computing. In reality, I have not yet met Yuval, and I have not met Scott for many years. (Scott and Yuval approved the use of the picture.)

Scott Aaronson’s View of my View

Yuval: I’ve heard you refer many times in your talks to an argument with Gil Kalai about whether large-scale quantum computing is even possible. Do you think he still has a path to being vindicated, or is it over?

Scott: I feel like his path has been getting narrower and narrower. Gil Kalai is a brilliant mathematician and one of the leading skeptics of quantum computing. What he was postulating was that he believes quantum mechanics—quantum mechanics is fine—but there has to be some principle of correlated noise that comes on top of quantum mechanics and somehow screens off quantum computation.

I’ve never entirely understood why he’s so certain of that. Maybe it’s more accurate to say he starts with quantum computation being impossible as his axiom, then works backwards to find what kinds of correlated noise would kill the schemes for quantum error correction and therefore vindicate his axiom.

He’s come up with various models. I never found them physically plausible, but at least he was sticking his neck out, which is more than a lot of quantum computing skeptics were doing. He was proposing models and making predictions. His prediction was that at the scale of 50 to 100 qubits and hundreds or thousands of gates, you’d see correlations in the errors. If you apply a thousand gates, each 99.9% accurate, the total accuracy wouldn’t just be 0.999 to the thousandth power—it would be much worse because all the different errors would interact with each other.

Now those experiments have been done—famously by Google, Quantinuum, USTC, and I believe QuEra has done relevant demos too. And again and again, this is not what we’ve seen. The total accuracy does go down exponentially with the number of gates, but it merely goes down exponentially—exactly the way the theory of quantum fault tolerance presupposed 30 years ago. If this is all that’s going on—simple uncorrelated noise—then quantum error correction is going to work. It’s merely a staggeringly hard engineering problem to build this at the scale where it works.

Over the last five years, Gil Kalai has been driven in a really weird direction where he’s basically saying these experiments have to be wrong. He keeps writing to the Google people requesting more of their raw data—he CCs me on the emails—then does his own analyses, posts about it on the archive. He keeps saying their 2019 experiment must have been fallacious. But in the meantime, there’s been a dozen other experiments by other companies all getting the same conclusion. He’s fighting a losing battle at this point.

The fact that someone of his capability tried so hard to prove quantum computing impossible and failed makes me more confident. If there is a fundamental roadblock, it has to be something totally new and shocking, something we haven’t foreseen and Gil hasn’t foreseen either—some change to the laws of physics that somehow wouldn’t have reared its head with thousands of gates but will do so at millions of gates.

The scientist in me hopes we’ll make that discovery. I hope quantum computing will be impossible for some reason that revolutionizes physics—how exciting would that be? But that’s not my prediction. My prediction is that the more boring, conservative thing will happen: quantum computing will merely be possible, just like the theory said.

Some responses

Motivation

Maybe it’s more accurate to say he starts with quantum computation being impossible as his axiom, then works backwards to find what kinds of correlated noise would kill the schemes for quantum error correction and therefore vindicate his axiom.

Yes, this characterization of my work on correlated errors is essentially accurate, and it is often how I describe it myself. (See section “Motivation” of my previous post.)

My later works on quantum supremacy for NISQ computers analyzed the computational complexity and noise sensitivity of NISQ devices based on standard noise models.  Both directions lead to predictions at the scale of hundreds or thousands of gates.

Correlated errors

His prediction was that at the scale of 50 to 100 qubits and hundreds or thousands of gates, you’d see correlations in the errors.

Yes. For the precise predictions look at the previous post.

 If you apply a thousand gates, each 99.9% accurate, the total accuracy wouldn’t just be 0.999 to the thousandth power—it would be much worse because all the different errors would interact with each other.

No, this was not part of my predictions.

And again and again, this is not what we’ve seen. The total accuracy does go down exponentially with the number of gates, but it merely goes down exponentially—exactly the way the theory of quantum fault tolerance presupposed 30 years ago.

As I explained in item 8 of my previous post, this behavior does not contradict my conjectures regarding correlated errors. (I agree that such a behavior, if confirmed, is overall encouraging.)

Scrutinizing the Google 2019 experiment and other experiments

Over the last five years, Gil Kalai has been driven in a really weird direction where he’s basically saying these experiments have to be wrong. He keeps writing to the Google people requesting more of their raw data—he CCs me on the emails—then does his own analyses, posts about it on the archive.

Since I regard this issue as important in broader scientific contexts let me highlight my response.

In my view, carefully checking experimental claims—especially major ones—is an important part of scientific work. 

I also think that, as a general rule, raw data for such experiments should be publicly available.

(Scott was CC-ed to the correspondence because Scott initiated it; we would love to have a similar discussion with the relevant Google team about the 2024 distance-3,-5,-7 surface code paper and if Scott can make the connection this would be helpful.)

He keeps saying their 2019 experiment must have been fallacious.

Our findings indicate that the experiment may indeed have been flawed.

As I wrote elsewhere “I believe more can be done to clarify and explain the findings of our papers.” So far, the concerns raised in our papers were directed mainly to the Google team itself (and to interested specialists), and non-specialists may have found them difficult to follow. My 2024 post provides a short introduction of our work. 

But in the meantime, there’s been a dozen other experiments by other companies all getting the same conclusion. He’s fighting a losing battle at this point.

We examined the Google 2019 experiment carefully and looked less carefully at several other experiments. (I would personally be interested to extend our statistical study to the Google 2024 surface code paper.) If people find our efforts valuable, they may go on to scrutinize additional experiments. We would be happy to share our experience and computer programs.

For comparison, there have also been many experiments claiming the observation of Majorana zero modes (MZM), yet it remains an open question whether they have actually been demonstrated. (There are reasons to think that MZM were not conclusively demonstrated and to doubt the methodology of some of the experimental efforts. ) 

Conclusion

The fact that someone of his capability tried so hard to prove quantum computing impossible and failed makes me more confident.

This is perfectly OK! My goal is to advance understanding—even if the conclusions eventually go against my own views. 

If there is a fundamental roadblock, it has to be something totally new and shocking, something we haven’t foreseen and Gil hasn’t foreseen either—some change to the laws of physics that somehow wouldn’t have reared its head with thousands of gates but will do so at millions of gates.

Contrary to what Scott says, my conjectures and explicit predictions would already manifest themselves at the scales of hundreds of gates and of thousands of gates (perhaps even tens of gates), rather than only at the scale of millions.

__________

So what’s wrong with a little bit of hype?

There are various other interesting issues raised in Scott’s answer about my argument and in the entire interview. An interesting question raised by Yuval Boger in the interview was about hype in commercialization:

Yuval: It takes a lot of money to build a quantum computer and even more to develop one. This money comes from investors, and investors need to believe in a vision and a future. So what’s wrong with a little bit of hype to get the money you need to execute on the plan?

Yuval Boger graduated from the Hebrew University of Jerusalem. He is now the chief commercial officer for QuEra Computing.

By Gil Kalai

We have an open position for a doctoral candidate in the field of algorithmic operations research. The position is funded for 3 years by the NSF.

Requisite qualifications: Familiarity with algorithmic design, computational complexity, linear programming and game theory.

Website: https://directory.statler.wvu.edu/faculty-staff-directory/piotr-wojciechowski
Email: pwojciec@mail.wvu.edu

By shacharlovett

What’s been clear so far about this conference on Cultural AI is the organizers were interested in a broadly construed definition of AI and Culture. That works for me, as my talk ended up being about two ways of construing the culture of benchmarking. Here’s a summarized version of what I said.

I’ve been a machine learning researcher for nearly 25 years now (yikes), and I opened with a slide describing machine learning that I originally made in 2003.

It still works. Machine learning is prediction from examples, and that’s it. You have some blob of stuff that you call X’s. You have some blob of stuff you call Y’s, and you build computer programs to predict the Y’s from the X’s. The key thing that makes machine learning algorithms different than other kinds of predictions is that you deliberately try to bake in as few assumptions as possible, other than the fact that you have examples.

I find the online discourse castigating those who say “LLMs are just next token predictors” beyond annoying. They are just next token predictors. And that’s fascinating.1

The fascinating part comes in convincing yourself that your function works on new examples. How do you do that? Anybody who has read David Hume knows you can’t do it with formal proof. We convince ourselves through a particular system of evaluation. And then we built an entire engineering discipline on top of this.

Now, what is evaluation? In our 2025 course, Deb Raji and I adapted Peter Rossi’s definition, which he developed for social scientific program evaluation.

This definition seems reasonable enough, but in a world obsessed with quantification, this sets into motion an inevitable bureaucratic collapse. If you want to make your evaluation legible and fair to all stakeholders, you must make it quantitative. If you want to handle a diversity of contexts, you must evaluate on multiple instantiations and report the average behavior. Quantification has to become statistical. And once you declare your expectations and metrics, everything becomes optimization. Evaluation inevitably becomes statistical prediction.

This bureaucratic loop swallows up not just social scientific program evaluation but engineering evaluation more broadly. If you are calculating mean-square errors, you’re shoehorning your evaluation into statistical prediction. Everyone loves to lean on the artifice of clean statistical facts. Once you have set this stage, machine learning is practically optimal by definition.

Machine learning as a discipline has no foundation beyond evaluation. This is a descriptive, not normative statement. The most successful machine learning papers work like this: I say that Y is predictable from X by Method M, and you should be impressed. I then make billions of dollars in a startup. Maybe I have to tell a story about how Method M relates to the brain or mean-field approximations in statistical physics. Fantastic stories don’t seem to hurt.

Now, here’s an invalid AI paper, which a lot of critics like to write: “Y is not predictable from X.” It is impossible to refute this claim. You can’t even refute it for simple methods, because what’s gonna happen is some high school kid is gonna go and change the rules slightly and prove you wrong. Then he will dunk on you on Twitter, gleefully writing “skill issue.”

The logical reconstruction makes the logical positivists roll over in their graves. The field is fueled by pure induction. We progress research programs by demonstration alone. And the way we convince others that our demos are cool is by sharing data and code.

Core to machine learning is the culture of data sets. I’m not sure if some poor soul is still trying to update this wikipedia page, but the field thrives on shared data with common tasks. The data sets give you an easy path to impress your colleagues. You can argue about the novelty of your method M, which achieves high accuracy on a dataset that others agree is challenging.

People have turned datasets into literal competitions, starting with the Netflix Prize, moving to the ImageNet Large Scale Visual Recognition Challenge (ILSVRC), and ending with a company that hosts hundreds of competitions. Not to get all monocausal on you, but the ImageNet Challenge is why we use neural networks today instead of other methods. More fascinating is that we declared protein folding solved because Alphafold did really well on a machine learning competition. Competitive testing on benchmarks can produce Nobel Prizes.

You might be put off by how everything in machine learning becomes an optimization competition. But let’s applaud machine learning for its brutal, ingenuous honesty about how researchers are driven by ruthless competition. If you want to read more on how this works in practice, read Dave Donoho’s construction of frictionless reproducibility, my concurrence and analysis of the mechanism and costs, the history Moritz Hardt and I lay out in Patterns, Predictions, and Actions, or how it fits into the bigger story of The Irrational Decision.2

Perhaps the weirdest transition of the last decade was a move from dataset evaluation to “generalist” evaluation. Tracking the GPT series of papers is instructive. GPT2 declared language models to be general-purpose predictors, but OpenAI made their case with rather standard evaluations and metrics. GPT3 moved on to harder to pin down evaluations in “natural language inference,” but there were still tables with numbers and scores. With GPT4, we didn’t even get a paper. We got a press release formatted like a paper, which is fascinating in and of itself.3 That press release bragged about the LLM’s answers on standardized tests.

Of course, this got people excited, resulting in breathless press coverage and declarations of the end of education and white-collar work. Hypecycles are part of culture, too. Part of the goal of predicting Y from X is impressing people, and the results were very impressive. Based on the reaction, you can’t say that GPT4 didn’t surpass people’s expectations.

Now, if you live by the evaluation, you die by the evaluation. Notably, Facebook nuked their AI division after flopping on GPT4-style evaluation. Not only did its userbase think the model sucked, but they were caught cheating on their evaluations, too. In a flailing attempt to recover, Facebook went out and spent $14 billion to buy some random AI talent willing to report to King Z, and they’ve thrown orders of magnitude more at their subsequent AI investments. And what did this buy them? Literally Vibes.

We’re in this fascinating world now where research artifacts are consumer products, and the evaluation is necessarily cultural. Nonprofits funded by the same dirty money that funds AI companies might argue that they can measure the power of coding agents with objective statistical evaluations of yore. But agents are evaluated by coders’ experiences and managers’ fever dreams. I wrote this a year ago, and it remains true today: Generative AI lives in the weird liminal space between productivity software and science fiction revolution. The future of generative AI will be evaluated with our wallets. No leaderboard will help us do that.

Subscribe now

By Ben Recht

Turing Award winner and former Oxford professor Tony Hoare passed away last Thursday at the age of 92. Hoare is famous for quicksort, ALGOL, Hoare logic and so much more. Jim Miles gives his personal reflections.

Jill Hoare, Tony Hoare, Jim Miles. Cambridge, 7 September 2021

Last Thursday (5th March 2026), Tony Hoare passed away, at the age of 92. He made many important contributions to Computer Science, which go well beyond just the one for which most Maths/CompSci undergraduates might know his name: the quicksort algorithm. His achievements in the field are covered comprehensively across easy-to-find books and articles, and I am sure will be addressed in detail as obituaries are published over the coming weeks. I was invited in this entry to remember the Tony that I knew, so here I will be writing about his personality from the occasions that I met him.

I visited Tony Hoare several times in the past 5 years, as we both live in Cambridge (UK) and it turned out that my family knew his. As a Mathematics graduate, I was very keen to meet and learn about his life from the great man himself. I was further prompted by a post on this blog which mentioned Tony a few times and summarised a relevant portion of his work. I took a print out of that entry the first time I visited him to help break the ice - it is the green sheet of paper in the picture above.

Tony read the entry and smiled, clearly recalling very well the material of his that it referenced, and then elaborating a bit, explaining how vastly programs had scaled up in a rather short space of time and how they typically require different methods than many of those he had been developing in the early days.

I was aware that Tony had studied Classics and Philosophy at university so I was keen to learn how one thing had led to another in the development of his career. He explained that after completing his degree he had been intensively trained in Russian on the Joint Services School for Linguists programme and was also personally very interested in statistics as well as the emerging and exciting world of computers. This meant that after his National Service (which was essentially the JSSL) he took on a job 'demonstrating' a type of early computer, in particular globally, and especially in the Soviet Union. He described the place of these demonstrations as 'fairs' but I suppose we might now call them 'expos'. In a sense, this seemed like a very modest description of his job, when in fact - reading up on Tony's career - he was also involved in the development of code for these devices, but perhaps that's a historical quirk of the period: being a demonstrator of these machines meant really knowing them inside and out to the point of acting on the dev team (AND, one might deduce, being fluent in Russian!).

Tony would tell these stories with a clarity and warmth that made it clear that certainly he was still entirely 'all there' mentally, and that his memory was pinpoint sharp, even if there were some physical health issues, typical for anyone who makes it so far into their 80s (and, as we now know, beyond!).

A story that I was determined to hear from the source was the legendary quicksort 'wager'. The story goes that Tony told his boss at Elliott Brothers Ltd that he knew a faster sorting algorithm than the one that he had just implemented for the company. He was told 'I bet you sixpence you don't!'. Lo and behold, quicksort WAS faster. I asked Tony to tell this story pretty much every time we met, because I enjoyed it so much and it always put a smile on both of our faces. To his credit, Tony never tired of telling me this story 'right from the top'. I had hoped to visit again in the past year and record him telling it so that there was a record, but unfortunately this did not happen. However, I discover that it is indeed recorded elsewhere. One detail I might be able to add is that I asked Tony if indeed the wager was paid out or if it had merely been a figure of speech. He confirmed that indeed he WAS paid the wager (!). A detail of this story that I find particularly reflective of Tony's humble personality is that he went ahead and implemented the slower algorithm he was asked to, while he believed quicksort to be faster, and before chiming in with this belief. It speaks to a professionalism that Tony always carried.

About 50% of our meetings were spent talking about these matters relating to his career, while the rest varied across a vast range of topics. In particular, I wanted to ask him about a story that I had heard from a relative, that Tony - whilst working at Microsoft in Cambridge - would like to slip out some afternoons and watch films at the local Arts Picturehouse. This had come about because on one occasion a current film in question was brought up in conversation and it transpired Tony had seen it, much to the bemusement of some present. The jig was up - Tony admitted that, yes, sometimes he would nip out on an afternoon and visit the cinema. When I met Tony and gently questioned him on this anecdote he confirmed that indeed this was one of his pleasures and his position at Microsoft more than accommodated it.

On the topic of films, I wanted to follow up with Tony a quote that I have seen online attributed to him about Hollywood portrayal of geniuses, often especially in relation to Good Will Hunting. A typical example is: "Hollywood's idea of genius is Good Will Hunting: someone who can solve any problem instantly. In reality, geniuses struggle with a single problem for years". Tony agreed with the idea that cinema often misrepresents how ability in abstract fields such as mathematics is learned over countless hours of thought, rather than - as the movies like to make out - imparted, unexplained, to people of 'genius'. However, he was unsure where exactly he had said this or how/why it had gotten onto the internet, and he agreed that online quotes on the subject, attributed to him, may well be erroneous.

One final note I would like to share from these meetings with Tony is perhaps the most intriguing of what he said, but also the one he delivered with the greatest outright confidence. In a discussion about the developments of computers in the future - whether we are reaching limits of Moore's Law, whether Quantum Computers will be required to reinvigorate progress, and other rather shallow and obvious hardware talking points raised by me in an effort to spark Tony's interest - he said 'Well, of course, nothing we have even comes close to what the government has access to. They will always be years ahead of what you can imagine'. When pressed on this, in particular whether he believed such technology to be on the scale of solving the large prime factorisation that the world's cryptographic protocols are based on, he was cagey and shrugged enigmatically. One wonders what he had seen, or perhaps he was engaging in a bit of knowing trolling; Tony had a fantastic sense of humour and was certainly capable of leading me down the garden path with irony and satire before I realised a joke was being made.

I will greatly miss this humour, patience, and sharpness of mind, as I miss everything else about Tony.

RIP Tony Hoare (11 January 1934 - 5 March 2026)

By Lance Fortnow

Authors: Jing-Yuan Wei

Authors: Kirill Krinkin

Authors: Rahul Jain, Srijita Kundu

Authors: Aminadav Chuyoon, Amir Shpilka

Authors: Qiyuan Chen

Authors: Alexander Dobler, Siddharth Gupta, Philipp Kindermann, Fabrizio Montecchiani, Martin Nöllenburg

Authors: Stefan Huber, Kristóf Huszár, Michael Kerber, Martin Uray

Authors: Oswin Aichholzer, Katharina Klost, Kristin Knorr, Viola Mészáros, Josef Tkadlec

Authors: Jette Gutzeit, Kalani Kistler, Tim Ophelders, Anna Schenfisch

Authors: Jay Jayeshbhai Chavda, S Ganga Prasath

Authors: Josh Alman, Shyamal Patel, Rocco A. Servedio

Authors: Talya Eden, C. Seshadhri

Authors: Kshitij Gajjar, Neeldhara Misra

Authors: Sebastiano A. Piccolo, Pasquale De Meo, Giorgio Terracina, Gianluigi Greco

Authors: Chengu Wang

Authors: Hugo A. Akitaya, Joseph Dorfer, Peter Kramer, Christian Rieck, Gabriel Shahrouzi, Frederick Stock

Authors: Chao Li

Authors: Pravesh Kothari, Anand Louis, Rameesh Paul, Prasad Raghavendra

Authors: Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou

Authors: Zhou Fan, Timothy L. H. Wee, Kaylee Y. Yang

Authors: Aiya Kuchukova, Will Perkins, Xavier Povill

Authors: Priyanka Sinha, Dilys Thomas

Authors: Katalin Friedl, Levente Gegő, László Kabódi, Viktória Nemkin

Authors: Pierre Ohlmann

Authors: Mike Heddes, Igor Nunes, Tony Givargis, Alex Nicolau

Authors: Leo van Iersel, Mark Jones, Simone Linz, Norbert Zeh

Authors: Wenjing Chen, Chengyuan Qian, Shuo Xing, Yi Zhou, Victoria Crawford

Zero-knowledge codes, introduced by Decatur, Goldreich, and Ron (ePrint 1997), are error-correcting codes in which few codeword symbols reveal no information about the encoded message, and have been extensively used in cryptographic constructions. Quantum CSS codes, introduced by Calderbank and Shor (Phys. Rev. A 1996) and Steane (Royal Society A 1996), are error-correcting codes that allow for quantum error correction, and are also useful for applications in quantum complexity theory. In this short note, we show that (linear, perfect) zero-knowledge codes and quantum CSS codes are equivalent. We demonstrate the potential of this equivalence by using it to obtain explicit asymptotically-good zero-knowledge locally-testable codes.

This week, I’m attending a workshop at NYU organized by Tyler Shoemaker and Leif Weatherby called “Cultural AI: An Emerging Field.” What is Cultural AI? I’m not sure yet, but this workshop is going to find out. At this point in my career, the invite list is far more important than the planned topic, and this list is top notch. My brief talk will be about the culture of benchmarking in machine learning and how weird it is now that we’re trying to benchmark culture. I’ll let you know what the group synthesizes later this week.

In other exciting news, The Irrational Decision comes out tomorrow! Get it wherever you buy books. You can even get it in one of those atavistic bindings of printed pages wrapped in a pretty dust cover. I hear they look good in the background of your podcast.

I should say something longer about the book, but I want to see how release day moves me. So until tomorrow, here’s what I wrote about it last fall. Technology Review wrote a nice review that companioned it with two other great books, The Means of Prediction: How AI Really Works (and Who Benefits) by Max Kasy and Prophecy: Prediction, Power, and the Fight for the Future, from Ancient Oracles to AI by Carissa Véliz. I need to read both of these. In the interdisciplinary journal Critical AI, Jathan Sadowski further contextualized the book within the broader sphere of science studies.

Finally, for my friends and readers in the Bay Area, the folks at Bloomberg Beta and Reboot are sponsoring a launch event for The Irrational Decision on March 17 in San Francisco. If you’re in the area and interested, you can find more information and register here. Space is limited, but it would be great to meet you in person.

Subscribe now

By Ben Recht

Authors: Jing-Yuan Wei

Authors: Yasuhiro Takahashi, Masayuki Miyamoto, Noboru Kunihiro

Authors: Joaquim Reizi Higuchi

Authors: Eliel Ingervo, Sándor Kisfaludi-Bak

Authors: Pablo D. Viñambres, Miguel Yermo, Silvia R. Alcaraz, Oscar G. Lorenzo, Francisco F. Rivera, José C. Cabaleiro

Authors: Martin Schirneck

Authors: Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Kevin Schewior, Rob van Stee

Authors: Lucas Pesenti, Lucas Slot, Manuel Wiedmer

Authors: Ofek Gila, Michael T. Goodrich, Vinesh Sridhar

Authors: Nadir Ould-Khessal, Scott Fazackerley, Ramon Lawrence

In my graduate Ramsey Theory class I taught Kruskal's tree theorem (KTT) which was proven by Joe Kruskal in his PhD thesis in 1960.  (Should that be in a graduate Ramsey Theory class? There are not enough people teaching such a course to get a debate going.) A simpler proof was discovered (invented?) by Nash-Williams in 1963.

The theorem is that the set of trees under the homeomorphism ordering is a well quasi order.

But this blog post is not about well quasi orderings. It's about baseball brothers and AI.

The Kruskals are one of the best math families of all time. See my post on math families.The Bernoullis are another great math family.  What makes both families so great is that they had at least THREE great math people. Most have two.

Having taught the KTT and talked briefly about math families, I was curious how ChatGPT would do on the better-defined question of largest number of wins by a pair of brothers in baseball.  So I asked my students to look that up and include which tools they used,  as a HW problem  (worth 0 points but they had to do it). 

I wrote up 9 pages on what the answer is (there are some issues) and what the students' answers were. See my write up.

In case those 9 pages are tl;dr, here are the main takeaways

1) 7 of the answers given were just WRONG no matter how you look at it.

2) 7 had either the Clarksons who played in the 1880's, so don't count as modern baseball, or there were three of them, or both.  Even so, one could argue these are correct

3) 1 got it right. (That's   one got it right  not  I, bill g, got it right. It can be hard to distinguish the numeral for one, the letter capital i, and the letter small L. I blogged about L vs I here in the context of Weird AI vs Weird AL).

4) There were 13 different answers, which I find amazing.

As usual, when I study some odd issue, I learn a few other things of interest, at least to me, which may also have life lessons, though YMMV. 

a) Around 85% of pitchers in the Hall of Fame have won over 200 games. Dizzy Dean (his brother was also a pitcher which is why I was looking at this) got into the Hall of Fame with only 150 wins. Why? For 6 years he was the most dominant pitcher in the game. In addition (1) there was some sympathy for him since his career was cut short by an injury he got in an All-star game, and (2) he had a colorful personality and people liked him. The four least-wins for a HOF are: Candy Cummings (W-L 145-94).  [he is said to have invented the curveball], Dizzy Dean (W-L 150-83) , Addie Joss (W-L 160-97 )[he only played 9 years, which is less than the 10 needed for eligibility in the HOF, but he died so he was given an exception], Sandy Koufax (W-L 165-87) [he was dominant, like Dean, for a short time]. Sandy is the only one who is still alive. (W-L means Win-Loss. For example, Candy won 145 games and lost 94.)

b) Modern baseball starts in 1900. But this is arbitrary. In 1904 Jack Chesbro won 40 games which would never happen in modern baseball. But you have to draw the line someplace.  History is hard because there are fuzzy boundaries.

c) I had not known about the Clarkson brothers. 

d) My interest in this subject goes back to 1973. In that year I heard the following during a baseball game and, ever since I began blogging, I wondered how I could fit it into a blog post:


An old baseball trick question is now gone!  Just last week [in 1973] if you asked

What pair of brothers in baseball won the most games?

the answer was Christy and Henry Mathewson. Christy played for 16 seasons and had a W-L record of 373-188, while his brother Henry played in 3 games and had a W-L record of 0-1. So their total number of wins is 373 which was the record.

But this last week [in 1973] the Perry brothers, Gaylord and Jim, got 374 wins between them.  Hence the question

What pair of brothers in baseball won the most games?

is no longer a trick question since both Perrys are fine pitchers [Gaylord made it into the Hall of Fame; Jim didn't, but Jim was still quite good.]

As you will see in my writeup, the Perrys' record was broken by the Niekros.

e) Christy and Henry are a trick answer because Henry wasn't much of a player with his 0-1 W-L record. Are there other pairs like that? Greg (355 wins) and Mike (39 wins) Maddux might seem that way but they are not. While Mike only had 39 wins he had a 14-year career as a relief pitcher. Such pitchers can be valuable to the team, but because of their role they do not get many wins.

SO the usual question: Why did AI get this one wrong? Lance will say that the paid version wouldn't have and he may be right. David in Tokyo might say that ChatGPT is a random word generator. Others tell me that ChatGPT does not understand the questions it is asked (my proofreader thinks this is obvious).  I'll add that the pitcher-brother  question has more ambiguity than I thought- do you count pitchers before 1900? Do you count a brother who won 0 games? What about 3 brothers (not the restaurant)?

By gasarch

The 28th edition of the Estonian Winter School in Computer Science was held in the period 2-5 March in Viinistu, a small fishing village located on the coast of the Gulf of Finland. This edition of the school was organised by Cybernetica AS and the programme/organising committee included 

• Peeter Laud (Cybernetica AS), 
• Monika Perkmann (Tallinn University of Technology),
• Pille Pullonen-Raudvere (Cybernetica AS),
• Ago-Erik Riet (University of Tartu) and
• Tarmo Uustalu (Reykjavik University and Tallinn University of Technology). 

By Luca Aceto

We study sparse polynomials with bounded individual degree and the class of their factors. In particular we obtain the following algorithmic and structural results: 1. A deterministic polynomial-time algorithm for finding all the sparse divisors of a sparse polynomial with bounded individual degree. As part of this, we establish the first upper bound on the number of non-monomial irreducible factors of such polynomials. 2. A $\mathrm{poly}(n,s^{d\log \ell})$-time algorithm for recovering $\ell$ irreducible $s$-sparse polynomials of bounded individual degree $d$ from blackbox access to their product (which is not necessarily sparse). This partially resolves a question posed in Dutta-Sinhababu-Thierauf (Random 2024). In particular, when $\ell=O(1)$, the algorithm runs in polynomial time. 3. Deterministic algorithms for factoring a product of $s$-sparse polynomials of bounded individual degree $d$ from blackbox access. Over fields of characteristic zero or sufficiently large, the algorithm runs in $\mathrm{poly}(n,s^{d^3\log n})$-time; over arbitrary fields it runs in $\mathrm{poly}(n,{(d^2)!},s^{d^5\log n})$-time. This improves upon the algorithm of Bhargava-Saraf-Volkovich (JACM 2020), which runs in $\mathrm{poly}(n,s^{d^7\log n})$-time and applies only to a single sparse polynomial of bounded individual degree. In the case where the input is a single sparse polynomial, we give an algorithm that runs in $\mathrm{poly}(n,s^{d^2\log n})$-time. 4. Given blackbox access to a product of (not necessarily sparse or irreducible) factors of sparse polynomials of bounded individual degree, we give a deterministic polynomial-time algorithm for finding all irreducible sparse multiquadratic factors of it (along with their multiplicities). This generalizes the algorithms of Volkovich (Random 2015, Random 2017). We also show how to decide whether such a product is a complete power (in case it is defined over a field of zero or large enough characteristic), extending the algorithm of Bisht-Volkovich (CC 2025). Our algorithms most naturally apply over fields of zero or sufficiently large characteristic. To handle arbitrary fields, we introduce the notion of primitive divisors for a class of polynomials, which may be of independent interest. This notion enables us to adapt ideas of Bisht-Volkovich (CC 2025) and remove characteristic assumptions from most of our algorithms.

A symbolic determinant under rank-one restriction computes a polynomial of the form $\det(A_0 + A_1y_1 + \ldots + A_ny_n)$, where $A_0, A_1, \ldots, A_n$ are square matrices over a field $\mathbb{F}$ and $\rank(A_i) = 1$ for each $i \in [n]$. This class of polynomials has been studied extensively, since the work of Edmonds (1967), in the context of linear matroids, matching, matrix completion and polynomial identity testing. We study the following learning problem for this class: Given black-box access to an $n$-variate polynomial $f = \det(A_0 + A_1y_1 + \ldots + A_ny_n)$, where $A_0, A_1, \ldots, A_n$ are unknown square matrices over $\mathbb{F}$ and $rank(A_i) = 1$ for each $i \in [n]$, find a square matrix $B_0$ and rank-one square matrices $B_1, \ldots, B_n$ over $\mathbb{F}$ such that $f = \det(B_0 + B_1y_1 + \ldots + B_ny_n)$. In this work, we give a randomized poly$(n)$ time algorithm to solve this problem; the algorithm can be derandomized in quasi-polynomial time. To our knowledge, this is the first efficient learning algorithm for this class. As the above-mentioned class is known to be equivalent to the class of read-once determinants (RODs), we will refer to the problem as learning RODs. An ROD computes the determinant of a matrix whose entries are field constants or variables and every variable appears at most once in the matrix. Thus, the class of RODs is a rare example of a well-studied class of polynomials that admits efficient proper learning. The algorithm for learning RODs is obtained by connecting with a well-known open problem in linear algebra, namely the Principal Minor Assignment Problem (PMAP), which asks to find (if possible) a matrix having prescribed principal minors. PMAP has also been studied in machine learning to learn the kernel matrix of a determinantal point process. Here, we study a natural black-box version of PMAP: Given black-box access to an $n$-variate polynomial $f = \det(A + Y)$, where $A \in \mathbb{F}^{n \times n}$ is unknown and $Y = diag(y_1, \ldots, y_n)$, find a $B \in \mathbb{F}^{n\times n}$ such that $f = \det(B + Y)$. We show that black-box PMAP can be solved in randomized poly$(n)$ time, and further, it is randomized polynomial-time equivalent to learning RODs. The algorithm and the reduction between the two problems can be derandomized in quasi-polynomial time. To our knowledge, no efficient algorithm to solve this black-box version of PMAP was known before. We resolve black-box PMAP by investigating a crucial property of dense matrices that we call the rank-one extension property. Understanding ``cuts'' of matrices with this property and designing a black-box cut-finding algorithm to solve PMAP for such matrices (using only principal minors of order $4$ or less) constitute the technical core of this work. The insights developed along the way also help us give the first NC algorithm for the Principal Minor Equivalence problem, which asks to check if two given matrices have equal corresponding principal minors.

Sorry to interrupt your regular programming about the AI apocalypse, etc., and return to the traditional beat of this blog’s very earliest years … but I’ve now gotten multiple messages asking me to comment on something called the “JVG (Jesse–Victor–Gharabaghi) algorithm” (yes, the authors named it after themselves). This is presented as a massive improvement over Shor’s factoring algorithm, which could (according to popular articles) allow RSA-2048 to be broken using only 5,000 physical qubits.

On inspection, the paper’s big new idea is that, in the key step of Shor’s algorithm where you compute x^r mod N in a superposition over all r’s, you instead precompute the x^r mod N’s on a classical computer and then load them all into the quantum state.

Alright kids, why does this not work? Shall we call on someone in the back of the class—like, any undergrad quantum computing class in the world? Yes class, that’s right! There are exponentially many r’s. Computing them all takes exponential time, and loading them into the quantum computer also takes exponential time. We’re out of the n²-time frying pan but into the 2ⁿ-time fire. This can only look like it wins on tiny numbers; on large numbers it’s hopeless.

If you want to see people explaining the same point more politely and at greater length, try this from Hacker News or this from Postquantum.com.

Even for those who know nothing about quantum algorithms, is there anything that could’ve raised suspicion here?

1. The paper didn’t appear on the arXiv, but someplace called “Preprints.org.” Come to think of it, I should add this to my famous Ten Signs a Claimed Mathematical Breakthrough is Wrong! It’s not that there isn’t tons of crap on the arXiv as well, but so far I’ve seen pretty much only crap on preprint repositories other than arXiv, ECCC, and IACR.
2. Judging from a Google search, the claim seems to have gotten endlessly amplified on clickbait link-farming news sites, but ignored by reputable science news outlets—yes, even the usual quantum hypesters weren’t touching this one!

Often, when something is this bad, the merciful answer is to let it die in obscurity. In this case, I feel like there was a sufficient level of intellectual hooliganism, just total lack of concern for what’s true, that those involved deserve to have this Shtetl-Optimized post as a tiny bit of egg on their faces forever.

By Scott

The Quantum Information Theory group at LMU Munich is inviting applications for several postdoctoral & PhD positions. We are looking for excellent, highly motivated candidates in all areas of the field, including: quantum {algorithms & complexity, information, cryptography, formal methods} and their mathematical and CS foundations and connections. Applications will be reviewed on a rolling basis.

Website: https://michaelwalter.info/jobs
Email: michael.walter@lmu.de

By shacharlovett

We construct a universal decompressor $U$ for plain Kolmogorov complexity $\mathrm{C}_U$ such that the Halting Problem cannot be decided by any polynomial-time oracle machine with access to the set of random strings $R_{\mathrm{C}_U} = \{x : \mathrm{C}_U(x) \ge |x|\}$. This result resolves a problem posed by Eric Allender regarding the computational power of Kolmogorov complexity-based oracles.