Questions: Are there references which mention the relation between pebble games and conversions to bounded width circuits?

Here, "conversions to bounded width circuits" means that circuits of size $s$ are converted to circuits of size $f(s)$ and width $g(s)$.

I have noticed that a pebble game is closely related to the conversions (even for nondeterministic circuits). The relation is quite natural, and I'm wondering whether the relation has been already mentioned somewhere, although I think there will be probably no reference. (Since the definition of the pebble game is a little bit long, I write a reference. The pebble game is Definition 2.10 of Nordstrom's arXiv manuscript (page 14 of the 3rd version) https://arxiv.org/abs/1307.3913 .)

  • $\begingroup$ Can you clarify what you mean by "circuit width" here? $\endgroup$ May 12 at 18:52
  • 1
    $\begingroup$ Although the definition of "circuit width" is also a little bit long, the next comment is a copy of my (arXiv) paper. $\endgroup$ May 12 at 19:46
  • 2
    $\begingroup$ [Definition (circuit width)] When we consider the width of a circuit, we temporarily insert COPY gates to the circuit. A COPY gate is a dummy gate which simply outputs its input. A circuit is layered if its set of gates can be partitioned into subsets called layers such that every edge in the circuit is between adjacent layers. Note that every circuit is naturally converted to a layered circuit by inserting COPY gates to each edge which jumps over some layers. The width of a layer is the number of gates in the layer. The width of a circuit is the maximum width of all layers in the circuit. $\endgroup$ May 12 at 19:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.