How about focus on making BERT better. So far BERT is much worse than ChatGPT.
Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
211–220 of 328 posts
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#212How about focus on making BERT better. So far BERT is much worse than ChatGPT.
?
BERT was 5 years ago. Of course it's worse than anything introduced more recently (both inside and outside Google).
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#213Earlier quoted context omitted.
I think you're confusing proving that the hash function is collision resistant with the other goal which is hashing speed. If you really need a collision resistant hash you need to use a cryptographic hash function, but outside of cryptographic applications that is rarely the requirement. And (huge caveat, this isn't my domain expertise) I'm not sure what security properties are really "proven" about existing cryptog…
> I think you're confusing proving that the hash function is collision resistant with the other goal which is hashing speed. If you really need a collision resistant hash you need to use a cryptographic hash function. I wish this misconception would die. There is a great theory of algorithmic probabilistic hash functions, completely distinct from cryptographic hash functions. If you are designing a hash table, or a d…
> The idea is that `Pr[h(x) = h(y)]` is small _no matter the inputs x and y_.
That sounds like such a function is strongly collision resistant, which means it's also second preimage resistant. And that gets you most of the way to a cryptographic hash function.
Is the only difference that it doesn't have to be first preimage resistant? Compared to cryptographic hashes, does that expand the set of viable functions a lot, to allow first preimages while still not allowing second preimages?
> It is all about probabilistic guarantees
So are cryptographic hash functions.
When I search for `algorithmic probabilistic hash functions` I just get results about bloom filters.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#214Earlier quoted context omitted.
"may have actually made things worse. Go players..." Go players are using AI to get better at Go.
That claim is often made, and never substantiated.
Not AlphaGo, but there are newer neural networks tailored not to crush players, but to teach and explain their playing style, such as Lizzie with Leela Zero.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#215> AlphaDev uncovered new sorting algorithms that led to improvements in the LLVM libc++ sorting library that were up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements. As someone that knows a thing or two about sorting... bullshit. No new algorithms were uncovered, and the work here did not lead to the claimed improvements. They found a sequence of assembly that saves.…
What's surprising is that anyone would've expected an AI to come up with a brand-new algorithm with better complexity than pre-exsiting human-made solutions.
How could it possibly come up with something better when it doesn't even understand how the original authors of qsort/mergesort/etc came up with their own..
Sure, it's great PR for the company, but.. the results just aren't there.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#216Earlier quoted context omitted.
> I think you're confusing proving that the hash function is collision resistant with the other goal which is hashing speed. If you really need a collision resistant hash you need to use a cryptographic hash function. I wish this misconception would die. There is a great theory of algorithmic probabilistic hash functions, completely distinct from cryptographic hash functions. If you are designing a hash table, or a d…
> The idea is that `Pr[h(x) = h(y)]` is small _no matter the inputs x and y_. That sounds like such a function is strongly collision resistant, which means it's also second preimage resistant. And that gets you most of the way to a cryptographic hash function. Is the only difference that it doesn't have to be first preimage resistant? Compared to cryptographic hashes, does that expand the set of viable functions a lo…
> > It is all about probabilistic guarantees
> So are cryptographic hash functions.
Cryptographic hash functions like MD5, SHA-2, BLAKE2, etc are deterministic functions, so it doesn't really make sense to talk about Pr[h(x)=h(y)]. Either the collide or not.
It's muddied a bit by the fact that cryptographers also use universal hashing (or probabilistic hashing, or what I called algorithmic hashing) for stuff like UMACs, https://en.m.wikipedia.org/wiki/UMAC#NH_and_the_RFC_UMAC , but they often have a lot of extra considerations on top of just collision resistance.
Some algorithms also need stronger probabilistic guarantees than just collision resistance (see e.g. https://en.m.wikipedia.org/wiki/K-independent_hashing#Indepe... ). These properties are usually too hard to test for with an experimental testing suite like SMhasher, but if your hash function don't have them, people will be able to find inputs that break your algorthm.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#217Earlier quoted context omitted.
> I'm not sure what security properties are really "proven" about existing cryptographic hash functions AFAIK, we don’t even know whether trapdoor functions exist . https://en.wikipedia.org/wiki/Trapdoor_function : “As of 2004, the best known trapdoor function (family) candidates are the RSA and Rabin families of functions” Also note that the ‘examples’ section starts with: “In the following two examples, we always a…
IIRC, if P=NP then trapdoor functions do not exist, so proving that one existed would be a huge deal even outside of cryptography.
Only if your definitions of "easy" and "hard" are based entirely on complexity classes.
If you show me a setup where "easy" is n^3 and "hard" is n^15 I will happily call that a trapdoor function.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#218> AlphaDev uncovered new sorting algorithms that led to improvements in the LLVM libc++ sorting library that were up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements. As someone that knows a thing or two about sorting... bullshit. No new algorithms were uncovered, and the work here did not lead to the claimed improvements. They found a sequence of assembly that saves.…
I feel like your take is overly cynical. The fact that humans can do the same thing by hand is not really the point. The contribution lies in the fact that their method derived this improvement *automatically*, which is where the impact lies. No one cares all that much if a human can make a sorting routine 2% faster, but if a program can do it, it suddenly becomes interesting (since it suggests that a similar approac…
Automatic tuning and optimisation of code is not new.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#219Earlier quoted context omitted.
> The idea is that `Pr[h(x) = h(y)]` is small _no matter the inputs x and y_. That sounds like such a function is strongly collision resistant, which means it's also second preimage resistant. And that gets you most of the way to a cryptographic hash function. Is the only difference that it doesn't have to be first preimage resistant? Compared to cryptographic hashes, does that expand the set of viable functions a lo…
> > It is all about probabilistic guarantees > So are cryptographic hash functions. Cryptographic hash functions like MD5, SHA-2, BLAKE2, etc are deterministic functions, so it doesn't really make sense to talk about Pr[h(x)=h(y)]. Either the collide or not. It's muddied a bit by the fact that cryptographers also use universal hashing (or probabilistic hashing, or what I called algorithmic hashing) for stuff like UMA…
> Cryptographic hash functions like MD5, SHA-2, BLAKE2, etc are deterministic functions, so it doesn't really make sense to talk about Pr[h(x)=h(y)]. Either the collide or not.
Eh, that's how I usually see collision resistance described. The probability is based on generating fresh inputs with any method you want/the most effective attack method available.
But I wouldn't say the hash you linked is nondeterministic just because it has a seed. You can seed MD5, SHA-2, and BLAKE2 by tossing bytes in as a prefix. It'll prevent the same attacks and you can give it the same analysis.
So I'm still not sure in what sense a hash like this is facing different requirements than a cryptographic hash.
Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
#220Earlier quoted context omitted.
This is DeepMind's modus operandi. Every press release is just utterly hyperbolic nonsense that doesn't withstand the slightest scrutiny. AlphaGo, AlphaFold, AlphaDev... they've done literally nothing to improve the human condition, and may have actually made things worse. Go players have DECREASED their Elo after playing AlphaGo (or just quit the game altogether). I would be embarrassed to be associated with DeepMin…
I thought the same thing - it smacks of desperation at the moment, any tiny win is exaggerated . It’s not hard to see why, with the emergence (ha) of OpenAI, Midjourney and all of this generative modelling, what has DeepMind done? I imagine the execs at Google are asking them some very probing questions on their mediocre performance over the last 5 years.
They solved an open challenge problem, Protein Structure Prediction, with AlphaFold, which has been nothing short of revolutionary in the structural biology and biochemistry fields. I do scientific research in these fields and the capabilities AlphaFold provides are used now everywhere.