Tata Institute of Fundamental Research
Pseudo-deterministic Algorithms
STCS Student Seminar
Speaker:
Vishwas Bhargava (Rutgers University
New Brunswick-Piscataway
New Jersey
United States)
Organiser:
Tulasi mohan Molli
Date:
Friday, 24 Aug 2018, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Vishwas Bhargava (Rutgers University New Brunswick-Piscataway New Jersey United States) |
| Organiser: | Tulasi mohan Molli |
| Date: | Friday, 24 Aug 2018, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.