Fall 2013

Discrete Tori and Bounds for Linear Codes

Friday, Dec. 6, 2013 3:00 pm3:45 pm PST

Add to Calendar

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.