Summer 2019

Connection Between Codes and HDX

Friday, Jul. 12, 2019 9:00 am11:00 am PDT

Add to Calendar


Prahladh Harsha (Tata Institute of Fundamental Research)

Expander graphs have myriad applications in coding theory giving rise to error-correcting codes with constant relative distance and rate equipped with extremely efficient encoding, unique-decoding and list-decoding procedures. Over the last decade and a half, local versions of these procedures have been extensively studied in theoretical computer science. For instance, Locally testable codes are error-correcting codes that admit super-efficient checking procedures.

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.