Pseudo-deterministic Algorithms

Speaker: 

Vishwas Bhargava

Affiliation: 

Rutgers University
New Brunswick-Piscataway
New Jersey
United States

Time: 

Friday, 24 August 2018, 17:15 to 18:15

Venue: 

  • A-201 (STCS Seminar Room)

Organisers: 

In this talk, we describe a new type of probabilistic algorithm (introduced by Gat and Goldwasser [GG11]) called Pseudo-deterministic Algorithms: a randomized algorithm which is guaranteed to run in expected polynomial time and to produce a correct and unique solution with high probability.

The name comes from the fact that they can not be distinguished from deterministic algorithms in polynomial time by a probabilistic polynomial time observer with black-box access to the algorithm.

We will discuss some interesting algorithms as well as open problems. We will also look at  Pseudo-deterministic Algorithms from a complexity point of view.