Pebble games - Time and space to differentiate a program

The trade-off between time and space is a central issue in reverse mode automatic differentiation. The optimal checkpointing allows people to access computational states in a reversed order with only logarithmic overheads in time and space. Bennett's reversible computing scheme also allows efficient time and space trade-offs. This talk is about the pros and cons of two time and space trade-off schemes within the simple pebble game setup that even a gorilla can understand.

Youtube Video:


  1. Reversible programming
  2. Optimal checkpointing