Rounds versus time for the two person pebble game
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.
- A universal prior for integers and estimation by minimum description length
- Asymptotically tight bounds on time-space trade-offs in a pebble game
- Circuit size is nonlinear in depth
- Computing multivariate polynomials in parallel
- On sparse graphs with dense long paths
- On Time Versus Space
- On uniform circuit complexity
- Space bounds for a game on graphs
- Speedups of deterministic machines by synchronous parallel machines
- Superconcentrators
- Speedup of determinism by alternation for multidimensional Turing machines
- Reversible pebble game on trees
- scientific article; zbMATH DE number 3976363 (Why is no real title available?)
- scientific article; zbMATH DE number 1333612 (Why is no real title available?)
- Rounds versus time for the two person pebble game (extended abstract)
This page was built for publication: Rounds versus time for the two person pebble game
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2641235)
