Graph capacity, broadcast rate and local repair

Mon, Sep. 28

3-4PM

400 Cory

3-4PM

400 Cory

Recently, the local repair property of error-correcting codes is the center of a lot of attention due to applications in distributed storage systems. We generalize the notion of local repair to include the topology of networks of such systems. Assume that, information is to be stored in vertices of a graph in a way such that the conditional entropy of content of any vertex given its neighbors is zero. Then what is the maximum amount of information that can be stored in the graph?

We estimate the above graph capacity and propose some constructive schemes. Among other results, we provide an upper (converse) bound on the minimum pairwise distance of a set of words that can be stored in a graph with the above local repair guarantee. The well-known impossibility bounds on the distance of locally recoverable codes (Gopalan et al, 2011; Cadambe, Mazumdar, 2013) follow from our result.

The above graph parameter is closely related to the well-studied broadcasting with side information (index coding) problem. We will discuss some nice open problems in this area. Further we point that, the reverse (synthesis) problem of learning the graph given the information to be stored is equivalent to designing neural networks for associative memory.

Bio: Arya Mazumdar is an assistant professor in University of Minnesota-Twin Cities (UMN) since January 2013. Before coming to UMN, he was a postdoctoral scholar at the Massachusetts Institute of Technology (MIT). He received his Ph.D. degree from University of Maryland, College Park, in 2011.

Arya is a recipient of 2014-15 NSF CAREER award and the 2010 IEEE ISIT Student Paper Award. He is also the recipient of the Distinguished Dissertation Fellowship Award, 2011, at the University of Maryland. He spent the summers of 2008 and 2010 at the Hewlett-Packard Laboratories, Palo Alto, CA, and IBM Almaden Research Center, San Jose, CA, respectively. Arya's research interests include Error-Correcting Codes, Information Theory and their applications.

We estimate the above graph capacity and propose some constructive schemes. Among other results, we provide an upper (converse) bound on the minimum pairwise distance of a set of words that can be stored in a graph with the above local repair guarantee. The well-known impossibility bounds on the distance of locally recoverable codes (Gopalan et al, 2011; Cadambe, Mazumdar, 2013) follow from our result.

The above graph parameter is closely related to the well-studied broadcasting with side information (index coding) problem. We will discuss some nice open problems in this area. Further we point that, the reverse (synthesis) problem of learning the graph given the information to be stored is equivalent to designing neural networks for associative memory.

Bio: Arya Mazumdar is an assistant professor in University of Minnesota-Twin Cities (UMN) since January 2013. Before coming to UMN, he was a postdoctoral scholar at the Massachusetts Institute of Technology (MIT). He received his Ph.D. degree from University of Maryland, College Park, in 2011.

Arya is a recipient of 2014-15 NSF CAREER award and the 2010 IEEE ISIT Student Paper Award. He is also the recipient of the Distinguished Dissertation Fellowship Award, 2011, at the University of Maryland. He spent the summers of 2008 and 2010 at the Hewlett-Packard Laboratories, Palo Alto, CA, and IBM Almaden Research Center, San Jose, CA, respectively. Arya's research interests include Error-Correcting Codes, Information Theory and their applications.

UC Berkeley Networking

Ashwin Pananjady and Orhan Ocal

Last Modification Date: Wednesday, February 10, 2016

Ashwin Pananjady and Orhan Ocal

Last Modification Date: Wednesday, February 10, 2016