Combinatorics and TCS Seminar
Wednesday, 8th Nov. 2.30 pm
======================
Host: Niranjan Balachandran
Venue: Ramanujan Hall
Speaker: Venkitesh (University of Haifa, Israel)
Title: List Decoding Randomly Punctured Polynomial Ideal Codes
Abstract: List decoding is a paradigm in algorithmic coding theory, where for a received word (possibly corrupted to some extent), the objective is to efficiently obtain a small list of 'approximately correct' codewords. A classic problem in this context is to obtain constructions of 'polynomial-based' codes that can be optimally list decoded (up to the information-theoretic limit), with optimal field size and output list size. Such codes will be said to 'achieve list decoding capacity'. While no such 'perfectly optimal' explicit constructions are known as yet, it has been observed in previous works that a promising trick of 'folding' codewords enables achieving capacity (non-optimally in other parameters), prominently at the cost of a blow-up in the folding size as the 'gap to capacity' approaches zero. Some recent previous works showed a breakthrough where 'unfolded' polynomial codes (called Reed-Solomon codes) achieve capacity under a random choice of evaluation points. We observe a similar result in the folded setting, with the folding size, held constant (independent of the gap to capacity), and for a much larger class of 'polynomial ideal codes'. This talk is based on an ongoing joint work with Noga Ron-Zewi and Mary
Wootters.