Birbla

Join the discussion

Write your take first — we'll ask for email only when you're ready to publish.

Sign in
  • Hacker News
  • > the algorithm requires you to multiply complex numbers whose magnitudes grow superpolynomially with n.

    Err... doesn't that completely invalidate the big-O analysis!?

    I suspected that these Open AI "proofs" of sub-nlogn times were cheating somehow, by sweeping something under a rug. This seems to be it!

    by jiggawatts
  • I’ve made some half hearted attempts to try and understand even the framing of some of these problems that were solved, and my god theoretical math is hard. It’s completely impenetrable with unknown symbols and hard to comprehend bounds and several orders of derivatives. It’s all unintuitive to me.
    by dyauspitr
  • I am as upset as the slew of math slop from OpenAI as the next guy, but I do not understand this article. Are they saying that this was not a true improvement because the algorithm is _galactic_? Human algorithm researchers have been publishing those sorts of results for decades now
    by agnishom
  • Did not realize that the model of computation for all of the banner computational complexity results from last week was "exact complex arithmetic." Is this and/or "exact real arithmetic" a common premise for papers in this field? My assumption as an outsider was that people mostly care about things equivalent to Turing machines.
    by scuppernong
  • There is currently an effort underway to improve the bound. They have reached at a much larger kappa around 0.001635527380375392

    https://github.com/CrocSwap/integer-mult-bounds

    by itissid
  • This is a bad take. I will happily acknowledge the new term "slopository" which I had not heard before, while taking the author to task for malice towards theorists. STOC/FOCS/SODA, etc are not about "doing practical algorithms". If you want that, you go to ESA, ALENEX, or VLDB/SIGMOD, or any of the other more applied venues featuring this work. I don't think it's fair to just shit on theory because they don't do experiments---they're mathematicians, and it is fine to have absurd constants in your big-O as long as they are constants.

    PS. I can have this view while simultaneously thinking that Ben is a badass.

    by p11p
  • To be honest this reminds me of interview leetcode. Like I remember one where you could get constant time if you made nested hashtables covering character sequences that might have made sense in USCII but probably would be impossible to maintain in UTF. In general leetcode problems love goading you to treat the ASCII character space as constant time to deal with and it's stupid. And it seems very similar to this.
    by Glyptodon

Explore Birbla archives