Rounds versus time for the two person pebble game (Q2641235)

The two-person pebble game is played on a directed acyclic graph G of bounded fan-in, between two adversaries called Pebbler and Challenger. To begin, Challenger places a challenge on a vertex. Then Pebbler places some pebbles on vertices of G. In each round of the game, Challenger either retains the challenge, or challenges a vertex that has just been pebbled. The two adversaries alternate in this way until, at the beginning of Pebbler's move, all immediate predecessors of the challenged vertex are already pebbled, in which case Challenger has lost. The number R of rounds in a game is equal to the number of moves of Challenger. If, against optimal play by Challenger, Pebbler can win using at most t pebbles, one says that G can be pebbled in time t. The paper is concerned with rounds/time tradeoffs, and obtains the following results: (1) For every R and n \((R=O(n/\log n))\), there is a bounded degree graph of n vertices for which Pebbler can win in R rounds only in time (n/log R). (2) There is a graph that exhibits almost tight round/time tradeoffs for all rounds. (3) There is no graph with tight round/time tradeoffs for all rounds. As a consequence the authors improve the simulation of bounded fan-in circuits by unbounded fan-in circuits, extending the size/depth tradeoff of Paterson and Valiant.