Searching valiantly for LTCs


Ashutosh Shankar


TIFR, Mumbai.


Friday, 30 September 2022, 16:00 to 17:00


  • A201


A desirable property for a code is "local testability" - being able to look at a small number of locations and determine if the received word is a codeword or far from one. Given two base codes, one can construct a tensor code: matrices with rows in one code, and columns in the other. A natural local test for this would be to randomly pick a row or column and check if it is in that base code. Unfortunately, this fails - we will look at a neat counterexample by Paul Valiant (2005). However, if one of the codes is "smooth", the test works. Time permitting, we will look at the definition of smoothness (later relaxed to "weakly smooth") and a sketch of the analysis in that case.