# Expanders, Property Testing and the PCP theorem

## Student Presentation #1

Posted in presentations by atri on November 9, 2008

(Guest post by Than Nguyen)

I presented the paper by Paul Feldman, Joel Friedman and Nichloas Pippenger titled Wide-sense nonblocking networks.

A network is an acyclic directed graph that allows connections to be made between a set of vertices, called inputs, to another disjoint set of vertices, called outputs. A network is called wide-sense nonblocking (WSNB) if a request from an idle input to an idle output can be always satisfied. This paper suggests a new way to construct “generalized concentrators” by using certain expanders. From this, they build WSNB generalized connectors with size $O(n \log n)$, where $n$ is the number of inputs and outputs. In addition, with a given depth $k$, they get a  WSNB generalized connectors with size $O(n^{1+1/k} (\log n))^{1- 1/k}$.