17
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
this post was submitted on 18 May 2025
17 points (100.0% liked)
TechTakes
2122 readers
278 users here now
Big brain tech dude got yet another clueless take over at HackerNews etc? Here's the place to vent. Orange site, VC foolishness, all welcome.
This is not debate club. Unless it’s amusing debate.
For actually-good tech, you want our NotAwfulTech community
founded 2 years ago
MODERATORS
Your understanding is correct. It's worth knowing that the matrix-multiplication exponent actually controls multiple different algorithms. I stubbed a little list a while ago; important examples include several graph-theory algorithms as well as parsing for context-free languages. There's also a variant of P vs NP for this specific problem, because we can verify that a matrix is a product in quadratic time.
That Reddit discussion contains mostly idiots, though. We expect an iterative sequence of ever-more-complicated algorithms with ever-slightly-better exponents, approaching quadratic time in the infinite limit. We also expected a computer to be required to compute those iterates at some point; personally I think Strassen's approach only barely fits inside a brain and the larger approaches can't be managed by humans alone.
I'm not sure what you mean by your last sentence. All of the actual improvements to omega were invented by humans; computers have still not made a contribution to this.
Oh, sorry. We're in agreement and my sentence was poorly constructed. The computation of a matrix multiplication usually requires at least pencil and paper, if not a computer. I can't compute anything larger than a 2 × 2. But I'll readily concede that Strassen's specific trick is simple enough that a mentalist could use it.