Some computations, when performed on a machine
with a fixed amount of "fast" memory, must be
decomposed into smaller computations. Accordingly,
intermediate results must be stored in "slow" memory
and retrieved later in the computation. A two-pebble
game was introduced by Hong and Kung in order to model
this phenomenon and produce lower bounds on the number
of such transitions required by certain computations.
Some basic results from their paper will be presented,
along with some background material on pebbling.
Last modified 8 April 2003