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.