Information Lower Bounds via Self-Reducibility