IMSc Webinar
Reproducibility Meets Computational Complexity
Vinod Variyam
University of Nebraska – Lincoln, USA
Join the seminar at this link:
zoom.us/j/99018916192
Meeting ID: 990 1891 6192
Randomized algorithms play a central role in modern computing. For many computational tasks there are randomized algorithms that are simple and more efficient than their deterministic counterparts. Moreover, for several application areas including computations over massive data sets, distributed computing, and cryptography, randomization is a necessity. Despite their wide applicability, a serious drawback of randomized computations, as opposed to the deterministic ones, is their lack of reproducibility: two different runs of the same randomized algorithm can produce two different valid outputs. Thus a significant question is: can we design randomized algorithms for important computational tasks that are also reproducible?
In this talk, I will first introduce pseudo-determinism, a notion that formalizes reproducibility in randomized algorithms, and then show how the task of designing pseudo-deterministic algorithms is fundamentally related to certain well-investigated questions in computational complexity theory.
This is joint work with Peter Dixon, Aduri Pavan, and Jason Vander Woude.
Done