Tata Institute of Fundamental Research
Searching valiantly for LTCs
STCS Student Seminar
Speaker:
Ashutosh Shankar (TIFR, Mumbai.)
Organiser:
Eeshan Modak
Date:
Friday, 30 Sep 2022, 16:00 to 17:00
Venue:
A201
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Ashutosh Shankar (TIFR, Mumbai.) |
| Organiser: | Eeshan Modak |
| Date: | Friday, 30 Sep 2022, 16:00 to 17:00 |
| Venue: | A201 |
(Scan to add to calendar)
Abstract:
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.