I have two questions concerning the paper Nearly linear-size holographic proofs. In the second paragraph of section 6, A Graph Coloring Problem, it is claimed that
Using standard packet-routing techniques [Lei92], we can find switching actions for each node that establish collision-free paths in the graph for each packet.
The goal is to emulate a circuit (containing $m$ (arity 1 and 2 only ?) gates and $n$ inputs) using 5 consecutive copies of the butterly network of order $r$ (where $2^r\geq n+m$).
First question
- Where do I find the quoted result in [Lei92] ?
I am unable to locate the relevant result in Introduction to parallel Algorithms and Architectures, F.T. Leighton. I didn't find anything on the internet either when looking for "embedding directed acyclic graphs in butterfly networks" for instance. I found many interesting results about routing permutations, and there is a whole section that talks about packet routing, but I can't find what the authors quote...
In the following paragraph, the authors discuss the labels one may put on nodes. In particular they write that there are
4 switches (depending on how you count them)
It would seem most natural to me to have
- the empty switch : we won't be routing anything through here
- two "single wire going straight ahead" kind of switches
- two "single wire making a switch" kind of switches
- two fan-out switches
- one "two wires coming in and going straight ahead" kind of swich
- one "two wires coming in and making a switch" kind of switch
for a total of 9 ``natural'' switch types for intermediate nodes in the router. I can see that the 9 switches I describe can be clustered in 4 categories
- empty (only 1 of this kind)
- 1-1 (single wire in, single wire out : 4 of this kind),
- 1-2 (fan out : 2 of this kind),
- 2-2 (two wires in, two wires out : 2 of this kind)
Second question
- Why would the authors only talk of 4 switches ? Is this somehow more natural than ?
