HD-Combinatorics: Prahladh Harsha, "Local Testability and Expansion"

Locally testable codes are error-correcting codes that admit super-efficient checking procedures. In the first part of the talk, we will see why expander based codes are NOT locally testable. This is in contrast to typical "good" error correcting properties which follow from expansion. We will then see that despite this disconnect between expansion and testability, all known construction of locally testable codes follow from the high-dimensional expansion property of a related complex leaving open an intriguing connection between local-testability and high-dimension expanders. This talk will not assume any coding theory background.

Date: 

Mon, 04/06/2018 - 10:00 to 10:50

Location: 

Feldman Building, Givat Ram