Combinatorics Seminar

When: Sunday, January 6, 10am
Where: Schreiber 309
Speaker: Alex Samorodnitsky, Hebrew University
Title: Discrete tori and bounds for linear codes

Abstract:

Let C be a linear subspace of the Hamming cube H. Let C' be the dual code.

Following Friedman and Tillich we try to estimate the rate of growth of metric balls in the discrete "torus" T = H/C' and use this to upperbound the cardinality of T, and therefore of C.

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

This approach leads to different (and, we would like to think, easier) proofs of some known upper bounds and to some occasional improvements in the bounds.

Joint work with Eran Iceland.