EE Seminar: Coset leader graphs and bounds for binary linear codes

~~(The talk will be given in English)

Speaker:   Prof. Alex Samorodnitsky
                  Computer Science and Engineering, Hebrew University

Monday, April 13th, 2015
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering

Coset leader graphs and bounds for binary linear codes

Abstract
Let C be a binary linear code. Let C' be the dual code. We try to obtain bounds on the rate of C by analyzing the weight distribution of coset leaders of C'.
For this purpose, following Friedman and Tillich, we define a graph whose vertices are indexed by the coset leaders of C' and estimate the rate of growth of metric balls in this graph.
A notion of discrete Ricci curvature of metric spaces, as defined by Ollivier, turns out to be useful in some cases where C' has local structure (that is C is locally correctable / locally testable).

Joint work with Eran Iceland.