Efficient pebbling for list traversal synopses

Yossi Matias, Ely Porat

We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using $O(\log n)$ memory for a list…