What is an "advanced" algorithm? How do you differentiate this from other algorithms?
AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms
171–180 of 298 posts
Re: AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms
#172> 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 multi…
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.
Re: AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms
#173Can someone explain how an "agent" is distinct from a "chatbot"?
I'm reading descriptions of agents and it just seems like the same tech deployed with authority to write and a scheduler
Re: AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms
#174Earlier quoted context omitted.
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).
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).
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."
Re: AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms
#175Earlier quoted context omitted.
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).
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 a…
If you don't want to allow division by 2 then there is Winograd's algorithm from 1967 which works over any commutative ring and uses 48 multiplications for 4 x 4.
Re: AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms
#176Interestingly, it seems alphaevolve has already been in use for a year, and it is just now being publicly shown. The paper also mentions that it uses Gemini 2.0 (pro and flash), which creates a situation where Gemini 2.0 was used in a way to train Gemini 2.5. I don't know if I would call this the fabled "self improving feedback loop", but it seems to have some degree of it. It also begs the question if Alphaevolve wa…
> which creates a situation where Gemini 2.0 was used in a way to train Gemini 2.5.
The use of synthetic data from prior models to create both superior models and distilled models has been going on since at least OpenAI's introduction of RLHF, and probably before that too.
Re: AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms
#177Earlier quoted context omitted.
Merely from your telling, it seems it is no longer "not worth the effort", as "the effort" has been reduced drastically. This is itself significant.
That right and In fact it’s the core purpose of the tool. This is complex automation which by definition compresses the solution into a computable process that works more efficiently than the non-automated process That, in fact, is the revolutionary part - you’re changing how energy is used to solve the problem.
Faster, yes; more efficiently...I guess that's why they're funding nuclear plants then?
Re: AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms
#178Earlier quoted context omitted.
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).
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 a…
Z_2 has characteristic 2, not 0.
Re: AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms
#179> 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 multi…
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…
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.
Re: AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms
#180This is an important moment. We now have verifiable evidence that these systems can do new useful research that has actual value in the real world. That 1% savings is only the start as well. I would expect the compounding number of gains to be significant over some time. Also in a way this process was used to make gemini 2.5 pro better, so its like a baby step towards recursive self improvement. Not fully automated yet, but there are hints of where this is going.