What is the role of randomness in computation? This thesis focuses on the prBPP=prP conjecture, which asserts that randomness is not crucial for efficiently solving decision problems, as well as for solving a broad class of search problems.
The contributions in this thesis are two-fold. First, we make unconditional progress in the long-term effort towards proving the prBPP=prP conjecture. We consider several restricted settings that are prominent frontiers in the study of the conjecture, and within these restricted settings we study a relaxed version of the conjecture, called quantified derandomization. We then show two complementary results: We construct algorithms that solve this relaxed version within these restricted settings, and we show that even very mild improvement to the parameters achieved by these algorithms would suffice to prove the original (“non-relaxed”) version of the conjecture in these restricted settings. Moreover, we point at an inherent limitation of certain “blackbox” techniques in this context, which preclude algorithms that rely only on these techniques from closing the remaining gap in the parameters.
Secondly, we significantly strengthen the connections between the prBPP=prP conjecture and the question of lower bounds for algorithms and for non-uniform circuits. Specifically, we show that any proof that prBPP=prP implies circuit lower bounds that are significantly stronger compared to what was previously known; and (in the other direction), we show that strong lower bounds for uniform probabilistic algorithms imply (almost-)polynomial-time average-case derandomization of BPP. Lastly, we prove that certain lower bounds for a weak uniform model of computation are both sufficient and necessary in order to prove that the prBPP=prP conjecture is completely equivalent to specific circuit lower bounds.
Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, April 2020.
Available: the thesis (in PDF file).
Back to Oded Goldreich's homepage.