News for hackers. Stuff that matters.

A comment on Galactic Algorithm.

Re:Galactic Algorithm by cperciva on Saturday October 05, 2019 @12:49AM (#21163870)
In addition to galactic algorithms, there are also galactically proven algorithms. One example is the algorithm for matching with mismatches which I presented in the first chapter of my doctoral thesis; I proved that it was faster than other algorithms for inputs of at least ~10^30 bytes.

In practice, it wins starting at around 10^4 bytes.

[ Parent | on HN ]
Re:Galactic Algorithm by Gehinnn on Saturday October 05, 2019 @08:01AM (#21165043)
How do you prove that something is faster than everything else? Was it already running in linear-time?

There aren't many non-trivial lower bounds out there, and I think they all use one of three ideas (diagonalization, crossing sequences or oracle reconstruction)!

[ Parent | on HN ]
Re:Galactic Algorithm by cperciva on Saturday October 05, 2019 @12:21PM (#21166335)
Sorry, I was unclear. I proved that my algorithm was faster than other known algorithms; I didn't prove that it was faster than all other possible algorithms.
[ Parent | on HN ]