The Power and Weakness of Randomness in Computation