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.