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

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: