I wish we had a theory connecting randomness with time/space complexity.

Intuitively I think the key to many computational limitations is making use of randomness.