# 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})$.