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

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

  1. Why would the authors only talk of 4 switches ? Is this somehow more natural than ?


Your Answer

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

Browse other questions tagged or ask your own question.