2
$\begingroup$

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 .)

Improve this question
$\endgroup$
3
  • $\begingroup$ Can you clarify what you mean by "circuit width" here? $\endgroup$
    – Joshua Grochow
    May 12, 2022 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$
    – Hiroki Morizumi
    May 12, 2022 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$
    – Hiroki Morizumi
    May 12, 2022 at 19:50

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.