News for hackers. Stuff that matters.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by 1001101 on Monday April 03, 2017 @12:25PM (#14024164)
Las Vegas = Always Correct, Probably Fast

Monte Carlo = Probably Correct, Always Fast

Re:A Las Vegas algorithm to solve the elliptic curve discret... by funkaster on Monday April 03, 2017 @04:36PM (#14026894)
Adding speed to the classification is misleading. It might be better to state:

  - Las Vegas: Correct, Time unbounded
  - Monte Carlo: Not always correct, Time bounded
edit: format
Re:A Las Vegas algorithm to solve the elliptic curve discret... by kccqzy on Monday April 03, 2017 @04:41PM (#14026934)
As pointed out already, a Las Vegas algorithm might have bounded but non-deterministic time.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by thomasahle on Monday April 03, 2017 @03:04PM (#14026003)
I think people would probably call an algorithm that is "Probably Correct, Probably Fast" Monte Carlo as well.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by hyperbovine on Monday April 03, 2017 @01:20PM (#14024873)
Since when is Monte Carlo fast :-)
Re:A Las Vegas algorithm to solve the elliptic curve discret... by snovv_crash on Monday April 03, 2017 @01:59PM (#14025298)
More often than not, it is faster than figuring out the exact solution, if an exact solution exists. Things like having a piecewise distribution somewhere in your problem make Monte Carlo several orders of magnitude easier to implement.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by hyperbovine on Monday April 03, 2017 @05:37PM (#14027418)
The depends a lot of the dimension of the space you're trying to integrate over, and in any case, (vanilla) Monte Carlo is trivial to implement. I was more poking fun at the very different way theorists and practitioners view classes certain algorithms. "Deterministic running time" is not a particularly strong guarantee, in practice.