Readit News logoReadit News
wbhart commented on Gemini with Deep Think achieves gold-medal standard at the IMO   deepmind.google/discover/... · Posted by u/meetpateltech
daxfohl · a month ago
Oh, I didn't realize that last year the problem formalization was a human effort; I assumed the provers themselves took the problem and created the formalization. Is this step actually harder to automate than solving the problem once it's formalized?

Anyway mainly I was curious whether using an interactive prover like Lean would have provided any advantage, or whether that is no longer really the case. My initial take would be that, yes, it should provide a huge advantage. Like in chess and go, it'd allow it to look algorithmically through a huge search space and check which approaches get it closer to resolving, where the AI is "only" responsible for determining what approaches to try.

OTOH, maybe not. Maybe the search space is so big that trying to go through it linearly is a waste of CPU. In which case, plausibly the translation to Lean offers no benefit. And now that I think about it, I could imagine that. When doing problems like these, you kind of have to figure out the overall approach end to end first, fill in any gaps in your logic, and the formalization/writing step is kind of the last thing you do. So I could see where starting on formalization from the start could end up being the wrong approach for IMO-level problems. It'd just be nice to have that confirmed.

The cool thing is that if true, it implies this is something completely different from the chess/go engines that rely on sheer computational power. Not so much of a "deep blue" moment, but more of an existential one.

wbhart · a month ago
I have not been working on formalization but theorem proving, so I can't confidently answer some of those questions.

However, I recognise that there is not so much training data for LLMs wanting to use the Lean language. Moreover, you are really teaching it how to apply "Lean tactics", which may or may not be related to what mathematicians do in standard texts on which LLMs have trained. Finally, the foundations are different: dependent type theory, instead of the set theory that mathematicians use.

My own personal perspective is that esoteric formal languages serve a purpose, but not this one. Most mathematicians have not been hot on the idea (with a handful of famous exceptions). But the idea seems to have gained a lot of traction anyway.

I'd personally like to see more money put into informal symbolic theorem proving tools which can very rapidly find a solution as close to natural language and the usual foundations as possible. But funding seems to be a huge issue. Academia has been bled dry, and no one has an appetite for huge multi-year projects of that kind.

wbhart commented on Gemini with Deep Think achieves gold-medal standard at the IMO   deepmind.google/discover/... · Posted by u/meetpateltech
daxfohl · a month ago
I'd also be curious as to why not use Lean. Is it that Lean use at this point makes the problems too easy to brute force? Or is it that Lean at this point just gets in the way of things?
wbhart · a month ago
Lean is an interactive prover, not an automated prover. Last year a lot of human effort was required to formalise the problems in Lean before the machines could get to work. This year you get natural language input and output, and much faster.

The advantage of Lean is that the system checks the solutions, so hallucination is impossible. Of course, one still relies on the problems and solutions being translated to natural language correctly.

Some people prefer difficult to read formally checked solutions over informal but readable solutions. The two approaches are just solving different problems.

But there is another important reason to want to do this reliably in natural language: you can't use Lean for other domains (with a few limited exceptions). They want to train their RL pipelines for general intelligence and make them reliable for long horizon problems. If a tool is needed as a crutch, then it more or less demonstrates that LLMs will not be enough in any domain, and we'll have to wait for traditional AI to catch up for every domain.

wbhart commented on AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms   deepmind.google/discover/... · Posted by u/Fysi
gjm11 · 4 months ago
My understanding of the situation is that:

1. Waksman's algorithm works in any commutative ring admitting division by 2.

2. In particular, it won't work when the matrix entries are themselves matrices, which means you can't use it recursively to get an algorithm for n-by-n matrices with large n with a better exponent than you get from Strassen's algorithm.

3. The Deep Mind paper is annoyingly unexplicit about whether the algorithm it reports has that property or not.

4. What they say about tensors suggests that their algorithm can be used recursively to do better than Strassen (but, note, there are other algorithms that are substantially better for very large n which using their algorithm recursively would very much not outperform) but it's possible I've misunderstood.

5. They explicitly talk about complex-valued matrices, but I think they don't mean "complex numbers as opposed to matrices, so you can't do this recursively" but "complex numbers as opposed to real numbers, so our algorithm doesn't get you a 4x4 matmul using 48 real multiplications".

I am not certain about points 4 and 5. The language in the paper is a bit vague. There may be supporting material with more details but I haven't looked.

wbhart · 4 months ago
1. Correct

2. Correct, however you can use Waksman as a basecase and always beat Strassen (though it is not asymptotically better of course).

