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