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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.