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: https://youtu.be/Qf10_ngKMRw

References

  1. Reversible programming
    https://github.com/GiggleLiu/NiLang.jl
  2. Optimal checkpointing
    https://www.tandfonline.com/doi/abs/10.1080/10556789208805505