Expanders, Property Testing and the PCP theorem

Student Presentation #4

Posted in presentations by atri on November 17, 2008

(Guest post by Swapnoneel Roy)

I presented the first algorithmic result in the paper Online Algorithms for Path Selection in a Nonblocking Network by Sanjeev Arora, Tom Leighton and Bruce Maggs. The algorithm was applied on a Multi-Butterfly network with N inputs and outputs with the (\alpha, \delta) unshared neighbor property. In the algorithm, all the paths were extended from level \ell to level \ell+1 (for any level \ell) of the network by performing the following steps:

  1. every path that waits to be extended sends out a “proposal” to each of its output level \ell+1  neighbors in the desired direction (up or down), 
  2. every output node that receives one proposal sends back its acceptance to that proposal,  
  3. every path that receives an acceptance advances to one of its accepting outputs on level \ell+1.

Going by this way, the algorithm extends the paths from level 0 to level \log N. The time taken to extend the paths from one level to the next was shown to be O(\log N). This makes the total running time of the algorithm O(\log^2{N}).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: