Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR19-109 | 21st August 2019 13:11

#### Decoding Downset codes over a finite grid

TR19-109
Authors: Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh
Publication: 23rd August 2019 16:39
In 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}.$