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.