Center for Algorithms and Theory of Computation

CS 269S, Spring 2021: Theory Seminar


May 14, 2021, 1:00 – 1:50:

Pseudo-Determinism: The New Frontier for Randomness

Karthik Gajulapalli

While understanding how randomness affects computation has been one of the core tenets of complexity theory for the last 50 years, many fundamental problems still seem far away from being resolved. In this talk I will present the study of randomness through the lens of pseudo-determinism and see if this newer notion of pseudo-determinism may be a viable stepping stone to bridging the gap between \(\mathsf{BPP}\) and \(\mathsf{P}\). No background in complexity is required.