5. Possible, but even so, there is already an algorithm that will work with 46 real multiplications (and some divisions by 2). The real numbers are commutative and admit division by 2.

wbhart commented on AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms   deepmind.google/discover/... · Posted by u/Fysi
nemonemo · 4 months ago
The answer says "For rings in which division by 2 is permitted". Is there the same constraint for AlphaEvolve's algorithm?

Edit2: Z_2 has characteristics 2.

Edit: AlphaEvolve claims it works over any field with characteristic 0. It appears Waksman's could be an existing work. From the AlphaEvolve paper: "For 56 years, designing an algorithm with fewer than 49 multiplications over any field with characteristic 0 was an open problem. AlphaEvolve is the first method to find an algorithm to multiply two 4 × 4 complex-valued matrices using 48 multiplications."

wbhart · 4 months ago
Z_2 has characteristic 2, not 0.
wbhart commented on AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms   deepmind.google/discover/... · Posted by u/Fysi
lf88 · 4 months ago
By googling "4x4 matrices multiplication 48" I ended up on this discussion on math.stackexchange https://math.stackexchange.com/questions/578342/number-of-el... , where in 2019 someone stated "It is possible to multiply two 4×4 matrix A,B with only 48 multiplications.", with a link to a PhD thesis. This might mean that the result was already known (I still have to check the outline of the algorithm).
wbhart · 4 months ago
As already noted in a post by fdej further down, Waksman's algorithm from 1970, which works over the complex numbers, requires only 46 multiplications (and I guess, divisions by 2, which may or may not be relevant depending on your actual ring).
wbhart commented on AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms   deepmind.google/discover/... · Posted by u/Fysi
fdej · 4 months ago
> From the paper, "Notably, for multiplying two 4 × 4 matrices, applying the algorithm of Strassen recursively results in an algorithm with 49 multiplications, which works over any field...AlphaEvolve is the first method to find an algorithm to multiply two 4 × 4 complex-valued matrices using 48 multiplications."

...but Waksman's algorithm from 1970 [1] multiplies two 4 x 4 complex-valued matrices using only 46 multiplications (indeed, it works in any ring admitting division by 2).

Sloppy by DeepMind and by Nature to publish such a claim - did they not ask someone knowledgeable about matrix multiplication to review the work?

[1] https://doi.org/10.1109/T-C.1970.222926

wbhart · 4 months ago
There's even an Open Source implementation of Waksman's in Flint, the package fdej maintains.

Deleted Comment

wbhart commented on A cycle-accurate IBM PC emulator in your web browser   martypc.net/?mount=fd:0:A... · Posted by u/GloriousCow
wbhart · 4 months ago
I've been using MartyPC for a few years and except for emulating glitches in hardware which depend on the manufacturer, date of manufacture or even temperature, it is getting harder to find cycle accurate tricks that MartyPC can't emulate perfectly (believe me, we've been trying).

The whole thing is a marvel of software engineering!

What is remarkable is that the author (GloriousCow) doesn't complain that people are ripping off his code and ideas, but that more people haven't used his learnings to create other cycle accurate emulators for the PC.

wbhart commented on What we learned copying all the best code assistants   blog.val.town/blog/fast-f... · Posted by u/stevekrouse
stevekrouse · 8 months ago
This post is the latest in a series about Townie, our AI assistant.

Our first had a nice discussion on HN: https://blog.val.town/blog/codegen/

The other posts in the series:

- https://blog.val.town/blog/townie/

- https://blog.val.town/blog/building-a-code-writing-robot/

wbhart · 8 months ago
This blog article is written in a very engaging way. It seems to be more or less a masterclass on how to keep someone's attention, although there is no meta-story making you wait for the big fulfillment at the end.

I think it is the short, punchy sections with plenty of visuals and the fact that you are telling a story the whole way through, which has a natural flow, each experiment you describe, leading to the next.

wbhart commented on The Theory of Topos-Theoretic 'Bridges' – A Conceptual Introduction (2016)   glass-bead.org/article/th... · Posted by u/ebcode
wbhart · a year ago
This is an interesting article, but the absence of simple examples of theories and their toposes and invariants made it seem a little abstract. Surely if the technique is so powerful, there ought to be easy examples of it aplenty.

u/wbhart

KarmaCake day2458December 22, 2010
About
I am a computer algebra/computational number theory researcher. I spend most of my time maintaining the Flint C library, and the Nemo.jl and Singular.jl libraries. I also work on algorithms for fast arithmetic.

My favourite languages are C and Julia.

View Original