Information lower bounds via self-reducibility