Pseudo-deterministic Algorithms

Conference object English OPEN
Goldwasser , Shafi;
(2012)
  • Publisher: LIPIcs
  • Subject: [ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC] | randomized algorithms | [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS] | Monte Carlo | distributed computing | Las Vegas

International audience; In this talk we describe a new type of probabilistic algorithm which we call Bellagio Algorithms: a randomized algorithm which is guaranteed to run in expected polynomial time, and to produce a correct and unique solution with high probability. T... View more
Share - Bookmark