Theory Seminar: Please join us on March 10th at 11am in Siebel 3401 where Fernando Granha Jeronimo will give a talk, “The Unreasonable Effectiveness of Expanders in Coding Theory”. Please see the abstract below:
The probabilistic method is commonly used as a yardstick to establish the existence of codes exhibiting optimal properties. However, explicit constructions are typically needed to be able to use these codes, but these purely existential methods often give us no clue on how to do so, and progress can take decades to come. In this talk, I will discuss how expander graphs can be incredibly effective in designing explicit codes achieving close to optimal (list) decoding properties, giving us the first explicit examples only previously known to exist.