<p><strong>Questions:</strong> Are there references which mention the relation between pebble games and conversions to bounded width circuits?</p>
<p>Here, &quot;conversions to bounded width circuits&quot; means that circuits of size <span class="math-container">$s$</span> are converted to circuits of size <span class="math-container">$f(s)$</span> and width <span class="math-container">$g(s)$</span>.</p>
<p>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) <a href="https://arxiv.org/abs/1307.3913" rel="nofollow noreferrer">https://arxiv.org/abs/1307.3913</a> .)</p>

CC BY-SA 4.0
2022-05-12T18:52:10.160Z
Can you clarify what you mean by "circuit width" here?
Joshua Grochow
CC BY-SA 4.0
2022-05-12T19:46:37.817Z
Although the definition of "circuit width" is also a little bit long, the next comment is a copy of my (arXiv) paper.
Hiroki Morizumi
CC BY-SA 4.0
2022-05-12T19:50:10.797Z
[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.
Hiroki Morizumi
<cc.complexity-theory><reference-request><circuit-complexity>
Pebble games and conversions to bounded width circuits
Hiroki Morizumi
# Pebble games and conversions to bounded width circuits

(Asked by: username_0 on 2022-05-12)

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

**Tags:** cc.complexity-theory, reference-request, circuit-complexity
> **Comments:**
> **username_1**: Can you clarify what you mean by "circuit width" here?  
> **username_0**: Although the definition of "circuit width" is also a little bit long, the next comment is a copy of my (arXiv) paper.  
> **username_0**: [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.  

---

## 0 answers

