Pseudo-deterministic Algorithms

Conference object English OPEN
Goldwasser , Shafi;
  • 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] | [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS] | [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] | 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