Center for Algorithms and Theory of Computation

CS 269S, Winter 2019: Theory Seminar
Bren Hall, Room 1423, 1pm


January 25, 2019:

In pursuit of a Randomized Time Hierarchy Theorem

Karthik Gajulapalli

In proving lower bounds we rely heavily on the time hierarchy theorems. By breaking the time hierarchy theorems we are able to show contradictions. Since we have time hierarchy theorems on deterministic turing machines and non deterministic turing machines, it seems natural to think about how more time and more randomness would affect a randomized machine. Interestingly we do not have a hierarchy on randomized machines, yet if we allow the machines to take 1 bit of advice we are able to achieve a desired hierarchy. Can we ever achieve a randomized time hierarchy in a uniform model of computation?

This was a survey paper I had written as the project requirements for a course on circuit lowerbounds. The survey summarizes the work of Barak, Goldriech, Melkebeek and others.