An easy choice for paper of the year, a paper that has nothing to do with randomness, interaction, quantum, circuits or codes. Just a near quadratic improvement in the amount of memory you need to simulate time.
Simulating Time with Square-Root Space by Ryan Williams
Any time \(t(n)\) algorithm can be simulated in space \(O(\sqrt{t(n)\log t(n)})\) greatly improving the \(O(t(n)/\log t(n))\) result from the 70's. Ryan's work makes strong use of last year's space efficient tree evaluation by James Cook and Ian Mertz. More in my February post and a Quanta article which did a better job explaining the importance of the result than I could.
Bill is also excited by the new \(O(m\log^{2/3}n)\) single-sourced shortest path algorithm by Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu and Longhui Yinthat that beats out Dijkstra on sparse graphs.
Last year I wrote
We're heading to a perfect storm for US higher education with the oncoming trains of the new administration, artificial intelligence, fiscal challenges and the demographic cliff. Hang on tight, it's going to be a bumpy ride.
Bumpy is an understatement and we're just starting the ride. Limited immigration, National Science Foundation woes in its 75th anniversary, and a drop in computer science enrollments as AI continues to suck up the atmosphere. Do we buckle down or should we completely rethink our institutions?
In the spirit of all the AI wrapped content, I asked Claude to put together a full year in review for this blog. This is getting scarily good.
We remember George Foreman, Frank Gehry, Ray Laflamme, Tom Lehrer, Charles Lin, Pradyut Shah and Tom Stoppard.
We thank our guest posters Eric Allender, Daniel Fernández and Alberto Fraile, Clyde Kruskal and Nick Sovich.
See you all in January!
I read the Claude-generated Review of the blog. It was very good. I did fine ONE mistake (ONE is a VERY small number.) The review claimed that Bill G wrote the blog post about LOTS of P vs NP proof, when actually Lance wrote that one. I wonder why it got that wrong.
ReplyDeleteThat aside, I concur with Lance that its scary how well Claude did.
Why do you care how well Claude did?
ReplyDeleteI'm serious here. We know what the underlying algorithms are: random text generation with no model to do logic or computations on and thus no means of verification of the generated text. And no scientific model of what meaning in language consists of. In any sense of "intellectual content", there's none there. Sure, it's "better" than single-word based Markov chain text generation. But it's still exactly the same thing: random text generation.
The world's gone crazy, and some of the smartest people around have gone there with it.
I care how well Claude did since I am curious how well AI can do at various tasks. You are saying its jut random text generation. Fine. i am curious how well random text generation can do.
Delete" i am curious how well random text generation can do."
DeleteBut that makes no _intellectual_ sense. Reading randomly generated text is, any way you could possibly think about it, no more sensible now than it was in 1990 with the Markov Chain programs.
LLMs can _copy_ reasoning they find on the net, but they don't know what multiplication is (they look up the answer). They are, in logical principle, really really dumb.
Even worse, playing with an LLM and thinking you are going to "figure out what it can, or cannot, do" is a fools erand, because it has way more text in its database than you have in your head and there are a lot of blokes that have a lot of their money on the line that's dependent on them creating front and rear ends for their pet LLM that hide the infelicities.
As Peter Shor (yes, that Peter Shor) pointed out (over at "Not Even Wrong"), they are good at "solving" problems for which there are solutions on the net, and seriously terrible for problems that don't have solutions.
The hilarious thing is Google and MickeySoft messed up their search engines by putting in ads and links to paying sites ("enshitification"), so the LLMs act for most people as better search engines than the search engines. (They're not, since you don't know when they're being wrong, but that's another discussion.)
I agree with Peter Shor. Okay. So I can use chatGPT (or some other AI) to see if the answer to the question I am asking is on the web. I will then CHECK what it says. So- what is your objection to using AI to see i the answer to your problem is on the web. The CHECKING is really important and (alas) may be a step that students skip. but I wont.
ReplyDeleteI don't object to your using Claude, I object to claims of the form "Claude proved X". (I also object to posting text generated by LLMs, because I have better things to do with my time than reading such text. I _recommend_ that you don't waste your time reading such text also, but it's your time, not mine.)
DeleteIf you discuss a problem that's been solved, you need to give credit to the bloke who solved it.
Say you use a Google search to find a page that has the solution. Did Google do the work or did the blokes that wrote that page? That's an odd question.
But people write as though Claude/ChatGPT _said_ something. It didn't, some source did. No one says "Google claims that (whatever)". They say "A bloke named X presented a proof of Y in this paper, which Google found for me" or "Wikipedia reports that ...:"
So, specifically, if you actually checked Claude then you would have found a real reference to the actual source of the information. If you wouln't say "Google proved X", why is "Claude proved X" any less problematic?
Also note that since you have to find the actual sources and read them, Claude didn't save you much time...
In the case at hand Claude was asked to give a full year in review for the blog. It produced the review and it was accurate. You raise a good question- is it appropriate to say ``Claude wrote a good summary of the blog posts in 2025'' or to say--- something else? Not sure how else to put it. A long sure how else to put it.
DeleteLLMs are good at summarizing. No surprise there.
ReplyDelete1 mistake is a big number, depending on the real in question.
why they make mistake is because of their architecture, it is probabilistic text generation.
the easy improvements in quality through scaling had essentially stopped, the later improvements you see are the result of a lot of small hacks here and there essentially.
and more and more experts are starting to acknowledge that LLMs will not get us to human level intelligence. even Ilya Sutskever admitted that the LLMs keep making unexpected mistakes in easy cases and we need new fundamental ideas.
world models are the new thing that experts in deep learning find most promising.
"They took the credit for your second symphony. Rewritten by machine on new technology."
ReplyDeleteNow I understand the problems The Buggles could see...
AI generated summary sure reads dry and matter-of-fact, doesn't it?
ReplyDeleteIt does a good job at a check-all-the-boxes type brute-forcing task, but fails at extracting coherent themes or exploring what-ifs or speculating where-tos regarding possible leads for future exploration.
The latter (intangible) aspects are presumably what the readers are seeking (at least I'd hope so).
Enshittification - it is what it is; machines doing what machines are really good at (repeatability); would I be scared that a machine can effortlessly generate the first trillion primes?
I would sure be scared if a machine came up with a new property of primes; say like the "Fermat's Little Theorem".