Matt Green muses: are n^25 galactic algorithms normal, or a glimpse of provable Algorithmica?

matthew_d_green · x · 2026-11-20

Cryptographer Matthew Green poses an open question in theoretical CS: are n^25 "galactic algorithms" normal for the universe, or the first strands of mist revealing a provable Algorithmica? He notes the value of "no human ever found an algorithm" keeps dropping, and adds the alternative that humans may just occupy a cramped corner of complexity space where asymptotic beauty doesn't matter for concrete parameters.

Original post →

More from Research

Research channel →