Rounds versus time for the two person pebble game

AbstractWe show the following results for rounds/time trade-offs in the two person pebble game: 1.1. For every R and n (R = O(nlogn)), there is a bounded degree graph of n vertices for which the Pebbler can win in R rounds only in time Ω(nlogR).2.2. There is a graph that exhibits almost tight round/time trade-offs for all rounds.3.3. There is no graph with tight round/time trade-offs for all rounds.As a consequence, we improve the simulation of bounded fan-in circuits by unbounded fan-in circuits, extending the size/depth trade-off of Paterson and Valiant