New algorithm breaks speed limit for solving linear equations

Re:New algorithm breaks speed limit for solving linear equat... by okintheory on Tuesday March 09, 2021 @04:02AM (#26396801)

Not really. This algorithm is only fast with high probability, and getting a linear equation solver to be always-correct is just a matter of checking the output at the end and trying again if you're (too) wrong. So always-correct and fast-with-high-probability is a feature of any randomized linear equation solver. It still amazing stuff, I'm just pointing out that this particular aspect of the behaviour is not surprising.

[ Parent | on HN ]

Re:New algorithm breaks speed limit for solving linear equat... by blt on Tuesday March 09, 2021 @08:06PM (#26406574)

Thanks for your insight!

> This algorithm is only fast with high probability

Why is this not mentioned in Theorem 1.1?

[ Parent | on HN ]

Re:New algorithm breaks speed limit for solving linear equat... by okintheory on Wednesday March 10, 2021 @08:01AM (#26410774)

This is a pretty common omission to make, even though it's strictly speaking wrong. But suppose for a moment that the algorithm was always fast. In that case, it would not need randomness anymore, as you could just pick a fixed string as the "random" outcome, and you would be guaranteed success. So, if an algorithm uses randomness, it will either fail with some probability or be slow with some probability. If neither is true, that algorithm doesn't need the randomness.

[ Parent | on HN ]

Re:New algorithm breaks speed limit for solving linear equat... by blt on Wednesday March 10, 2021 @02:21PM (#26415007)

Makes sense. Thank you for the thoughtful response. I hope my original comment is not too misleading.

[ Parent | on HN ]