ECCC-Report TR19-109https://eccc.weizmann.ac.il/report/2019/109Comments and Revisions published for TR19-109en-usFri, 23 Aug 2019 16:39:00 +0300
Paper TR19-109
| Decoding Downset codes over a finite grid |
Utkarsh Tripathi,
Srikanth Srinivasan,
S Venkitesh
https://eccc.weizmann.ac.il/report/2019/109In a recent paper, Kim and Kopparty (Theory of Computing, 2017) gave a deterministic algorithm for the unique decoding problem for polynomials of bounded total degree over a general grid $S_1\times\cdots \times S_m.$ We show that their algorithm can be adapted to solve the unique decoding problem for the general family of Downset codes. Here, a downset code is specified by a family $\mathcal{D}$ of monomials closed under taking factors: the corresponding code is the space of evaluations of all polynomials that can be written as linear combinations of monomials from $\mathcal{D}.$
Fri, 23 Aug 2019 16:39:00 +0300https://eccc.weizmann.ac.il/report/2019/109