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.