Student Presentation #1

(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 , where is the number of inputs and outputs. In addition, with a given depth , they get a  WSNB generalized connectors with size .

Student Presentation #5

(Guest post by Yang Wang)

I presented the paper on linear time encodable and decodable code. We get a good error correcting code by using error reduction code. Because of limited time, I mainly talked about the decoding of  error reduction codes. Note that the codes we talked about is a little different from usual codes in that they can be represented as bipartite graphs where the left side stands for message nodes, right side stands for check nodes and left side and right side together make up the codeword of the code. The first result was a simple explicit  -regular bipartite graph where each node in the right side stands for just one check bit. We proved that this construction can reduce errors to half as long as the number of errors are bounded. The second explicit construction was more complicated. We first start with a -regular expander and then get the corresponding bipartite graph as edge vertex incident graph. Now every check node in the right side of the bipartite graph stands for several check bits and every check node together with these message node neighbors is a word of another code. In fact we used a small code and an expander to construct the error reduction code we wanted.

Presentations

You will present papers in pairs. Each pair will get two weeks to present two papers: one on expanders and one on property testing. Email us your pair’s information by Wednesday, September 3, 2008. The student presentations on papers related to expanders will start in about 4.5 weeks.

Some suggestions for papers related to expanders is already online. The list of suggested papers on property testing should be up in a a couple of weeks at the same place. You can choose a paper outside the list, which is relevant (get approval from us first though).

Please let us know as soon as your group chooses a paper (as the ones in the suggested list will be “alloted” on a first-come-first-serve basis).