Property testing and LTC codes

Alex Lubotzky, Minerva Distinguished Visitor, & Weizmann Institute
Fine Hall Common Room

Property testing is an area in computer science dealing with problems of the following kind: can we (randomly) test only a small amount of the full data to reveal whether a global property is satisfied. Locally testable codes (LTC) form an important special case. The existence of ``good" LTC has been a major open problem in the area. It was recently solved via high dimensional expanders. Along the way we will see that the coboundary expansion can also be thought of as property testing, and so can Garland's local to global approach.